Header files for the target architecture description and for instruction

selection, and instances of these for the SPARC.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@226 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 1362 insertions, 0 deletions

diff --git a/include/llvm/CodeGen/InstrForest.h b/include/llvm/CodeGen/InstrForest.h
new file mode 100644
index 0000000000..c49933f3b3
--- /dev/null
+++ b/include/llvm/CodeGen/InstrForest.h
@@ -0,0 +1,339 @@
+/* $Id$ -*-c++-*-
+ ****************************************************************************
+ * File:
+ *	InstrForest.h
+ * 
+ * Purpose:
+ *	Convert SSA graph to instruction trees for instruction selection.
+ * 
+ * Strategy:
+ *  The basic idea is that we would like to group instructions into a single
+ *  tree if one or more of them might be potentially combined into a single
+ *  complex instruction in the target machine.
+ *  Since this grouping is completely machine-independent, it is as
+ *  aggressive as possible.  In particular, we group two instructions
+ *  O and I if:
+ *  (1) Instruction O computes an operand of instruction I, and
+ *  (2) O and I are part of the same basic block, and
+ *  (3) O has only a single use, viz., I.
+ * 
+ * History:
+ *	6/28/01	 -  Vikram Adve  -  Created
+ ***************************************************************************/
+
+#ifndef LLVM_CODEGEN_INSTRFOREST_H
+#define LLVM_CODEGEN_INSTRFOREST_H
+
+/*
+ CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
+ C
+ C The following types and macros are visible to the C code generated
+ C by BURG.
+ */
+
+extern "C" {
+  
+  //-------------------------------------------------------------------------
+  // Data types needed by BURG and implemented by us
+  //-------------------------------------------------------------------------
+  
+  typedef int OpLabel;
+  typedef int StateLabel;
+  
+  typedef struct BasicTreeNode_struct {
+    
+    BasicTreeNode_struct* leftChild;
+    BasicTreeNode_struct* rightChild;
+    BasicTreeNode_struct* parent;
+    OpLabel		  opLabel;
+    StateLabel		  state;
+    void*		  treeNodePtr;	/* points to the C++ tree node object
+					 * that "contains" this node */
+  } BasicTreeNode;
+  
+  //-------------------------------------------------------------------------
+  // Declarations of data and functions created by BURG
+  //-------------------------------------------------------------------------
+  
+# ifdef __STDC__
+#   define ARGS(x) x
+# else
+#   define ARGS(x) ()
+# endif
+
+  extern short*		burm_nts[];
+  
+  extern StateLabel	burm_label	ARGS((BasicTreeNode* p));
+  
+  extern StateLabel	burm_state	ARGS((OpLabel op,
+					      StateLabel leftState,
+					      StateLabel rightState));
+  
+  extern StateLabel	burm_rule	ARGS((StateLabel state,
+						      int goalNT));
+  
+  extern BasicTreeNode** burm_kids	ARGS((BasicTreeNode* p,
+					      int eruleno,
+					      BasicTreeNode* kids[]));
+  
+  extern void		printcover	ARGS((BasicTreeNode*, int, int));
+  extern void		printtree	ARGS((BasicTreeNode*));
+  extern int		treecost	ARGS((BasicTreeNode*, int, int));
+  extern void		printMatches	ARGS((BasicTreeNode*));
+
+}
+/* end extern "C" */
+
+
+/*CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC*/
+
+
+#ifdef __cplusplus
+
+//************************** System Include Files **************************/
+
+#include <bool.h>
+#include <hash_map>
+#include <hash_set>
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Support/Unique.h"
+#include "llvm/Instruction.h"
+
+//************************* Opaque Declarations ****************************/
+
+class Value;
+class Instruction;
+class ConstPoolVal;
+class BasicBlock;
+class Method;
+class InstrTreeNode;
+class InstrForest;
+
+//************************ Exported Constants ******************************/
+
+
+//--------------------------------------------------------------------------
+// OpLabel values for special-case nodes created for instruction selection.
+// All op-labels not defined here are identical to the instruction
+// opcode returned by Instruction::getInstType()
+//--------------------------------------------------------------------------
+
+const int  InvalidOp	=  -1;
+const int  VRegListOp   =  97;
+const int  VRegNodeOp	=  98;
+const int  ConstantNodeOp= 99;
+const int  LabelNodeOp	= 100;
+
+const int  RetValueOp	= 100 + Instruction::Ret;
+const int  BrCondOp	= 100 + Instruction::Br;
+
+const int  SetCCOp	= 100 + Instruction::SetEQ;
+
+const int  AllocaN	= 100 + Instruction::Alloca;		// 121
+const int  LoadIdx	= 100 + Instruction::Load;		// 122
+const int  GetElemPtrIdx= 100 + Instruction::GetElementPtr;	// 124
+
+const int  ToBoolTy	= 100 + Instruction::Cast;		// 126
+const int  ToUByteTy	= ToBoolTy +  1;
+const int  ToSByteTy	= ToBoolTy +  2;
+const int  ToUShortTy	= ToBoolTy +  3;
+const int  ToShortTy	= ToBoolTy +  4;
+const int  ToUIntTy	= ToBoolTy +  5;
+const int  ToIntTy	= ToBoolTy +  6;
+const int  ToULongTy	= ToBoolTy +  7;
+const int  ToLongTy	= ToBoolTy +  8;
+const int  ToFloatTy	= ToBoolTy +  9;
+const int  ToDoubleTy	= ToBoolTy + 10;
+const int  ToArrayTy	= ToBoolTy + 11;
+const int  ToPointerTy	= ToBoolTy + 12;
+
+
+//************************ Exported Data Types *****************************/
+
+struct ptrHashFunc {
+  inline size_t operator()(const void* const& p) const
+  {
+    // Copied from body of hash<unsigned long>::operator().
+    // I cannot figure out how to invoke that without an object
+    return (size_t) ((const unsigned long) p);
+  }
+};
+
+
+//------------------------------------------------------------------------ 
+// class InstrTreeNode
+// 
+// A single tree node in the instruction tree used for
+// instruction selection via BURG.
+//------------------------------------------------------------------------ 
+
+inline InstrTreeNode*
+MainTreeNode(BasicTreeNode* node) {
+  return (InstrTreeNode*) node->treeNodePtr;
+}
+
+
+class InstrTreeNode: public Unique {
+public:
+  enum InstrTreeNodeType { NTInstructionNode,
+			   NTVRegListNode,
+			   NTVRegNode,
+			   NTConstNode,
+			   NTLabelNode };
+  
+protected:
+  BasicTreeNode    basicNode;
+  InstrTreeNodeType treeNodeType;
+  Value*	   val;
+  
+public:
+  /*ctor*/		InstrTreeNode	(InstrTreeNodeType nodeType,
+					 Value* _val);
+  /*dtor*/ virtual	~InstrTreeNode	();
+  
+  BasicTreeNode*	getBasicNode	()	 { return &basicNode; }
+  
+  InstrTreeNodeType	getNodeType	() const { return treeNodeType; }
+  
+  Value*		getValue	() const { return val; }
+  
+  inline OpLabel	getOpLabel	() const { return basicNode.opLabel; }
+  
+  inline InstrTreeNode*	leftChild	() const {
+    return (InstrTreeNode*)
+      (basicNode.leftChild? basicNode.leftChild->treeNodePtr : NULL);
+  }
+  
+  // If right child is a list node, recursively get its *left* child
+  inline InstrTreeNode* rightChild	() const {
+    return (InstrTreeNode*)
+      (basicNode.rightChild
+       ? (MainTreeNode(basicNode.rightChild)->getOpLabel() == VRegListOp
+	  ? MainTreeNode(basicNode.rightChild)->leftChild()
+	  : MainTreeNode(basicNode.rightChild))
+       : NULL);
+  }
+  
+  inline InstrTreeNode*	parent		() const {
+    return (InstrTreeNode*)
+      (basicNode.parent? basicNode.parent->treeNodePtr : NULL);
+  }
+  
+  void			dump		(int dumpChildren,
+					 int indent) const;
+  
+protected:
+  virtual void		dumpNode	(int indent) const = 0;
+
+  friend class InstrForest;
+};
+
+
+class InstructionNode: public InstrTreeNode {
+public:
+  /*ctor*/	InstructionNode		(Instruction* _instr);
+  Instruction*	getInstruction		() const { return (Instruction*) val; }
+  void		reverseBinaryArgumentOrder();
+protected:
+  virtual void		dumpNode	(int indent) const;
+};
+
+
+class VRegListNode: public InstrTreeNode {
+public:
+  /*ctor*/		VRegListNode	();
+protected:
+  virtual void		dumpNode	(int indent) const;
+};
+
+
+class VRegNode: public InstrTreeNode {
+public:
+  /*ctor*/		VRegNode	(Value* _val);
+protected:
+  virtual void		dumpNode	(int indent) const;
+};
+
+
+class ConstantNode: public InstrTreeNode {
+public:
+  /*ctor*/		ConstantNode	(ConstPoolVal* constVal);
+  ConstPoolVal*		getConstVal	() const { return (ConstPoolVal*) val;}
+protected:
+  virtual void		dumpNode	( int indent) const;
+};
+
+
+class LabelNode: public InstrTreeNode {
+public:
+  /*ctor*/		LabelNode	(BasicBlock* _bblock);
+  BasicBlock*		getBasicBlock	() const { return (BasicBlock*) val;}
+protected:
+  virtual void		dumpNode	(int indent) const;
+};
+
+
+//------------------------------------------------------------------------
+// class InstrForest
+// 
+// A forest of instruction trees, usually for a single method.
+//
+// Methods:
+//     buildTreesForMethod()	Builds the forest of trees for a method
+//     getTreeNodeForInstr()	Returns the tree node for an Instruction
+//     getRootSet()		Returns a set of root nodes for all the trees
+// 
+//------------------------------------------------------------------------ 
+
+class InstrForest :
+  public Unique,
+  private hash_map<const Instruction*, InstructionNode*, ptrHashFunc > {
+  
+private:
+  hash_set<InstructionNode*, ptrHashFunc > treeRoots;
+  
+public:
+  /*ctor*/	InstrForest		()	    {}
+  /*dtor*/	~InstrForest		()	    {}
+  
+  void		buildTreesForMethod	(Method *method);
+				    
+  inline InstructionNode*
+  getTreeNodeForInstr(Instruction* instr)
+  {
+    return (*this)[instr];
+  }
+  
+  inline const hash_set<InstructionNode*, ptrHashFunc>&
+  getRootSet() const {
+    return treeRoots;
+  }
+  
+  void		dump			() const;
+  
+private:
+  //
+  // Private methods for buidling the instruction forest
+  //
+  void		setLeftChild		(InstrTreeNode* parent,
+					 InstrTreeNode* child);
+  
+  void		setRightChild		(InstrTreeNode* parent,
+					 InstrTreeNode* child);
+  
+  void		setParent		(InstrTreeNode* child,
+					 InstrTreeNode* parent);
+  
+  void		noteTreeNodeForInstr	(Instruction* instr,
+					 InstructionNode* treeNode);
+  
+  InstructionNode* buildTreeForInstruction(Instruction* instr);
+};
+
+//---------------------------------------------------------------------------
+
+#endif	/* #ifdef __cplusplus */
+
+#endif  /* #ifndef INSTRFOREST_H */
diff --git a/include/llvm/CodeGen/InstrSelection.h b/include/llvm/CodeGen/InstrSelection.h
new file mode 100644
index 0000000000..7538a1532b
--- /dev/null
+++ b/include/llvm/CodeGen/InstrSelection.h
@@ -0,0 +1,121 @@
+// $Id$ -*-c++-*-
+//***************************************************************************
+// File:
+//	InstrSelection.h
+// 
+// Purpose:
+//	
+// History:
+//	7/02/01	 -  Vikram Adve  -  Created
+//***************************************************************************
+
+#ifndef LLVM_CODEGEN_INSTR_SELECTION_H
+#define LLVM_CODEGEN_INSTR_SELECTION_H
+
+//************************** System Include Files **************************/
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Instruction.h"
+
+//************************* Opaque Declarations ****************************/
+
+class CompileContext;
+class Instruction;
+class Method;
+class InstrForest;
+class MachineInstruction;
+class TmpInstruction;
+
+
+//************************ Exported Constants ******************************/
+
+const int	DEBUG_INSTR_TREES = 2;
+const int	DEBUG_BURG_TREES  = 5;
+
+
+//****************** External Function Prototypes **************************/
+
+//---------------------------------------------------------------------------
+// GLOBAL data and an external function that must be implemented
+// for each architecture.
+//---------------------------------------------------------------------------
+
+const unsigned MAX_INSTR_PER_VMINSTR = 8;
+
+extern unsigned	GetInstructionsByRule	(InstructionNode* subtreeRoot,
+					 int ruleForNode,
+					 short* nts,
+					 CompileContext& ccontext,
+					 MachineInstr** minstrVec);
+
+extern bool	ThisIsAChainRule	(int eruleno);
+
+
+//************************ Exported Data Types *****************************/
+
+
+//---------------------------------------------------------------------------
+// Function: SelectInstructionsForMethod
+// 
+// Purpose:
+//   Entry point for instruction selection using BURG.
+//   Returns true if instruction selection failed, false otherwise.
+//   Implemented in machine-specific instruction selection file.
+//---------------------------------------------------------------------------
+
+bool		SelectInstructionsForMethod	(Method* method,
+						 CompileContext& ccontext);
+
+
+// Debugging function to print the generated instructions
+void		PrintMachineInstructions	(Method* method,
+						 CompileContext& ccontext);
+
+
+//---------------------------------------------------------------------------
+// Function: FoldGetElemChain
+// 
+// Purpose:
+//   Fold a chain of GetElementPtr instructions into an equivalent
+//   (Pointer, IndexVector) pair.  Returns the pointer Value, and
+//   stores the resulting IndexVector in argument chainIdxVec.
+//---------------------------------------------------------------------------
+
+Value*		FoldGetElemChain    (const InstructionNode* getElemInstrNode,
+				     vector<ConstPoolVal*>& chainIdxVec);
+
+
+//---------------------------------------------------------------------------
+// class TmpInstruction
+//
+//   This class represents temporary intermediate values
+//   used within the machine code for a VM instruction
+//---------------------------------------------------------------------------
+
+class TmpInstruction : public Instruction {
+  TmpInstruction (const TmpInstruction  &CI) : Instruction(CI.getType(), CI.getOpcode()) {
+    Operands.reserve(2);
+    Operands.push_back(Use(Operands[0], this));
+    Operands.push_back(Use(Operands[1], this));
+  }
+public:
+  TmpInstruction(OtherOps Opcode, Value *S1, Value* S2, const string &Name = "")
+    : Instruction(S1->getType(), Opcode, Name)
+  {
+    assert(Opcode == UserOp1 && "Tmp instruction opcode invalid!");
+    Operands.reserve(S2? 2 : 1);
+    Operands.push_back(Use(S1, this));
+    if (S2)
+      Operands.push_back(Use(S2, this));
+  }
+  
+  virtual Instruction *clone() const { return new TmpInstruction(*this); }
+  virtual const char *getOpcodeName() const {
+    return "userOp1";
+  }
+};
+
+//**************************************************************************/
+
+#endif
diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
new file mode 100644
index 0000000000..0421d8ca1a
--- /dev/null
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -0,0 +1,370 @@
+// $Id$ -*-c++-*-
+//***************************************************************************
+// File:
+//	MachineInstr.h
+// 
+// Purpose:
+//	
+// 
+// Strategy:
+// 
+// History:
+//	7/2/01	 -  Vikram Adve  -  Created
+//**************************************************************************/
+
+#ifndef LLVM_CODEGEN_MACHINEINSTR_H
+#define LLVM_CODEGEN_MACHINEINSTR_H
+
+//************************** System Include Files **************************/
+
+#include <string>
+#include <vector>
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Tools/DataTypes.h"
+#include "llvm/Instruction.h"
+#include "llvm/Support/Unique.h"
+#include "llvm/Codegen/TargetMachine.h"
+
+
+//************************* Opaque Declarations ****************************/
+
+class Value;
+class InstrTreeNode;
+class InstructionNode;
+class MachineInstr;
+class MachineInstrInfo;
+class MachineOperand;
+
+
+//************************ Exported Data Types *****************************/
+
+//---------------------------------------------------------------------------
+// class MachineOperand 
+// 
+// Purpose:
+//   Representation of each machine instruction operand.
+//   This class is designed so that you can allocate a vector of operands
+//   first and initialize each one later.
+//
+//   E.g, for this VM instruction:
+//		ptr = alloca type, numElements
+//   we generate 2 machine instructions on the SPARC:
+// 
+//		mul Constant, Numelements -> Reg
+//		add %sp, Reg -> Ptr
+// 
+//   Each instruction has 3 operands, listed above.  Of those:
+//   -	Reg, NumElements, and Ptr are of operand type MO_Register.
+//   -	Constant is of operand type MO_SignExtendedImmed on the SPARC.
+//	
+//   For the register operands, the virtual register type is as follows:
+//	
+//   -  Reg will be of virtual register type MO_MInstrVirtualReg.  The field
+//	MachineInstr* minstr will point to the instruction that computes reg.
+// 
+//   -	%sp will be of virtual register type MO_MachineReg.
+//	The field regNum identifies the machine register.
+// 
+//   -	NumElements will be of virtual register type MO_VirtualReg.
+//	The field Value* value identifies the value.
+// 
+//   -	Ptr will also be of virtual register type MO_VirtualReg.
+//	Again, the field Value* value identifies the value.
+// 
+//---------------------------------------------------------------------------
+
+class MachineOperand {
+public:
+  friend ostream& operator<<(ostream& os, const MachineOperand& mop);
+
+public:
+  enum MachineOperandType {
+    MO_Register,
+    MO_CCRegister,
+    MO_SignExtendedImmed,
+    MO_UnextendedImmed,
+    MO_PCRelativeDisp,
+  };
+  
+  enum VirtualRegisterType {
+    MO_VirtualReg,		// virtual register for *value
+    MO_MachineReg		// pre-assigned machine register `regNum'
+  };
+  
+  MachineOperandType machineOperandType;
+  
+  VirtualRegisterType vregType;
+  
+  Value*	value;		// BasicBlockVal for a label operand.
+				// ConstantVal for a non-address immediate.
+				// Virtual register for a register operand.
+  
+  unsigned int regNum;		// register number for an explicit register
+  
+  int64_t immedVal;		// constant value for an explicit constant
+  
+  /*ctor*/		MachineOperand	();
+  /*ctor*/		MachineOperand	(MachineOperandType operandType,
+					 Value* _val);
+  /*copy ctor*/		MachineOperand	(const MachineOperand&);
+  /*dtor*/		~MachineOperand	() {}
+  
+  // These functions are provided so that a vector of operands can be
+  // statically allocated and individual ones can be initialized later.
+  // 
+  void			Initialize	(MachineOperandType operandType,
+					 Value* _val);
+  void			InitializeConst	(MachineOperandType operandType,
+					 int64_t intValue);
+  void			InitializeReg	(unsigned int regNum);
+};
+
+
+inline
+MachineOperand::MachineOperand()
+  : machineOperandType(MO_Register),
+    vregType(MO_VirtualReg),
+    value(NULL),
+    regNum(0),
+    immedVal(0)
+{}
+
+inline
+MachineOperand::MachineOperand(MachineOperandType operandType,
+			       Value* _val)
+  : machineOperandType(operandType),
+    vregType(MO_VirtualReg),
+    value(_val),
+    regNum(0),
+    immedVal(0)
+{}
+
+inline
+MachineOperand::MachineOperand(const MachineOperand& mo)
+  : machineOperandType(mo.machineOperandType),
+    vregType(mo.vregType),
+    value(mo.value),
+    regNum(mo.regNum),
+    immedVal(mo.immedVal)
+{
+}
+
+inline void
+MachineOperand::Initialize(MachineOperandType operandType,
+			   Value* _val)
+{
+  machineOperandType = operandType;
+  value = _val;
+}
+
+inline void
+MachineOperand::InitializeConst(MachineOperandType operandType,
+				int64_t intValue)
+{
+  machineOperandType = operandType;
+  value = NULL;
+  immedVal = intValue;
+}
+
+inline void
+MachineOperand::InitializeReg(unsigned int _regNum)
+{
+  machineOperandType = MO_Register;
+  vregType = MO_MachineReg;
+  value = NULL;
+  regNum = _regNum;
+}
+
+
+//---------------------------------------------------------------------------
+// class MachineInstr 
+// 
+// Purpose:
+//   Representation of each machine instruction.
+// 
+//   MachineOpCode must be an enum, defined separately for each target.
+//   E.g., It is defined in SparcInstructionSelection.h for the SPARC.
+//   The array MachineInstrInfo TargetMachineInstrInfo[] objects
+//   (indexed by opCode) provides information about each target instruction.
+// 
+//   opCodeMask is used to record variants of an instruction.
+//   E.g., each branch instruction on SPARC has 2 flags (i.e., 4 variants):
+//	ANNUL:		   if 1: Annul delay slot instruction.
+//	PREDICT-NOT-TAKEN: if 1: predict branch not taken.
+//   Instead of creating 4 different opcodes for BNZ, we create a single
+//   opcode and set bits in opCodeMask for each of these flags.
+//---------------------------------------------------------------------------
+
+class MachineInstr : public Unique {
+private:
+  MachineOpCode	opCode;
+  OpCodeMask	opCodeMask;		// extra bits for variants of an opcode
+  vector<MachineOperand> operands;	// operand 0 is the result
+  
+public:
+  /*ctor*/		MachineInstr	(MachineOpCode _opCode,
+					 OpCodeMask    _opCodeMask = 0x0);
+  
+  /*dtor*/ virtual	~MachineInstr	();
+  
+  const MachineOpCode	getOpCode	() const;
+  
+  unsigned int		getNumOperands	() const;
+  
+  const MachineOperand& getOperand	(unsigned int i) const;
+  
+  void			dump		(unsigned int indent = 0);
+  
+public:
+  friend ostream& operator<<(ostream& os, const MachineInstr& minstr);
+
+public:
+  // Access to set the operands when building the machine instruction
+  void			SetMachineOperand(unsigned int i,
+			      MachineOperand::MachineOperandType operandType,
+			      Value* _val);
+  void			SetMachineOperand(unsigned int i,
+			      MachineOperand::MachineOperandType operandType,
+			      int64_t intValue);
+  void			SetMachineOperand(unsigned int i,
+					  unsigned int regNum);
+};
+
+inline const MachineOpCode
+MachineInstr::getOpCode() const
+{
+  return opCode;
+}
+
+inline unsigned int
+MachineInstr::getNumOperands() const
+{
+  assert(operands.size() == TargetMachineInstrInfo[opCode].numOperands);
+  return operands.size();
+}
+
+inline const MachineOperand&
+MachineInstr::getOperand(unsigned int i) const
+{
+  return operands[i];
+}
+
+
+//---------------------------------------------------------------------------
+// class MachineInstructionsForVMInstr
+// 
+// Purpose:
+//   Representation of the sequence of machine instructions created
+//   for a single VM instruction.  Additionally records any temporary 
+//   "values" used as intermediate values in this sequence.
+//   Note that such values should be treated as pure SSA values with
+//   no interpretation of their operands (i.e., as a TmpInstruction object
+//   which actually represents such a value).
+// 
+//---------------------------------------------------------------------------
+
+class MachineCodeForVMInstr: public vector<MachineInstr*>
+{
+private:
+  vector<Value*> tempVec;
+  
+public:
+  /*ctor*/	MachineCodeForVMInstr	()	{}
+  /*ctor*/	~MachineCodeForVMInstr	();
+  
+  const vector<Value*>&
+		getTempValues		() const { return tempVec; }
+  
+  void		addTempValue		(Value* val)
+						 { tempVec.push_back(val); }
+
+  // dropAllReferences() - This function drops all references within
+  // temporary (hidden) instructions created in implementing the original
+  // VM intruction.  This ensures there are no remaining "uses" within
+  // these hidden instructions, before the values of a method are freed.
+  //
+  // Make this inline because it has to be called from class Instruction
+  // and inlining it avoids a serious circurality in link order.
+  inline void dropAllReferences() {
+    for (unsigned i=0, N=tempVec.size(); i < N; i++)
+    if (tempVec[i]->getValueType() == Value::InstructionVal)
+      ((Instruction*) tempVec[i])->dropAllReferences();
+  }
+};
+
+inline
+MachineCodeForVMInstr::~MachineCodeForVMInstr()
+{
+  // Free the Value objects created to hold intermediate values
+  for (unsigned i=0, N=tempVec.size(); i < N; i++)
+    delete tempVec[i];
+  
+  // Free the MachineInstr objects allocated, if any.
+  for (unsigned i=0, N=this->size(); i < N; i++)
+    delete (*this)[i];
+}
+
+//---------------------------------------------------------------------------
+// Target-independent utility routines for creating machine instructions
+//---------------------------------------------------------------------------
+
+
+//------------------------------------------------------------------------ 
+// Function Set2OperandsFromInstr
+// Function Set3OperandsFromInstr
+// 
+// For the common case of 2- and 3-operand arithmetic/logical instructions,
+// set the m/c instr. operands directly from the VM instruction's operands.
+// Check whether the first or second operand is 0 and can use a dedicated
+// "0" register.
+// Check whether the second operand should use an immediate field or register.
+// (First and third operands are never immediates for such instructions.)
+// 
+// Arguments:
+// canDiscardResult: Specifies that the result operand can be discarded
+//		     by using the dedicated "0"
+// 
+// op1position, op2position and resultPosition: Specify in which position
+//		     in the machine instruction the 3 operands (arg1, arg2
+//		     and result) should go.
+// 
+// RETURN VALUE: unsigned int flags, where
+//	flags & 0x01	=> operand 1 is constant and needs a register
+//	flags & 0x02	=> operand 2 is constant and needs a register
+//------------------------------------------------------------------------ 
+
+void		Set2OperandsFromInstr	(MachineInstr* minstr,
+					 InstructionNode* vmInstrNode,
+					 const TargetMachine& targetMachine,
+					 bool canDiscardResult = false,
+					 int op1Position = 0,
+					 int resultPosition = 1);
+
+void		Set3OperandsFromInstr	(MachineInstr* minstr,
+					 InstructionNode* vmInstrNode,
+					 const TargetMachine& targetMachine,
+					 bool canDiscardResult = false,
+					 int op1Position = 0,
+					 int op2Position = 1,
+					 int resultPosition = 2);
+
+MachineOperand::MachineOperandType
+		ChooseRegOrImmed(Value* val,
+			     MachineOpCode opCode,
+			     const TargetMachine& targetMachine,
+			     bool canUseImmed,
+			     MachineOperand::VirtualRegisterType& getVRegType,
+			     unsigned int& getMachineRegNum,
+			     int64_t& getImmedValue);
+
+ostream& operator<<(ostream& os, const MachineInstr& minstr);
+
+
+ostream& operator<<(ostream& os, const MachineOperand& mop);
+					 
+
+//**************************************************************************/
+
+#endif
diff --git a/include/llvm/CodeGen/Sparc.h b/include/llvm/CodeGen/Sparc.h
new file mode 100644
index 0000000000..8c3fbffbf4
--- /dev/null
+++ b/include/llvm/CodeGen/Sparc.h
@@ -0,0 +1,421 @@
+// $Id$ -*-c++-*-
+//***************************************************************************
+// File:
+//	Sparc.cpp
+// 
+// Purpose:
+//	
+// History:
+//	7/15/01	 -  Vikram Adve  -  Created
+//**************************************************************************/
+
+#ifndef LLVM_CODEGEN_SPARC_H
+#define LLVM_CODEGEN_SPARC_H
+
+//************************** System Include Files **************************/
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Codegen/TargetMachine.h"
+#include "llvm/Codegen/MachineInstr.h"
+
+
+//************************* Opaque Declarations ****************************/
+
+
+//************************ Exported Constants ******************************/
+
+
+// OpCodeMask definitions for the Sparc V9
+// 
+const OpCodeMask	Immed		= 0x00002000; // immed or reg operand?
+const OpCodeMask	Annul		= 0x20000000; // annul delay instr?
+const OpCodeMask	PredictTaken	= 0x00080000; // predict branch taken?
+
+
+//************************ Exported Data Types *****************************/
+
+
+//---------------------------------------------------------------------------
+// class UltraSparcMachine 
+// 
+// Purpose:
+//   Machine description.
+// 
+//---------------------------------------------------------------------------
+
+class UltraSparc: public TargetMachine {
+public:
+  /*ctor*/		UltraSparc	();
+  /*dtor*/ virtual	~UltraSparc	() {}
+};
+
+
+//---------------------------------------------------------------------------
+// enum SparcMachineOpCode. 
+// const MachineInstrInfo SparcMachineInstrInfo[].
+// 
+// Purpose:
+//   Description of UltraSparc machine instructions.
+// 
+//---------------------------------------------------------------------------
+
+
+enum SparcMachineOpCode {
+
+  NOP,
+  
+  // Synthetic SPARC assembly opcodes for setting a register to a constant
+  SETSW,
+  SETUW,
+  
+  // Add or add with carry.
+  // Immed bit specifies if second operand is immediate(1) or register(0)
+  ADD,
+  ADDcc,
+  ADDC,
+  ADDCcc,
+
+  // Subtract or subtract with carry.
+  // Immed bit specifies if second operand is immediate(1) or register(0)
+  SUB,
+  SUBcc,
+  SUBC,
+  SUBCcc,
+  
+  // Integer multiply, signed divide, unsigned divide.
+  // Note that the deprecated 32-bit multiply and multiply-step are not used.
+  MULX,
+  SDIVX,
+  UDIVX,
+  
+  // Floating point add, subtract, compare
+  FADDS,
+  FADDD,
+  FADDQ,
+  FSUBS,
+  FSUBD,
+  FSUBQ,
+  FCMPS,
+  FCMPD,
+  FCMPQ,
+  // NOTE: FCMPE{S,D,Q}: FP Compare With Exception are currently unused!
+  
+  // Floating point multiply or divide.
+  FMULS,
+  FMULD,
+  FMULQ,
+  FSMULD,
+  FDMULQ,
+  FDIVS,
+  FDIVD,
+  FDIVQ,
+  
+  // Logical operations
+  AND,
+  ANDcc,
+  ANDN,
+  ANDNcc,
+  OR,
+  ORcc,
+  ORN,
+  ORNcc,
+  XOR,
+  XORcc,
+  XNOR,
+  XNORcc,
+  
+  // Shift operations
+  SLL,
+  SRL,
+  SRA,
+  SLLX,
+  SRLX,
+  SRAX,
+  
+  // Convert from floating point to floating point formats
+  FSTOD,
+  FSTOQ,
+  FDTOS,
+  FDTOQ,
+  FQTOS,
+  FQTOD,
+  
+  // Convert from floating point to integer formats
+  FSTOX,
+  FDTOX,
+  FQTOX,
+  FSTOI,
+  FDTOI,
+  FQTOI,
+  
+  // Convert from integer to floating point formats
+  FXTOS,
+  FXTOD,
+  FXTOQ,
+  FITOS,
+  FITOD,
+  FITOQ,
+  
+  // Branch on integer comparison with zero.
+  // Annul bit specifies if intruction in delay slot is annulled(1) or not(0).
+  // PredictTaken bit hints if branch should be predicted taken(1) or not(0).
+  BRZ,
+  BRLEZ,
+  BRLZ,
+  BRNZ,
+  BRGZ,
+  BRGEZ,
+
+  // Branch on integer condition code.
+  // Annul bit specifies if intruction in delay slot is annulled(1) or not(0).
+  // PredictTaken bit hints if branch should be predicted taken(1) or not(0).
+  BA,
+  BN,
+  BNE,
+  BE,
+  BG,
+  BLE,
+  BGE,
+  BL,
+  BGU,
+  BLEU,
+  BCC,
+  BCS,
+  BPOS,
+  BNEG,
+  BVC,
+  BVS,
+
+  // Branch on floating point condition code.
+  // Annul bit specifies if intruction in delay slot is annulled(1) or not(0).
+  // PredictTaken bit hints if branch should be predicted taken(1) or not(0).
+  FBA,
+  FBN,
+  FBU,
+  FBG,
+  FBUG,
+  FBL,
+  FBUL,
+  FBLG,
+  FBNE,
+  FBE,
+  FBUE,
+  FBGE,
+  FBUGE,
+  FBLE,
+  FBULE,
+  FBO,
+
+  // Load integer instructions
+  LDSB,
+  LDSH,
+  LDSW,
+  LDUB,
+  LDUH,
+  LDUW,
+  LDX,
+  
+  // Load floating-point instructions
+  LD,
+  LDD,			// use of this for integers is deprecated for Sparc V9
+  LDQ,
+  
+  // Store integer instructions
+  STB,
+  STH,
+  STW,
+  STX,
+  
+  // Store floating-point instructions
+  ST,
+  STD,
+  
+  // Call, Return, and "Jump and link"
+  // Immed bit specifies if second operand is immediate(1) or register(0)
+  CALL,
+  JMPL,
+  RETURN,
+
+  // End-of-array marker
+  INVALID_OPCODE
+};
+
+const MachineInstrInfo SparcMachineInstrInfo[] = {
+  
+  { "NOP",	0,  -1,  0,  false },
+  
+  // Synthetic SPARC assembly opcodes for setting a register to a constant
+  { "SETSW",	2,  1,  0, true },	// max immediate constant is ignored
+  { "SETUW",	2,  1,  0, false },	// max immediate constant is ignored
+  
+  // Add or add with carry.
+  { "ADD",	3,  2,  (1 << 12) - 1,  true },
+  { "ADDcc",	3,  2,  (1 << 12) - 1,  true },
+  { "ADDC",	3,  2,  (1 << 12) - 1,  true },
+  { "ADDCcc",	3,  2,  (1 << 12) - 1,  true },
+
+  // Sub tract or subtract with carry.
+  { "SUB",	3,  2,  (1 << 12) - 1,  true },
+  { "SUBcc",	3,  2,  (1 << 12) - 1,  true },
+  { "SUBC",	3,  2,  (1 << 12) - 1,  true },
+  { "SUBCcc",	3,  2,  (1 << 12) - 1,  true },
+
+  // Integer multiply, signed divide, unsigned divide.
+  // Note that the deprecated 32-bit multiply and multiply-step are not used.
+  { "MULX",	3,  2,  (1 << 12) - 1,  true },
+  { "SDIVX",	3,  2,  (1 << 12) - 1,  true },
+  { "UDIVX",	3,  2,  (1 << 12) - 1,  true },
+  
+  // Floating point add, subtract, compare
+  { "FADDS",	3,  2,  0,  false },
+  { "FADDD",	3,  2,  0,  false },
+  { "FADDQ",	3,  2,  0,  false },
+  { "FSUBS",	3,  2,  0,  false },
+  { "FSUBD",	3,  2,  0,  false },
+  { "FSUBQ",	3,  2,  0,  false },
+  { "FCMPS",	3,  2,  0,  false },
+  { "FCMPD",	3,  2,  0,  false },
+  { "FCMPQ",	3,  2,  0,  false },
+  // NOTE: FCMPE{S,D,Q}: FP Compare With Exception are currently unused!
+  
+  // Floating point multiply or divide.
+  { "FMULS",	3,  2,  0,  false },
+  { "FMULD",	3,  2,  0,  false },
+  { "FMULQ",	3,  2,  0,  false },
+  { "FSMULD",	3,  2,  0,  false },
+  { "FDMULQ",	3,  2,  0,  false },
+  { "FDIVS",	3,  2,  0,  false },
+  { "FDIVD",	3,  2,  0,  false },
+  { "FDIVQ",	3,  2,  0,  false },
+  
+  // Logical operations
+  { "AND",	3,  2,  (1 << 12) - 1,  true },
+  { "ANDcc",	3,  2,  (1 << 12) - 1,  true },
+  { "ANDN",	3,  2,  (1 << 12) - 1,  true },
+  { "ANDNcc",	3,  2,  (1 << 12) - 1,  true },
+  { "OR",	3,  2,  (1 << 12) - 1,  true },
+  { "ORcc",	3,  2,  (1 << 12) - 1,  true },
+  { "ORN",	3,  2,  (1 << 12) - 1,  true },
+  { "ORNcc",	3,  2,  (1 << 12) - 1,  true },
+  { "XOR",	3,  2,  (1 << 12) - 1,  true },
+  { "XORcc",	3,  2,  (1 << 12) - 1,  true },
+  { "XNOR",	3,  2,  (1 << 12) - 1,  true },
+  { "XNORcc",	3,  2,  (1 << 12) - 1,  true },
+  
+  // Shift operations
+  { "SLL",	3,  2,  (1 << 5) - 1,  true },
+  { "SRL",	3,  2,  (1 << 5) - 1,  true },
+  { "SRA",	3,  2,  (1 << 5) - 1,  true },
+  { "SLLX",	3,  2,  (1 << 6) - 1,  true },
+  { "SRLX",	3,  2,  (1 << 6) - 1,  true },
+  { "SRAX",	3,  2,  (1 << 6) - 1,  true },
+  
+  // Convert from floating point to floating point formats
+  { "FSTOD",	2,  1,  0,  false },
+  { "FSTOQ",	2,  1,  0,  false },
+  { "FDTOS",	2,  1,  0,  false },
+  { "FDTOQ",	2,  1,  0,  false },
+  { "FQTOS",	2,  1,  0,  false },
+  { "FQTOD",	2,  1,  0,  false },
+  
+  // Convert from floating point to integer formats
+  { "FSTOX",	2,  1,  0,  false },
+  { "FDTOX",	2,  1,  0,  false },
+  { "FQTOX",	2,  1,  0,  false },
+  { "FSTOI",	2,  1,  0,  false },
+  { "FDTOI",	2,  1,  0,  false },
+  { "FQTOI",	2,  1,  0,  false },
+  
+  // Convert from integer to floating point formats
+  { "FXTOS",	2,  1,  0,  false },
+  { "FXTOD",	2,  1,  0,  false },
+  { "FXTOQ",	2,  1,  0,  false },
+  { "FITOS",	2,  1,  0,  false },
+  { "FITOD",	2,  1,  0,  false },
+  { "FITOQ",	2,  1,  0,  false },
+  
+  // Branch on integer comparison with zero.
+  { "BRZ",	2,  -1,  (1 << 15) - 1,  true },
+  { "BRLEZ",	2,  -1,  (1 << 15) - 1,  true },
+  { "BRLZ",	2,  -1,  (1 << 15) - 1,  true },
+  { "BRNZ",	2,  -1,  (1 << 15) - 1,  true },
+  { "BRGZ",	2,  -1,  (1 << 15) - 1,  true },
+  { "BRGEZ",	2,  -1,  (1 << 15) - 1,  true },
+
+  // Branch on condition code.
+  { "BA",	1,  -1,  (1 << 21) - 1,  true },
+  { "BN",	1,  -1,  (1 << 21) - 1,  true },
+  { "BNE",	1,  -1,  (1 << 21) - 1,  true },
+  { "BE",	1,  -1,  (1 << 21) - 1,  true },
+  { "BG",	1,  -1,  (1 << 21) - 1,  true },
+  { "BLE",	1,  -1,  (1 << 21) - 1,  true },
+  { "BGE",	1,  -1,  (1 << 21) - 1,  true },
+  { "BL",	1,  -1,  (1 << 21) - 1,  true },
+  { "BGU",	1,  -1,  (1 << 21) - 1,  true },
+  { "BLEU",	1,  -1,  (1 << 21) - 1,  true },
+  { "BCC",	1,  -1,  (1 << 21) - 1,  true },
+  { "BCS",	1,  -1,  (1 << 21) - 1,  true },
+  { "BPOS",	1,  -1,  (1 << 21) - 1,  true },
+  { "BNEG",	1,  -1,  (1 << 21) - 1,  true },
+  { "BVC",	1,  -1,  (1 << 21) - 1,  true },
+  { "BVS",	1,  -1,  (1 << 21) - 1,  true },
+
+  // Branch on floating point condition code.
+  // Annul bit specifies if intruction in delay slot is annulled(1) or not(0).
+  // PredictTaken bit hints if branch should be predicted taken(1) or not(0).
+  // The first argument is the FCCn register (0 <= n <= 3).
+  { "FBA",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBN",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBU",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBG",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBUG",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBL",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBUL",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBLG",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBNE",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBE",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBUE",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBGE",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBUGE",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBLE",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBULE",	2,  -1,  (1 << 18) - 1,  true },
+  { "FBO",	2,  -1,  (1 << 18) - 1,  true },
+
+  // Load integer instructions
+  { "LDSB",	3,  2,  (1 << 12) - 1,  true },
+  { "LDSH",	3,  2,  (1 << 12) - 1,  true },
+  { "LDSW",	3,  2,  (1 << 12) - 1,  true },
+  { "LDUB",	3,  2,  (1 << 12) - 1,  true },
+  { "LDUH",	3,  2,  (1 << 12) - 1,  true },
+  { "LDUW",	3,  2,  (1 << 12) - 1,  true },
+  { "LDX",	3,  2,  (1 << 12) - 1,  true },
+  
+  // Load floating-point instructions
+  { "LD",	3,  2,  (1 << 12) - 1,  true },
+  { "LDD",	3,  2,  (1 << 12) - 1,  true },
+  { "LDQ",	3,  2,  (1 << 12) - 1,  true },
+  
+  // Store integer instructions
+  { "STB",	3,  -1,  (1 << 12) - 1,  true },
+  { "STH",	3,  -1,  (1 << 12) - 1,  true },
+  { "STW",	3,  -1,  (1 << 12) - 1,  true },
+  { "STX",	3,  -1,  (1 << 12) - 1,  true },
+  
+  // Store floating-point instructions
+  { "ST",	3,  -1,  (1 << 12) - 1,  true },
+  { "STD",	3,  -1,  (1 << 12) - 1,  true },
+  
+  // Call, Return and "Jump and link"
+  { "CALL",	1,  -1,  (1 << 29) - 1,  true },
+  { "JMPL",	3,  -1,  (1 << 12) - 1,  true },	
+  { "RETURN",	2,  -1,  0,  false },
+  
+  // End-of-array marker
+  { "INVALID_SPARC_OPCODE",	0,  -1,  0,  false }
+};
+
+
+/***************************************************************************/
+
+#endif
diff --git a/include/llvm/CodeGen/TargetMachine.h b/include/llvm/CodeGen/TargetMachine.h
new file mode 100644
index 0000000000..72545f88e9
--- /dev/null
+++ b/include/llvm/CodeGen/TargetMachine.h
@@ -0,0 +1,111 @@
+// $Id$ -*-c++-*-
+//***************************************************************************
+// File:
+//	TargetMachine.h
+// 
+// Purpose:
+//	
+// History:
+//	7/12/01	 -  Vikram Adve  -  Created
+//**************************************************************************/
+
+#ifndef LLVM_CODEGEN_TARGETMACHINE_H
+#define LLVM_CODEGEN_TARGETMACHINE_H
+
+//************************** System Include Files **************************/
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Support/Unique.h"
+#include "llvm/Tools/DataTypes.h"
+
+//************************* Opaque Declarations ****************************/
+
+class Type;
+class StructType;
+class MachineInstrInfo;
+
+
+//************************ Exported Data Types *****************************/
+
+
+//---------------------------------------------------------------------------
+// Data types used to define information about a single machine instruction
+//---------------------------------------------------------------------------
+
+typedef int MachineOpCode;
+typedef int OpCodeMask;
+
+
+// struct MachineInstrInfo:
+//	Predefined information about each machine instruction.
+// 
+struct MachineInstrInfo {
+  string	opCodeString;	// Assembly language mnemonic for the opcode.
+  unsigned int	numOperands;	// Number of arguments for the instruction.
+  int		resultPos;	// Position of the result; -1 if no result
+  unsigned int	maxImmedConst;	// Largest +ve constant in IMMMED field or 0.
+  bool    immedIsSignExtended;	// Is the IMMED field sign-extended? If so,
+				//   smallest -ve value is -(maxImmedConst+1).
+  
+  
+  // Check if the specified constant fits in the immediate field
+  // of this machine instruction
+  // 
+  bool	constantFitsInImmedField	(int64_t intValue) const;
+  
+  // Return the largest +ve constant that can be held in the IMMMED field
+  // of this machine instruction.
+  // isSignExtended is set to true if the value is sign-extended before use
+  // (this is true for all immediate fields in SPARC instructions).
+  // Return 0 if the instruction has no IMMED field.
+  // 
+  inline uint64_t	maxImmedConstant(bool& isSignExtended) const {
+				isSignExtended = immedIsSignExtended;
+				return maxImmedConst; }
+};
+
+// Global variable holding an array of the above structures.
+// This needs to be defined separately for each target machine.
+// 
+extern const MachineInstrInfo* TargetMachineInstrInfo;
+
+
+//---------------------------------------------------------------------------
+// class TargetMachine
+// 
+// Purpose:
+//   Machine description.
+// 
+//---------------------------------------------------------------------------
+
+class TargetMachine: public Unique {
+public:
+  int		optSizeForSubWordData;
+  int		intSize;
+  int		longSize;
+  int		floatSize;
+  int		doubleSize;
+  int		longDoubleSize;
+  int		pointerSize;
+  int		minMemOpWordSize;
+  int		maxAtomicMemOpWordSize;
+  
+  // Description of machine instructions (array indexed by machine opcode)
+  const MachineInstrInfo* machineInstrInfo;
+  
+  // Register information.  This needs to be reorganized into a single class.
+  int		zeroRegNum;	// register that gives 0 if any (-1 if none)
+  
+public:
+  /*ctor*/		TargetMachine		() {}
+  /*dtor*/ virtual	~TargetMachine		() {}
+  
+  virtual unsigned int	findOptimalStorageSize	(const Type* ty) const;
+  
+  virtual unsigned int*	findOptimalMemberOffsets(const StructType* stype)const;
+};
+
+//**************************************************************************/
+
+#endif