aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/CodeGen/InstrForest.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/CodeGen/InstrForest.h')
-rw-r--r--include/llvm/CodeGen/InstrForest.h339
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 */
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-16 05:01:43 +0000