include/llvm/Analysis/InstForest.h

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