Eliminate 'BasicNode' from InstrForest.
authorChris Lattner <sabre@nondot.org>
Tue, 11 Sep 2001 23:52:11 +0000 (23:52 +0000)
committerChris Lattner <sabre@nondot.org>
Tue, 11 Sep 2001 23:52:11 +0000 (23:52 +0000)
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@551 91177308-0d34-0410-b5e6-96231b3b80d8

include/llvm/CodeGen/InstrForest.h
lib/CodeGen/InstrSelection/InstrForest.cpp
lib/CodeGen/InstrSelection/InstrSelection.cpp
lib/CodeGen/TargetMachine/Sparc/Sparc.burg
lib/CodeGen/TargetMachine/Sparc/SparcInstrSelection.cpp
lib/Target/SparcV9/InstrSelection/InstrForest.cpp
lib/Target/SparcV9/InstrSelection/InstrSelection.cpp

index 382a72ee11da23997207adb79fa609fc4976f82e..403a27ac8a46a191a8619baf412ae8be9c4fe673 100644 (file)
@@ -78,36 +78,26 @@ const int  ToPointerTy      = ToBoolTy + 12;
 typedef int OpLabel;
 typedef int StateLabel;
 
-struct BasicTreeNode {
-  BasicTreeNode* leftChild;
-  BasicTreeNode* rightChild;
-  BasicTreeNode* parent;
-  OpLabel        opLabel;
-  StateLabel     state;
-  InstrTreeNode *treeNodePtr;  // points to the C++ tree node object
-                                // that "contains" this node
-};
-
 //-------------------------------------------------------------------------
 // Declarations of data and functions created by BURG
 //-------------------------------------------------------------------------
 
 extern short*          burm_nts[];
   
-extern StateLabel      burm_label      (BasicTreeNode* p);
+extern StateLabel      burm_label      (InstrTreeNode* p);
   
 extern StateLabel      burm_state      (OpLabel op, StateLabel leftState,
                                         StateLabel rightState);
 
 extern StateLabel      burm_rule       (StateLabel state, int goalNT);
   
-extern BasicTreeNode**  burm_kids      (BasicTreeNode* p, int eruleno,
-                                        BasicTreeNode* kids[]);
+extern InstrTreeNode**  burm_kids      (InstrTreeNode* p, int eruleno,
+                                        InstrTreeNode* kids[]);
   
-extern void            printcover      (BasicTreeNode*, int, int);
-extern void            printtree       (BasicTreeNode*);
-extern int             treecost        (BasicTreeNode*, int, int);
-extern void            printMatches    (BasicTreeNode*);
+extern void            printcover      (InstrTreeNode*, int, int);
+extern void            printtree       (InstrTreeNode*);
+extern int             treecost        (InstrTreeNode*, int, int);
+extern void            printMatches    (InstrTreeNode*);
 
 
 //------------------------------------------------------------------------ 
@@ -125,8 +115,15 @@ public:
                           NTConstNode,
                           NTLabelNode };
   
+  // BASIC TREE NODE START
+  InstrTreeNode* LeftChild;
+  InstrTreeNode* RightChild;
+  InstrTreeNode* Parent;
+  OpLabel        opLabel;
+  StateLabel     state;
+  // BASIC TREE NODE END
+
 protected:
-  BasicTreeNode    basicNode;
   InstrTreeNodeType treeNodeType;
   Value*          val;
   
@@ -135,30 +132,25 @@ public:
                                         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 OpLabel       getOpLabel      () const { return opLabel; }
   
   inline InstrTreeNode*        leftChild       () const {
-    return (basicNode.leftChild? basicNode.leftChild->treeNodePtr : NULL);
+    return LeftChild;
   }
   
   // If right child is a list node, recursively get its *left* child
-  inline InstrTreeNode* rightChild     () const {
-    return (InstrTreeNode*)
-      (basicNode.rightChild
-       ? (basicNode.rightChild->treeNodePtr->getOpLabel() == VRegListOp
-         ? basicNode.rightChild->treeNodePtr->leftChild()
-         : basicNode.rightChild->treeNodePtr)
-       : NULL);
+  inline InstrTreeNode* rightChild() const {
+    return (!RightChild ? 0 : 
+           (RightChild->getOpLabel() == VRegListOp
+            ? RightChild->LeftChild : RightChild));
   }
   
-  inline InstrTreeNode*        parent          () const {
-    return (basicNode.parent? basicNode.parent->treeNodePtr : NULL);
+  inline InstrTreeNode *parent() const {
+    return Parent;
   }
   
   void                 dump            (int dumpChildren,
index 181c1a1d43f33682f57cca2d6a48de46c9f248b3..1ff4c881f7366e36a3ed705486fdfd98825344fa 100644 (file)
 //------------------------------------------------------------------------ 
 
 
-InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType,
-                            Value* _val)
-  : treeNodeType(nodeType),
-    val(_val)
-{
-  basicNode.leftChild = NULL;
-  basicNode.rightChild = NULL;
-  basicNode.parent = NULL;
-  basicNode.opLabel = InvalidOp;
-  basicNode.treeNodePtr = this;
+InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType, Value* _val)
+  : treeNodeType(nodeType), val(_val) {
+  LeftChild   = 0;
+  RightChild  = 0;
+  Parent      = 0;
+  opLabel     = InvalidOp;
 }
 
-void
-InstrTreeNode::dump(int dumpChildren,
-                   int indent) const
-{
-  this->dumpNode(indent);
+void InstrTreeNode::dump(int dumpChildren, int indent) const {
+  dumpNode(indent);
   
   if (dumpChildren)
     {
@@ -122,7 +115,7 @@ InstructionNode::InstructionNode(Instruction* _instr)
        }
     }
   
-  basicNode.opLabel = opLabel;
+  this->opLabel = opLabel;
 }
 
 
@@ -148,10 +141,8 @@ InstructionNode::dumpNode(int indent) const
 }
 
 
-VRegListNode::VRegListNode()
-  : InstrTreeNode(NTVRegListNode, NULL)
-{
-  basicNode.opLabel = VRegListOp;
+VRegListNode::VRegListNode() : InstrTreeNode(NTVRegListNode, 0) {
+  opLabel = VRegListOp;
 }
 
 void
@@ -164,10 +155,8 @@ VRegListNode::dumpNode(int indent) const
 }
 
 
-VRegNode::VRegNode(Value* _val)
-  : InstrTreeNode(NTVRegNode, _val)
-{
-  basicNode.opLabel = VRegNodeOp;
+VRegNode::VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) {
+  opLabel = VRegNodeOp;
 }
 
 void
@@ -181,10 +170,9 @@ VRegNode::dumpNode(int indent) const
 }
 
 
-ConstantNode::ConstantNode(ConstPoolVal* constVal)
-  : InstrTreeNode(NTConstNode, constVal)
-{
-  basicNode.opLabel = ConstantNodeOp;
+ConstantNode::ConstantNode(ConstPoolVal *constVal)
+  : InstrTreeNode(NTConstNode, constVal) {
+  opLabel = ConstantNodeOp;
 }
 
 void
@@ -198,10 +186,8 @@ ConstantNode::dumpNode(int indent) const
 }
 
 
-LabelNode::LabelNode(BasicBlock* _bblock)
-  : InstrTreeNode(NTLabelNode, _bblock)
-{
-  basicNode.opLabel = LabelNodeOp;
+LabelNode::LabelNode(BasicBlock *BB) : InstrTreeNode(NTLabelNode, BB) {
+  opLabel = LabelNodeOp;
 }
 
 void
@@ -255,10 +241,9 @@ InstrForest::noteTreeNodeForInstr(Instruction* instr,
 
 
 inline void
-InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child)
-{
-  parent->basicNode.leftChild = & child->basicNode;
-  child->basicNode.parent = & parent->basicNode;
+InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child) {
+  parent->LeftChild = child;
+  child->Parent = parent;
   if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
     treeRoots.erase((InstructionNode*) child); // no longer a tree root
 }
@@ -267,8 +252,8 @@ InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child)
 inline void
 InstrForest::setRightChild(InstrTreeNode* parent, InstrTreeNode* child)
 {
-  parent->basicNode.rightChild = & child->basicNode;
-  child->basicNode.parent = & parent->basicNode;
+  parent->RightChild = child;
+  child->Parent = parent;
   if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
     treeRoots.erase((InstructionNode*) child); // no longer a tree root
 }
index e6884ab572a6b62514e0221f58211e7298c8c543..675e489e46071829866fb9b962fd3c20d1691c21 100644 (file)
 //**************************************************************************/
 
 
-//************************** System Include Files ***************************/
-
-
-//*************************** User Include Files ***************************/
-
 #include "llvm/CodeGen/InstrSelection.h"
+#include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Type.h"
 #include "llvm/iMemory.h"
 #include "llvm/Instruction.h"
 #include "llvm/BasicBlock.h"
 #include "llvm/Method.h"
-#include "llvm/CodeGen/MachineInstr.h"
 
-
-//************************* Forward Declarations ***************************/
-
-static bool SelectInstructionsForTree(BasicTreeNode* treeRoot,
-                                     int goalnt,
+static bool SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
                                      TargetMachine &Target);
 
 
-//************************* Internal Data Types *****************************/
-
 enum SelectDebugLevel_t {
   Select_NoDebugInfo,
   Select_PrintMachineCode, 
@@ -50,8 +39,6 @@ cl::Enum<enum SelectDebugLevel_t> SelectDebugLevel("dselect", cl::NoFlags, // cl
    clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"), 0);
 
 
-//************************** External Functions ****************************/
-
 
 //---------------------------------------------------------------------------
 // Entry point for instruction selection using BURG.
@@ -87,7 +74,7 @@ SelectInstructionsForMethod(Method* method,
        treeRootIter != treeRoots.end();
        ++treeRootIter)
     {
-      BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode();
+      InstrTreeNode* basicNode = *treeRootIter;
       
       // Invoke BURM to label each tree node with a state
       (void) burm_label(basicNode);
@@ -192,8 +179,7 @@ FoldGetElemChain(const InstructionNode* getElemInstrNode,
 //---------------------------------------------------------------------------
 
 bool
-SelectInstructionsForTree(BasicTreeNode* treeRoot,
-                         int goalnt,
+SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
                          TargetMachine &Target)
 {
   // Use a static vector to avoid allocating a new one per VM instruction
@@ -220,7 +206,7 @@ SelectInstructionsForTree(BasicTreeNode* treeRoot,
   // 
   if (treeRoot->opLabel != VRegListOp)
     {
-      InstructionNode* instrNode = (InstructionNode*)treeRoot->treeNodePtr;
+      InstructionNode* instrNode = (InstructionNode*)treeRoot;
       assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
       
       unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target,
@@ -238,7 +224,7 @@ SelectInstructionsForTree(BasicTreeNode* treeRoot,
   if (nts[0])
     { // i.e., there is at least one kid
 
-      BasicTreeNode* kids[2];
+      InstrTreeNode* kids[2];
       int currentRule = ruleForNode;
       burm_kids(treeRoot, currentRule, kids);
       
@@ -258,8 +244,7 @@ SelectInstructionsForTree(BasicTreeNode* treeRoot,
       for (int i = 0; nts[i]; i++)
        {
          assert(i < 2);
-         InstrTreeNode::InstrTreeNodeType
-           nodeType = kids[i]->treeNodePtr->getNodeType();
+         InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
          if (nodeType == InstrTreeNode::NTVRegListNode ||
              nodeType == InstrTreeNode::NTInstructionNode)
            {
index b211b54ee814cbe89f5d6ea5b7704f5cd10b6bc8..a40a9bb1fb86d1b533e4b22ef378991183d3d309 100644 (file)
@@ -2,10 +2,10 @@
 #include <stdio.h>
 #include <llvm/CodeGen/InstrForest.h>
 
-typedef BasicTreeNode* NODEPTR_TYPE;
+typedef InstrTreeNode* NODEPTR_TYPE;
 #define OP_LABEL(p)    ((p)->opLabel)
-#define LEFT_CHILD(p)  ((p)->leftChild)
-#define RIGHT_CHILD(p) ((p)->rightChild)
+#define LEFT_CHILD(p)  ((p)->LeftChild)
+#define RIGHT_CHILD(p) ((p)->RightChild)
 #define STATE_LABEL(p) ((p)->state)
 #define PANIC          printf
 %}
index 492a52f623711b7195573cf8e2b40578989d177e..ca2bca65847594ec9b462fd1837aa0b8979ab089 100644 (file)
@@ -9,23 +9,18 @@
 //     7/02/01  -  Vikram Adve  -  Created
 //**************************************************************************/
 
+#include "llvm/CodeGen/Sparc.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/InstrForest.h"
+#include "llvm/CodeGen/InstrSelection.h"
 #include "llvm/Support/MathExtras.h"
-#include "llvm/Type.h"
 #include "llvm/DerivedTypes.h"
-#include "llvm/SymbolTable.h"
-#include "llvm/Value.h"
-#include "llvm/Instruction.h"
-#include "llvm/InstrTypes.h"
 #include "llvm/iTerminators.h"
 #include "llvm/iMemory.h"
 #include "llvm/iOther.h"
 #include "llvm/BasicBlock.h"
 #include "llvm/Method.h"
 #include "llvm/ConstPoolVals.h"
-#include "llvm/CodeGen/Sparc.h"
-#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/CodeGen/InstrForest.h"
-#include "llvm/CodeGen/InstrSelection.h"
 
 
 //******************** Internal Data Declarations ************************/
@@ -1982,7 +1977,7 @@ GetInstructionsByRule(InstructionNode* subtreeRoot,
     assert(ThisIsAChainRule(ruleForNode));
     assert(nts[0] && ! nts[1]
           && "A chain rule should have only one RHS non-terminal!");
-    nextRule = burm_rule(subtreeRoot->getBasicNode()->state, nts[0]);
+    nextRule = burm_rule(subtreeRoot->state, nts[0]);
     nts = burm_nts[nextRule];
     numInstr = GetInstructionsByRule(subtreeRoot, nextRule, nts,target,mvec);
     break;
index 181c1a1d43f33682f57cca2d6a48de46c9f248b3..1ff4c881f7366e36a3ed705486fdfd98825344fa 100644 (file)
 //------------------------------------------------------------------------ 
 
 
-InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType,
-                            Value* _val)
-  : treeNodeType(nodeType),
-    val(_val)
-{
-  basicNode.leftChild = NULL;
-  basicNode.rightChild = NULL;
-  basicNode.parent = NULL;
-  basicNode.opLabel = InvalidOp;
-  basicNode.treeNodePtr = this;
+InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType, Value* _val)
+  : treeNodeType(nodeType), val(_val) {
+  LeftChild   = 0;
+  RightChild  = 0;
+  Parent      = 0;
+  opLabel     = InvalidOp;
 }
 
-void
-InstrTreeNode::dump(int dumpChildren,
-                   int indent) const
-{
-  this->dumpNode(indent);
+void InstrTreeNode::dump(int dumpChildren, int indent) const {
+  dumpNode(indent);
   
   if (dumpChildren)
     {
@@ -122,7 +115,7 @@ InstructionNode::InstructionNode(Instruction* _instr)
        }
     }
   
-  basicNode.opLabel = opLabel;
+  this->opLabel = opLabel;
 }
 
 
@@ -148,10 +141,8 @@ InstructionNode::dumpNode(int indent) const
 }
 
 
-VRegListNode::VRegListNode()
-  : InstrTreeNode(NTVRegListNode, NULL)
-{
-  basicNode.opLabel = VRegListOp;
+VRegListNode::VRegListNode() : InstrTreeNode(NTVRegListNode, 0) {
+  opLabel = VRegListOp;
 }
 
 void
@@ -164,10 +155,8 @@ VRegListNode::dumpNode(int indent) const
 }
 
 
-VRegNode::VRegNode(Value* _val)
-  : InstrTreeNode(NTVRegNode, _val)
-{
-  basicNode.opLabel = VRegNodeOp;
+VRegNode::VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) {
+  opLabel = VRegNodeOp;
 }
 
 void
@@ -181,10 +170,9 @@ VRegNode::dumpNode(int indent) const
 }
 
 
-ConstantNode::ConstantNode(ConstPoolVal* constVal)
-  : InstrTreeNode(NTConstNode, constVal)
-{
-  basicNode.opLabel = ConstantNodeOp;
+ConstantNode::ConstantNode(ConstPoolVal *constVal)
+  : InstrTreeNode(NTConstNode, constVal) {
+  opLabel = ConstantNodeOp;
 }
 
 void
@@ -198,10 +186,8 @@ ConstantNode::dumpNode(int indent) const
 }
 
 
-LabelNode::LabelNode(BasicBlock* _bblock)
-  : InstrTreeNode(NTLabelNode, _bblock)
-{
-  basicNode.opLabel = LabelNodeOp;
+LabelNode::LabelNode(BasicBlock *BB) : InstrTreeNode(NTLabelNode, BB) {
+  opLabel = LabelNodeOp;
 }
 
 void
@@ -255,10 +241,9 @@ InstrForest::noteTreeNodeForInstr(Instruction* instr,
 
 
 inline void
-InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child)
-{
-  parent->basicNode.leftChild = & child->basicNode;
-  child->basicNode.parent = & parent->basicNode;
+InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child) {
+  parent->LeftChild = child;
+  child->Parent = parent;
   if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
     treeRoots.erase((InstructionNode*) child); // no longer a tree root
 }
@@ -267,8 +252,8 @@ InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child)
 inline void
 InstrForest::setRightChild(InstrTreeNode* parent, InstrTreeNode* child)
 {
-  parent->basicNode.rightChild = & child->basicNode;
-  child->basicNode.parent = & parent->basicNode;
+  parent->RightChild = child;
+  child->Parent = parent;
   if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
     treeRoots.erase((InstructionNode*) child); // no longer a tree root
 }
index e6884ab572a6b62514e0221f58211e7298c8c543..675e489e46071829866fb9b962fd3c20d1691c21 100644 (file)
 //**************************************************************************/
 
 
-//************************** System Include Files ***************************/
-
-
-//*************************** User Include Files ***************************/
-
 #include "llvm/CodeGen/InstrSelection.h"
+#include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Type.h"
 #include "llvm/iMemory.h"
 #include "llvm/Instruction.h"
 #include "llvm/BasicBlock.h"
 #include "llvm/Method.h"
-#include "llvm/CodeGen/MachineInstr.h"
 
-
-//************************* Forward Declarations ***************************/
-
-static bool SelectInstructionsForTree(BasicTreeNode* treeRoot,
-                                     int goalnt,
+static bool SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
                                      TargetMachine &Target);
 
 
-//************************* Internal Data Types *****************************/
-
 enum SelectDebugLevel_t {
   Select_NoDebugInfo,
   Select_PrintMachineCode, 
@@ -50,8 +39,6 @@ cl::Enum<enum SelectDebugLevel_t> SelectDebugLevel("dselect", cl::NoFlags, // cl
    clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"), 0);
 
 
-//************************** External Functions ****************************/
-
 
 //---------------------------------------------------------------------------
 // Entry point for instruction selection using BURG.
@@ -87,7 +74,7 @@ SelectInstructionsForMethod(Method* method,
        treeRootIter != treeRoots.end();
        ++treeRootIter)
     {
-      BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode();
+      InstrTreeNode* basicNode = *treeRootIter;
       
       // Invoke BURM to label each tree node with a state
       (void) burm_label(basicNode);
@@ -192,8 +179,7 @@ FoldGetElemChain(const InstructionNode* getElemInstrNode,
 //---------------------------------------------------------------------------
 
 bool
-SelectInstructionsForTree(BasicTreeNode* treeRoot,
-                         int goalnt,
+SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
                          TargetMachine &Target)
 {
   // Use a static vector to avoid allocating a new one per VM instruction
@@ -220,7 +206,7 @@ SelectInstructionsForTree(BasicTreeNode* treeRoot,
   // 
   if (treeRoot->opLabel != VRegListOp)
     {
-      InstructionNode* instrNode = (InstructionNode*)treeRoot->treeNodePtr;
+      InstructionNode* instrNode = (InstructionNode*)treeRoot;
       assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
       
       unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target,
@@ -238,7 +224,7 @@ SelectInstructionsForTree(BasicTreeNode* treeRoot,
   if (nts[0])
     { // i.e., there is at least one kid
 
-      BasicTreeNode* kids[2];
+      InstrTreeNode* kids[2];
       int currentRule = ruleForNode;
       burm_kids(treeRoot, currentRule, kids);
       
@@ -258,8 +244,7 @@ SelectInstructionsForTree(BasicTreeNode* treeRoot,
       for (int i = 0; nts[i]; i++)
        {
          assert(i < 2);
-         InstrTreeNode::InstrTreeNodeType
-           nodeType = kids[i]->treeNodePtr->getNodeType();
+         InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
          if (nodeType == InstrTreeNode::NTVRegListNode ||
              nodeType == InstrTreeNode::NTInstructionNode)
            {