include/llvm/Analysis/InstForest.h

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