include/llvm/CodeGen/InstrForest.h

   1 //===-- llvm/CodeGen/InstForest.h -------------------------------*- C++ -*-===//
   2 //
   3 // Purpose:
   4 //      Convert SSA graph to instruction trees for instruction selection.
   5 //
   6 // Strategy:
   7 //  The basic idea is that we would like to group instructions into a single
   8 //  tree if one or more of them might be potentially combined into a single
   9 //  complex instruction in the target machine.
  10 //  Since this grouping is completely machine-independent, it is as
  11 //  aggressive as possible.  In particular, we group two instructions
  12 //  O and I if:
  13 //  (1) Instruction O computes an operand of instruction I, and
  14 //  (2) O and I are part of the same basic block, and
  15 //  (3) O has only a single use, viz., I.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #ifndef LLVM_CODEGEN_INSTRFOREST_H
  20 #define LLVM_CODEGEN_INSTRFOREST_H
  21
  22 #include "llvm/Instruction.h"
  23 #include "Support/hash_map"
  24
  25 class Constant;
  26 class Function;
  27 class InstrTreeNode;
  28 class InstrForest;
  29
  30 //--------------------------------------------------------------------------
  31 // OpLabel values for special-case nodes created for instruction selection.
  32 // All op-labels not defined here are identical to the instruction
  33 // opcode returned by Instruction::getOpcode()
  34 //--------------------------------------------------------------------------
  35
  36 const int  InvalidOp    =  -1;
  37 const int  VRegListOp   =  97;
  38 const int  VRegNodeOp   =  98;
  39 const int  ConstantNodeOp= 99;
  40 const int  LabelNodeOp  = 100;
  41
  42 const int  RetValueOp   = 100 + Instruction::Ret;               // 101
  43 const int  BrCondOp     = 100 + Instruction::Br;                // 102
  44
  45 const int  BAndOp       = 100 + Instruction::And;               // 111
  46 const int  BOrOp        = 100 + Instruction::Or;                // 112
  47 const int  BXorOp       = 100 + Instruction::Xor;               // 113
  48 const int  BNotOp       = 200 + Instruction::Xor;               // 213
  49 const int   NotOp       = 300 + Instruction::Xor;               // 313
  50
  51 const int  SetCCOp      = 100 + Instruction::SetEQ;             // 114
  52
  53 const int  AllocaN      = 100 + Instruction::Alloca;            // 122
  54 const int  LoadIdx      = 100 + Instruction::Load;              // 123
  55 const int  GetElemPtrIdx= 100 + Instruction::GetElementPtr;     // 125
  56
  57 const int  ToBoolTy     = 100 + Instruction::Cast;              // 127
  58 const int  ToUByteTy    = ToBoolTy +  1;
  59 const int  ToSByteTy    = ToBoolTy +  2;
  60 const int  ToUShortTy   = ToBoolTy +  3;
  61 const int  ToShortTy    = ToBoolTy +  4;
  62 const int  ToUIntTy     = ToBoolTy +  5;
  63 const int  ToIntTy      = ToBoolTy +  6;
  64 const int  ToULongTy    = ToBoolTy +  7;
  65 const int  ToLongTy     = ToBoolTy +  8;
  66 const int  ToFloatTy    = ToBoolTy +  9;
  67 const int  ToDoubleTy   = ToBoolTy + 10;
  68 const int  ToArrayTy    = ToBoolTy + 11;
  69 const int  ToPointerTy  = ToBoolTy + 12;
  70
  71 //-------------------------------------------------------------------------
  72 // Data types needed by BURG and implemented by us
  73 //-------------------------------------------------------------------------
  74
  75 typedef int OpLabel;
  76 typedef int StateLabel;
  77
  78 //-------------------------------------------------------------------------
  79 // Declarations of data and functions created by BURG
  80 //-------------------------------------------------------------------------
  81
  82 extern short*           burm_nts[];
  83
  84 extern StateLabel       burm_label      (InstrTreeNode* p);
  85
  86 extern StateLabel       burm_state      (OpLabel op, StateLabel leftState,
  87                                          StateLabel rightState);
  88
  89 extern StateLabel       burm_rule       (StateLabel state, int goalNT);
  90
  91 extern InstrTreeNode**  burm_kids       (InstrTreeNode* p, int eruleno,
  92                                          InstrTreeNode* kids[]);
  93
  94 extern void             printcover      (InstrTreeNode*, int, int);
  95 extern void             printtree       (InstrTreeNode*);
  96 extern int              treecost        (InstrTreeNode*, int, int);
  97 extern void             printMatches    (InstrTreeNode*);
  98
  99
 100 //------------------------------------------------------------------------
 101 // class InstrTreeNode
 102 //
 103 // A single tree node in the instruction tree used for
 104 // instruction selection via BURG.
 105 //------------------------------------------------------------------------
 106
 107 class InstrTreeNode {
 108   InstrTreeNode(const InstrTreeNode &);   // DO NOT IMPLEMENT
 109   void operator=(const InstrTreeNode &);  // DO NOT IMPLEMENT
 110 public:
 111   enum InstrTreeNodeType { NTInstructionNode,
 112                            NTVRegListNode,
 113                            NTVRegNode,
 114                            NTConstNode,
 115                            NTLabelNode };
 116
 117   // BASIC TREE NODE START
 118   InstrTreeNode* LeftChild;
 119   InstrTreeNode* RightChild;
 120   InstrTreeNode* Parent;
 121   OpLabel        opLabel;
 122   StateLabel     state;
 123   // BASIC TREE NODE END
 124
 125 protected:
 126   InstrTreeNodeType treeNodeType;
 127   Value*           val;
 128
 129 public:
 130   InstrTreeNode(InstrTreeNodeType nodeType, Value* _val)
 131     : treeNodeType(nodeType), val(_val) {
 132     LeftChild = RightChild = Parent = 0;
 133     opLabel   = InvalidOp;
 134   }
 135   virtual ~InstrTreeNode() {
 136     delete LeftChild;
 137     delete RightChild;
 138   }
 139
 140   InstrTreeNodeType     getNodeType     () const { return treeNodeType; }
 141
 142   Value*                getValue        () const { return val; }
 143
 144   inline OpLabel        getOpLabel      () const { return opLabel; }
 145
 146   inline InstrTreeNode* leftChild() const {
 147     return LeftChild;
 148   }
 149
 150   // If right child is a list node, recursively get its *left* child
 151   inline InstrTreeNode* rightChild() const {
 152     return (!RightChild ? 0 :
 153             (RightChild->getOpLabel() == VRegListOp
 154              ? RightChild->LeftChild : RightChild));
 155   }
 156
 157   inline InstrTreeNode *parent() const {
 158     return Parent;
 159   }
 160
 161   void dump(int dumpChildren, int indent) const;
 162
 163 protected:
 164   virtual void dumpNode(int indent) const = 0;
 165
 166   friend class InstrForest;
 167 };
 168
 169
 170 class InstructionNode : public InstrTreeNode {
 171 private:
 172   bool codeIsFoldedIntoParent;
 173
 174 public:
 175   InstructionNode(Instruction *_instr);
 176
 177   Instruction *getInstruction() const {
 178     assert(treeNodeType == NTInstructionNode);
 179     return cast<Instruction>(val);
 180   }
 181
 182   void markFoldedIntoParent() { codeIsFoldedIntoParent = true; }
 183   bool isFoldedIntoParent()   { return codeIsFoldedIntoParent; }
 184
 185   // Methods to support type inquiry through isa, cast, and dyn_cast:
 186   static inline bool classof(const InstructionNode *N) { return true; }
 187   static inline bool classof(const InstrTreeNode *N) {
 188     return N->getNodeType() == InstrTreeNode::NTInstructionNode;
 189   }
 190
 191 protected:
 192   virtual void dumpNode(int indent) const;
 193 };
 194
 195
 196 class VRegListNode : public InstrTreeNode {
 197 public:
 198   VRegListNode() : InstrTreeNode(NTVRegListNode, 0) {
 199     opLabel = VRegListOp;
 200   }
 201
 202   // Methods to support type inquiry through isa, cast, and dyn_cast:
 203   static inline bool classof(const VRegListNode  *N) { return true; }
 204   static inline bool classof(const InstrTreeNode *N) {
 205     return N->getNodeType() == InstrTreeNode::NTVRegListNode;
 206   }
 207
 208 protected:
 209   virtual void dumpNode(int indent) const;
 210 };
 211
 212
 213 class VRegNode : public InstrTreeNode {
 214 public:
 215   VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) {
 216     opLabel = VRegNodeOp;
 217   }
 218
 219   // Methods to support type inquiry through isa, cast, and dyn_cast:
 220   static inline bool classof(const VRegNode  *N) { return true; }
 221   static inline bool classof(const InstrTreeNode *N) {
 222     return N->getNodeType() == InstrTreeNode::NTVRegNode;
 223   }
 224
 225 protected:
 226   virtual void dumpNode(int indent) const;
 227 };
 228
 229
 230 class ConstantNode : public InstrTreeNode {
 231 public:
 232   ConstantNode(Constant *constVal)
 233     : InstrTreeNode(NTConstNode, (Value*)constVal) {
 234     opLabel = ConstantNodeOp;
 235   }
 236   Constant *getConstVal() const { return (Constant*) val;}
 237
 238   // Methods to support type inquiry through isa, cast, and dyn_cast:
 239   static inline bool classof(const ConstantNode  *N) { return true; }
 240   static inline bool classof(const InstrTreeNode *N) {
 241     return N->getNodeType() == InstrTreeNode::NTConstNode;
 242   }
 243
 244 protected:
 245   virtual void dumpNode(int indent) const;
 246 };
 247
 248
 249 class LabelNode : public InstrTreeNode {
 250 public:
 251   LabelNode(BasicBlock* BB) : InstrTreeNode(NTLabelNode, (Value*)BB) {
 252     opLabel = LabelNodeOp;
 253   }
 254
 255   BasicBlock *getBasicBlock() const { return (BasicBlock*)val;}
 256
 257   // Methods to support type inquiry through isa, cast, and dyn_cast:
 258   static inline bool classof(const LabelNode     *N) { return true; }
 259   static inline bool classof(const InstrTreeNode *N) {
 260     return N->getNodeType() == InstrTreeNode::NTLabelNode;
 261   }
 262
 263 protected:
 264   virtual void dumpNode(int indent) const;
 265 };
 266
 267
 268 //------------------------------------------------------------------------
 269 // class InstrForest
 270 //
 271 // A forest of instruction trees, usually for a single method.
 272 //
 273 // Methods:
 274 //     buildTreesForMethod()    Builds the forest of trees for a method
 275 //     getTreeNodeForInstr()    Returns the tree node for an Instruction
 276 //     getRootSet()             Returns a set of root nodes for all the trees
 277 //
 278 //------------------------------------------------------------------------
 279
 280 class InstrForest : private hash_map<const Instruction *, InstructionNode*> {
 281 public:
 282   // Use a vector for the root set to get a deterministic iterator
 283   // for stable code generation.  Even though we need to erase nodes
 284   // during forest construction, a vector should still be efficient
 285   // because the elements to erase are nearly always near the end.
 286   typedef std::vector<InstructionNode*> RootSet;
 287   typedef RootSet::      iterator       root_iterator;
 288   typedef RootSet::const_iterator const_root_iterator;
 289
 290 private:
 291   RootSet treeRoots;
 292
 293 public:
 294   /*ctor*/      InstrForest     (Function *F);
 295   /*dtor*/      ~InstrForest    ();
 296
 297   inline InstructionNode *getTreeNodeForInstr(Instruction* instr) {
 298     return (*this)[instr];
 299   }
 300
 301   const_root_iterator roots_begin() const     { return treeRoots.begin(); }
 302         root_iterator roots_begin()           { return treeRoots.begin(); }
 303   const_root_iterator roots_end  () const     { return treeRoots.end();   }
 304         root_iterator roots_end  ()           { return treeRoots.end();   }
 305
 306   void dump() const;
 307
 308 private:
 309   //
 310   // Private methods for buidling the instruction forest
 311   //
 312   void eraseRoot    (InstructionNode* node);
 313   void setLeftChild (InstrTreeNode* parent, InstrTreeNode* child);
 314   void setRightChild(InstrTreeNode* parent, InstrTreeNode* child);
 315   void setParent    (InstrTreeNode* child,  InstrTreeNode* parent);
 316   void noteTreeNodeForInstr(Instruction* instr, InstructionNode* treeNode);
 317
 318   InstructionNode* buildTreeForInstruction(Instruction* instr);
 319 };
 320
 321 #endif