include/llvm/Analysis/InstForest.h

   1 //===- llvm/Analysis/InstForest.h - Partition Func into forest --*- 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 // This interface is used to partition a method into a forest of instruction
  11 // trees, where the following invariants hold:
  12 //
  13 // 1. The instructions in a tree are all related to each other through use
  14 //    relationships.
  15 // 2. All instructions in a tree are members of the same basic block
  16 // 3. All instructions in a tree (with the exception of the root), may have only
  17 //    a single user.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_ANALYSIS_INSTFOREST_H
  22 #define LLVM_ANALYSIS_INSTFOREST_H
  23
  24 #include "llvm/Function.h"
  25 #include "Support/Tree.h"
  26 #include <map>
  27
  28 namespace llvm {
  29
  30 template<class Payload> class InstTreeNode;
  31 template<class Payload> class InstForest;
  32
  33 //===----------------------------------------------------------------------===//
  34 //  Class InstTreeNode
  35 //===----------------------------------------------------------------------===//
  36 //
  37 // There is an instance of this class for each node in the instruction forest.
  38 // There should be a node for every instruction in the tree, as well as
  39 // Temporary nodes that correspond to other trees in the forest and to variables
  40 // and global variables.  Constants have their own special node.
  41 //
  42 template<class Payload>
  43 class InstTreeNode :
  44     public Tree<InstTreeNode<Payload>,
  45                 std::pair<std::pair<Value*, char>, Payload> > {
  46
  47   friend class InstForest<Payload>;
  48   typedef Tree<InstTreeNode<Payload>,
  49                std::pair<std::pair<Value*, char>, Payload> > super;
  50
  51   // Constants used for the node type value
  52   enum NodeTypeTy {
  53     ConstNode        = Value::ConstantVal,
  54     BasicBlockNode   = Value::BasicBlockVal,
  55     InstructionNode  = Value::InstructionVal,
  56     TemporaryNode    = -1
  57   };
  58
  59   // Helper functions to make accessing our data nicer...
  60   const Value *getValue() const { return this->getTreeData().first.first; }
  61         Value *getValue()       { return this->getTreeData().first.first; }
  62   enum NodeTypeTy getNodeType() const {
  63     return (enum NodeTypeTy)this->getTreeData().first.second;
  64   }
  65
  66   InstTreeNode(const InstTreeNode &);     // Do not implement
  67   void operator=(const InstTreeNode &);   // Do not implement
  68
  69   // Only creatable by InstForest
  70   InstTreeNode(InstForest<Payload> &IF, Value *V, InstTreeNode *Parent);
  71   bool CanMergeInstIntoTree(Instruction *Inst);
  72 public:
  73   // Accessor functions...
  74   inline       Payload &getData()       { return this->getTreeData().second; }
  75   inline const Payload &getData() const { return this->getTreeData().second; }
  76
  77   // Type checking functions...
  78   inline bool isConstant()    const { return getNodeType() == ConstNode; }
  79   inline bool isBasicBlock()  const { return getNodeType() == BasicBlockNode; }
  80   inline bool isInstruction() const { return getNodeType() == InstructionNode; }
  81   inline bool isTemporary()   const { return getNodeType() == TemporaryNode; }
  82
  83   // Accessors for different node types...
  84   inline Constant *getConstant() {
  85     return cast<Constant>(getValue());
  86   }
  87   inline const Constant *getConstant() const {
  88     return cast<Constant>(getValue());
  89   }
  90   inline BasicBlock *getBasicBlock() {
  91     return cast<BasicBlock>(getValue());
  92   }
  93   inline const BasicBlock *getBasicBlock() const {
  94     return cast<BasicBlock>(getValue());
  95   }
  96   inline Instruction *getInstruction() {
  97     assert(isInstruction() && "getInstruction() on non instruction node!");
  98     return cast<Instruction>(getValue());
  99   }
 100   inline const Instruction *getInstruction() const {
 101     assert(isInstruction() && "getInstruction() on non instruction node!");
 102     return cast<Instruction>(getValue());
 103   }
 104   inline Instruction *getTemporary() {
 105     assert(isTemporary() && "getTemporary() on non temporary node!");
 106     return cast<Instruction>(getValue());
 107   }
 108   inline const Instruction *getTemporary() const {
 109     assert(isTemporary() && "getTemporary() on non temporary node!");
 110     return cast<Instruction>(getValue());
 111   }
 112
 113 public:
 114   // print - Called by operator<< below...
 115   void print(std::ostream &o, unsigned Indent) const {
 116     o << std::string(Indent*2, ' ');
 117     switch (getNodeType()) {
 118     case ConstNode      : o << "Constant   : "; break;
 119     case BasicBlockNode : o << "BasicBlock : " << getValue()->getName() << "\n";
 120       return;
 121     case InstructionNode: o << "Instruction: "; break;
 122     case TemporaryNode  : o << "Temporary  : "; break;
 123     default: o << "UNKNOWN NODE TYPE: " << getNodeType() << "\n"; abort();
 124     }
 125
 126     o << getValue();
 127     if (!isa<Instruction>(getValue())) o << "\n";
 128
 129     for (unsigned i = 0; i < this->getNumChildren(); ++i)
 130       this->getChild(i)->print(o, Indent+1);
 131   }
 132 };
 133
 134 template<class Payload>
 135 inline std::ostream &operator<<(std::ostream &o,
 136                                 const InstTreeNode<Payload> *N) {
 137   N->print(o, 0); return o;
 138 }
 139
 140 //===----------------------------------------------------------------------===//
 141 //  Class InstForest
 142 //===----------------------------------------------------------------------===//
 143 //
 144 // This class represents the instruction forest itself.  It exposes iterators
 145 // to an underlying vector of Instruction Trees.  Each root of the tree is
 146 // guaranteed to be an instruction node.  The constructor builds the forest.
 147 //
 148 template<class Payload>
 149 class InstForest : public std::vector<InstTreeNode<Payload> *> {
 150   friend class InstTreeNode<Payload>;
 151
 152   typedef typename std::vector<InstTreeNode<Payload> *>::const_iterator const_iterator;
 153
 154   // InstMap - Map contains entries for ALL instructions in the method and the
 155   // InstTreeNode that they correspond to.
 156   //
 157   std::map<Instruction*, InstTreeNode<Payload> *> InstMap;
 158
 159   void addInstMapping(Instruction *I, InstTreeNode<Payload> *IN) {
 160     InstMap.insert(std::make_pair(I, IN));
 161   }
 162
 163   void removeInstFromRootList(Instruction *I) {
 164     for (unsigned i = this->size(); i > 0; --i)
 165       if ((*this)[i-1]->getValue() == I) {
 166         this->erase(this->begin()+i-1);
 167         return;
 168       }
 169   }
 170
 171 public:
 172   // ctor - Create an instruction forest for the specified method...
 173   InstForest(Function *F) {
 174     for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
 175       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 176         if (!getInstNode(I)) {  // Do we already have a tree for this inst?
 177           // No, create one!  InstTreeNode ctor automatically adds the
 178           // created node into our InstMap
 179           push_back(new InstTreeNode<Payload>(*this, I, 0));
 180         }
 181   }
 182
 183   // dtor - Free the trees...
 184   ~InstForest() {
 185     for (unsigned i = this->size(); i != 0; --i)
 186       delete (*this)[i-1];
 187   }
 188
 189   // getInstNode - Return the instruction node that corresponds to the specified
 190   // instruction...  This node may be embeded in a larger tree, in which case
 191   // the parent pointer can be used to find the root of the tree.
 192   //
 193   inline InstTreeNode<Payload> *getInstNode(Instruction *Inst) {
 194     typename std::map<Instruction*, InstTreeNode<Payload> *>::iterator I =
 195       InstMap.find(Inst);
 196     if (I != InstMap.end()) return I->second;
 197     return 0;
 198   }
 199   inline const InstTreeNode<Payload> *getInstNode(const Instruction *Inst)const{
 200     typename std::map<Instruction*, InstTreeNode<Payload>*>::const_iterator I =
 201       InstMap.find(Inst);
 202     if (I != InstMap.end()) return I->second;
 203     return 0;
 204   }
 205
 206   // print - Called by operator<< below...
 207   void print(std::ostream &out) const {
 208     for (const_iterator I = this->begin(), E = this->end(); I != E; ++I)
 209       out << *I;
 210   }
 211 };
 212
 213 template<class Payload>
 214 inline std::ostream &operator<<(std::ostream &o, const InstForest<Payload> &IF){
 215   IF.print(o); return o;
 216 }
 217
 218
 219 //===----------------------------------------------------------------------===//
 220 //  Method Implementations
 221 //===----------------------------------------------------------------------===//
 222
 223 // CanMergeInstIntoTree - Return true if it is allowed to merge the specified
 224 // instruction into 'this' instruction tree.  This is allowed iff:
 225 //   1. The instruction is in the same basic block as the current one
 226 //   2. The instruction has only one use
 227 //
 228 template <class Payload>
 229 bool InstTreeNode<Payload>::CanMergeInstIntoTree(Instruction *I) {
 230   if (!I->use_empty() && !I->hasOneUse()) return false;
 231   return I->getParent() == cast<Instruction>(getValue())->getParent();
 232 }
 233
 234
 235 // InstTreeNode ctor - This constructor creates the instruction tree for the
 236 // specified value.  If the value is an instruction, it recursively creates the
 237 // internal/child nodes and adds them to the instruction forest.
 238 //
 239 template <class Payload>
 240 InstTreeNode<Payload>::InstTreeNode(InstForest<Payload> &IF, Value *V,
 241                                     InstTreeNode *Parent) : super(Parent) {
 242   this->getTreeData().first.first = V;   // Save tree node
 243
 244   if (!isa<Instruction>(V)) {
 245     assert((isa<Constant>(V) || isa<BasicBlock>(V) ||
 246             isa<Argument>(V) || isa<GlobalValue>(V)) &&
 247            "Unrecognized value type for InstForest Partition!");
 248     if (isa<Constant>(V))
 249       this->getTreeData().first.second = ConstNode;
 250     else if (isa<BasicBlock>(V))
 251       this->getTreeData().first.second = BasicBlockNode;
 252     else
 253       this->getTreeData().first.second = TemporaryNode;
 254
 255     return;
 256   }
 257
 258   // Must be an instruction then... see if we can include it in this tree!
 259   Instruction *I = cast<Instruction>(V);
 260   if (Parent && !Parent->CanMergeInstIntoTree(I)) {
 261     // Not root node of tree, but mult uses?
 262     this->getTreeData().first.second = TemporaryNode;   // Must be a temporary!
 263     return;
 264   }
 265
 266   // Otherwise, we are an internal instruction node.  We must process our
 267   // uses and add them as children of this node.
 268   //
 269   std::vector<InstTreeNode*> Children;
 270
 271   // Make sure that the forest knows about us!
 272   IF.addInstMapping(I, this);
 273
 274   // Walk the operands of the instruction adding children for all of the uses
 275   // of the instruction...
 276   //
 277   for (Instruction::op_iterator OI = I->op_begin(); OI != I->op_end(); ++OI) {
 278     Value *Operand = *OI;
 279     InstTreeNode<Payload> *IN = IF.getInstNode(dyn_cast<Instruction>(Operand));
 280     if (IN && CanMergeInstIntoTree(cast<Instruction>(Operand))) {
 281       Children.push_back(IN);
 282       IF.removeInstFromRootList(cast<Instruction>(Operand));
 283     } else {
 284       // No node for this child yet... create one now!
 285       Children.push_back(new InstTreeNode(IF, *OI, this));
 286     }
 287   }
 288
 289   setChildren(Children);
 290   this->getTreeData().first.second = InstructionNode;
 291 }
 292
 293 } // End llvm namespace
 294
 295 #endif
 296