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