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