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

1 files changed, 339 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 */