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