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