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/Instruction.h"
  18 #include "llvm/BasicBlock.h"
  19 #include "llvm/Function.h"
  20 #include "Support/Tree.h"
  21 #include <map>
  22 #include <assert.h>
  23
  24 template<class Payload> class InstTreeNode;
  25 template<class Payload> class InstForest;
  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   typedef typename std::vector<InstTreeNode<Payload> *>::const_iterator const_iterator;
 147
 148   // InstMap - Map contains entries for ALL instructions in the method and the
 149   // InstTreeNode that they correspond to.
 150   //
 151   std::map<Instruction*, InstTreeNode<Payload> *> InstMap;
 152
 153   void addInstMapping(Instruction *I, InstTreeNode<Payload> *IN) {
 154     InstMap.insert(std::make_pair(I, IN));
 155   }
 156
 157   void removeInstFromRootList(Instruction *I) {
 158     for (unsigned i = size(); i > 0; --i)
 159       if (operator[](i-1)->getValue() == I) {
 160         erase(begin()+i-1);
 161         return;
 162       }
 163   }
 164
 165 public:
 166   // ctor - Create an instruction forest for the specified method...
 167   InstForest(Function *F) {
 168     for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
 169       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 170         if (!getInstNode(I)) {  // Do we already have a tree for this inst?
 171           // No, create one!  InstTreeNode ctor automatically adds the
 172           // created node into our InstMap
 173           push_back(new InstTreeNode<Payload>(*this, I, 0));
 174         }
 175   }
 176
 177   // dtor - Free the trees...
 178   ~InstForest() {
 179     for (unsigned i = size(); i != 0; --i)
 180       delete operator[](i-1);
 181   }
 182
 183   // getInstNode - Return the instruction node that corresponds to the specified
 184   // instruction...  This node may be embeded in a larger tree, in which case
 185   // the parent pointer can be used to find the root of the tree.
 186   //
 187   inline InstTreeNode<Payload> *getInstNode(Instruction *Inst) {
 188     typename std::map<Instruction*, InstTreeNode<Payload> *>::iterator I =
 189       InstMap.find(Inst);
 190     if (I != InstMap.end()) return I->second;
 191     return 0;
 192   }
 193   inline const InstTreeNode<Payload> *getInstNode(const Instruction *Inst)const{
 194     typename std::map<Instruction*, InstTreeNode<Payload>*>::const_iterator I =
 195       InstMap.find(Inst);
 196     if (I != InstMap.end()) return I->second;
 197     return 0;
 198   }
 199
 200   // print - Called by operator<< below...
 201   void print(std::ostream &out) const {
 202     for (const_iterator I = begin(), E = end(); I != E; ++I)
 203       out << *I;
 204   }
 205 };
 206
 207 template<class Payload>
 208 inline std::ostream &operator<<(std::ostream &o, const InstForest<Payload> &IF){
 209   IF.print(o); return o;
 210 }
 211
 212
 213 //===----------------------------------------------------------------------===//
 214 //  Method Implementations
 215 //===----------------------------------------------------------------------===//
 216
 217 // CanMergeInstIntoTree - Return true if it is allowed to merge the specified
 218 // instruction into 'this' instruction tree.  This is allowed iff:
 219 //   1. The instruction is in the same basic block as the current one
 220 //   2. The instruction has only one use
 221 //
 222 template <class Payload>
 223 bool InstTreeNode<Payload>::CanMergeInstIntoTree(Instruction *I) {
 224   if (I->use_size() > 1) return false;
 225   return I->getParent() == cast<Instruction>(getValue())->getParent();
 226 }
 227
 228
 229 // InstTreeNode ctor - This constructor creates the instruction tree for the
 230 // specified value.  If the value is an instruction, it recursively creates the
 231 // internal/child nodes and adds them to the instruction forest.
 232 //
 233 template <class Payload>
 234 InstTreeNode<Payload>::InstTreeNode(InstForest<Payload> &IF, Value *V,
 235                                     InstTreeNode *Parent) : super(Parent) {
 236   getTreeData().first.first = V;   // Save tree node
 237
 238   if (!isa<Instruction>(V)) {
 239     assert((isa<Constant>(V) || isa<BasicBlock>(V) ||
 240             isa<Argument>(V) || isa<GlobalValue>(V)) &&
 241            "Unrecognized value type for InstForest Partition!");
 242     if (isa<Constant>(V))
 243       getTreeData().first.second = ConstNode;
 244     else if (isa<BasicBlock>(V))
 245       getTreeData().first.second = BasicBlockNode;
 246     else
 247       getTreeData().first.second = TemporaryNode;
 248
 249     return;
 250   }
 251
 252   // Must be an instruction then... see if we can include it in this tree!
 253   Instruction *I = cast<Instruction>(V);
 254   if (Parent && !Parent->CanMergeInstIntoTree(I)) {
 255     // Not root node of tree, but mult uses?
 256     getTreeData().first.second = TemporaryNode;   // Must be a temporary!
 257     return;
 258   }
 259
 260   // Otherwise, we are an internal instruction node.  We must process our
 261   // uses and add them as children of this node.
 262   //
 263   std::vector<InstTreeNode*> Children;
 264
 265   // Make sure that the forest knows about us!
 266   IF.addInstMapping(I, this);
 267
 268   // Walk the operands of the instruction adding children for all of the uses
 269   // of the instruction...
 270   //
 271   for (Instruction::op_iterator OI = I->op_begin(); OI != I->op_end(); ++OI) {
 272     Value *Operand = *OI;
 273     InstTreeNode<Payload> *IN = IF.getInstNode(dyn_cast<Instruction>(Operand));
 274     if (IN && CanMergeInstIntoTree(cast<Instruction>(Operand))) {
 275       Children.push_back(IN);
 276       IF.removeInstFromRootList(cast<Instruction>(Operand));
 277     } else {
 278       // No node for this child yet... create one now!
 279       Children.push_back(new InstTreeNode(IF, *OI, this));
 280     }
 281   }
 282
 283   setChildren(Children);
 284   getTreeData().first.second = InstructionNode;
 285 }
 286
 287 #endif
 288