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