include/llvm/CodeGen/InstrForest.h

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