include/llvm/CodeGen/InstrForest.h

   1 // $Id$ -*-c++-*-
   2 //***************************************************************************
   3 // File:
   4 //      InstrForest.h
   5 //
   6 // Purpose:
   7 //      Convert SSA graph to instruction trees for instruction selection.
   8 //
   9 // Strategy:
  10 //  The basic idea is that we would like to group instructions into a single
  11 //  tree if one or more of them might be potentially combined into a single
  12 //  complex instruction in the target machine.
  13 //  Since this grouping is completely machine-independent, it is as
  14 //  aggressive as possible.  In particular, we group two instructions
  15 //  O and I if:
  16 //  (1) Instruction O computes an operand of instruction I, and
  17 //  (2) O and I are part of the same basic block, and
  18 //  (3) O has only a single use, viz., I.
  19 //
  20 // History:
  21 //      6/28/01  -  Vikram Adve  -  Created
  22 //**************************************************************************/
  23
  24 #ifndef LLVM_CODEGEN_INSTRFOREST_H
  25 #define LLVM_CODEGEN_INSTRFOREST_H
  26
  27 #include "llvm/Support/NonCopyable.h"
  28 #include "llvm/Support/HashExtras.h"
  29 #include "llvm/Instruction.h"
  30 #include <hash_map>
  31 #include <hash_set>
  32
  33 class ConstPoolVal;
  34 class BasicBlock;
  35 class Method;
  36 class InstrTreeNode;
  37 class InstrForest;
  38
  39 //--------------------------------------------------------------------------
  40 // OpLabel values for special-case nodes created for instruction selection.
  41 // All op-labels not defined here are identical to the instruction
  42 // opcode returned by Instruction::getInstType()
  43 //--------------------------------------------------------------------------
  44
  45 const int  InvalidOp    =  -1;
  46 const int  VRegListOp   =  97;
  47 const int  VRegNodeOp   =  98;
  48 const int  ConstantNodeOp= 99;
  49 const int  LabelNodeOp  = 100;
  50
  51 const int  RetValueOp   = 100 + Instruction::Ret;
  52 const int  BrCondOp     = 100 + Instruction::Br;
  53
  54 const int  SetCCOp      = 100 + Instruction::SetEQ;
  55
  56 const int  AllocaN      = 100 + Instruction::Alloca;            // 121
  57 const int  LoadIdx      = 100 + Instruction::Load;              // 122
  58 const int  GetElemPtrIdx= 100 + Instruction::GetElementPtr;     // 124
  59
  60 const int  ToBoolTy     = 100 + Instruction::Cast;              // 126
  61 const int  ToUByteTy    = ToBoolTy +  1;
  62 const int  ToSByteTy    = ToBoolTy +  2;
  63 const int  ToUShortTy   = ToBoolTy +  3;
  64 const int  ToShortTy    = ToBoolTy +  4;
  65 const int  ToUIntTy     = ToBoolTy +  5;
  66 const int  ToIntTy      = ToBoolTy +  6;
  67 const int  ToULongTy    = ToBoolTy +  7;
  68 const int  ToLongTy     = ToBoolTy +  8;
  69 const int  ToFloatTy    = ToBoolTy +  9;
  70 const int  ToDoubleTy   = ToBoolTy + 10;
  71 const int  ToArrayTy    = ToBoolTy + 11;
  72 const int  ToPointerTy  = ToBoolTy + 12;
  73
  74 //-------------------------------------------------------------------------
  75 // Data types needed by BURG and implemented by us
  76 //-------------------------------------------------------------------------
  77
  78 typedef int OpLabel;
  79 typedef int StateLabel;
  80
  81 //-------------------------------------------------------------------------
  82 // Declarations of data and functions created by BURG
  83 //-------------------------------------------------------------------------
  84
  85 extern short*           burm_nts[];
  86
  87 extern StateLabel       burm_label      (InstrTreeNode* p);
  88
  89 extern StateLabel       burm_state      (OpLabel op, StateLabel leftState,
  90                                          StateLabel rightState);
  91
  92 extern StateLabel       burm_rule       (StateLabel state, int goalNT);
  93
  94 extern InstrTreeNode**  burm_kids       (InstrTreeNode* p, int eruleno,
  95                                          InstrTreeNode* kids[]);
  96
  97 extern void             printcover      (InstrTreeNode*, int, int);
  98 extern void             printtree       (InstrTreeNode*);
  99 extern int              treecost        (InstrTreeNode*, int, int);
 100 extern void             printMatches    (InstrTreeNode*);
 101
 102
 103 //------------------------------------------------------------------------
 104 // class InstrTreeNode
 105 //
 106 // A single tree node in the instruction tree used for
 107 // instruction selection via BURG.
 108 //------------------------------------------------------------------------
 109
 110 class InstrTreeNode : public NonCopyableV {
 111 public:
 112   enum InstrTreeNodeType { NTInstructionNode,
 113                            NTVRegListNode,
 114                            NTVRegNode,
 115                            NTConstNode,
 116                            NTLabelNode };
 117
 118   // BASIC TREE NODE START
 119   InstrTreeNode* LeftChild;
 120   InstrTreeNode* RightChild;
 121   InstrTreeNode* Parent;
 122   OpLabel        opLabel;
 123   StateLabel     state;
 124   // BASIC TREE NODE END
 125
 126 protected:
 127   InstrTreeNodeType treeNodeType;
 128   Value*           val;
 129
 130 public:
 131   InstrTreeNode(InstrTreeNodeType nodeType, Value* _val)
 132     : treeNodeType(nodeType), val(_val) {
 133     LeftChild = RightChild = Parent = 0;
 134     opLabel   = InvalidOp;
 135   }
 136   virtual ~InstrTreeNode() {}
 137
 138   InstrTreeNodeType     getNodeType     () const { return treeNodeType; }
 139
 140   Value*                getValue        () const { return val; }
 141
 142   inline OpLabel        getOpLabel      () const { return opLabel; }
 143
 144   inline InstrTreeNode* leftChild() const {
 145     return LeftChild;
 146   }
 147
 148   // If right child is a list node, recursively get its *left* child
 149   inline InstrTreeNode* rightChild() const {
 150     return (!RightChild ? 0 :
 151             (RightChild->getOpLabel() == VRegListOp
 152              ? RightChild->LeftChild : RightChild));
 153   }
 154
 155   inline InstrTreeNode *parent() const {
 156     return Parent;
 157   }
 158
 159   void dump(int dumpChildren, int indent) const;
 160
 161 protected:
 162   virtual void dumpNode(int indent) const = 0;
 163
 164   friend class InstrForest;
 165 };
 166
 167
 168 class InstructionNode : public InstrTreeNode {
 169 public:
 170   InstructionNode(Instruction *_instr);
 171
 172   Instruction *getInstruction() const {
 173     assert(treeNodeType == NTInstructionNode);
 174     return cast<Instruction>(val);
 175   }
 176 protected:
 177   virtual void dumpNode(int indent) const;
 178 };
 179
 180
 181 class VRegListNode : public InstrTreeNode {
 182 public:
 183   VRegListNode() : InstrTreeNode(NTVRegListNode, 0) {
 184     opLabel = VRegListOp;
 185   }
 186 protected:
 187   virtual void dumpNode(int indent) const;
 188 };
 189
 190
 191 class VRegNode : public InstrTreeNode {
 192 public:
 193   VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) {
 194     opLabel = VRegNodeOp;
 195   }
 196 protected:
 197   virtual void dumpNode(int indent) const;
 198 };
 199
 200
 201 class ConstantNode : public InstrTreeNode {
 202 public:
 203   ConstantNode(ConstPoolVal *constVal)
 204     : InstrTreeNode(NTConstNode, (Value*)constVal) {
 205     opLabel = ConstantNodeOp;
 206   }
 207   ConstPoolVal *getConstVal() const { return (ConstPoolVal*) val;}
 208 protected:
 209   virtual void dumpNode(int indent) const;
 210 };
 211
 212
 213 class LabelNode : public InstrTreeNode {
 214 public:
 215   LabelNode(BasicBlock* BB) : InstrTreeNode(NTLabelNode, (Value*)BB) {
 216     opLabel = LabelNodeOp;
 217   }
 218
 219   BasicBlock *getBasicBlock() const { return (BasicBlock*)val;}
 220 protected:
 221   virtual void dumpNode(int indent) const;
 222 };
 223
 224
 225 //------------------------------------------------------------------------
 226 // class InstrForest
 227 //
 228 // A forest of instruction trees, usually for a single method.
 229 //
 230 // Methods:
 231 //     buildTreesForMethod()    Builds the forest of trees for a method
 232 //     getTreeNodeForInstr()    Returns the tree node for an Instruction
 233 //     getRootSet()             Returns a set of root nodes for all the trees
 234 //
 235 //------------------------------------------------------------------------
 236
 237 class InstrForest : private hash_map<const Instruction *, InstructionNode*> {
 238 private:
 239   hash_set<InstructionNode*> treeRoots;
 240
 241 public:
 242   /*ctor*/      InstrForest     (Method *M);
 243   /*dtor*/      ~InstrForest    ();
 244
 245   inline InstructionNode *getTreeNodeForInstr(Instruction* instr) {
 246     return (*this)[instr];
 247   }
 248
 249   inline const hash_set<InstructionNode*> &getRootSet() const {
 250     return treeRoots;
 251   }
 252
 253   void dump() const;
 254
 255 private:
 256   //
 257   // Private methods for buidling the instruction forest
 258   //
 259   void setLeftChild (InstrTreeNode* parent, InstrTreeNode* child);
 260   void setRightChild(InstrTreeNode* parent, InstrTreeNode* child);
 261   void setParent    (InstrTreeNode* child,  InstrTreeNode* parent);
 262   void noteTreeNodeForInstr(Instruction* instr, InstructionNode* treeNode);
 263
 264   InstructionNode* buildTreeForInstruction(Instruction* instr);
 265 };
 266
 267 #endif