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