1 //===- llvm/Analysis/InstForest.h - Partition Func into forest ---*- C++ -*--=//
3 // This interface is used to partition a method into a forest of instruction
4 // trees, where the following invariants hold:
6 // 1. The instructions in a tree are all related to each other through use
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
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_INSTFOREST_H
15 #define LLVM_ANALYSIS_INSTFOREST_H
17 #include "llvm/Instruction.h"
18 #include "llvm/BasicBlock.h"
19 #include "Support/Tree.h"
24 template<class Payload> class InstTreeNode;
25 template<class Payload> class InstForest;
28 //===----------------------------------------------------------------------===//
30 //===----------------------------------------------------------------------===//
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.
37 template<class Payload>
39 public Tree<InstTreeNode<Payload>,
40 std::pair<std::pair<Value*, char>, Payload> > {
42 friend class InstForest<Payload>;
43 typedef Tree<InstTreeNode<Payload>,
44 std::pair<std::pair<Value*, char>, Payload> > super;
46 // Constants used for the node type value
48 ConstNode = Value::ConstantVal,
49 BasicBlockNode = Value::BasicBlockVal,
50 InstructionNode = Value::InstructionVal,
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;
61 InstTreeNode(const InstTreeNode &); // Do not implement
62 void operator=(const InstTreeNode &); // Do not implement
64 // Only creatable by InstForest
65 InstTreeNode(InstForest<Payload> &IF, Value *V, InstTreeNode *Parent);
66 bool CanMergeInstIntoTree(Instruction *Inst);
68 // Accessor functions...
69 inline Payload &getData() { return getTreeData().second; }
70 inline const Payload &getData() const { return getTreeData().second; }
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; }
78 // Accessors for different node types...
79 inline Constant *getConstant() {
80 return cast<Constant>(getValue());
82 inline const Constant *getConstant() const {
83 return cast<const Constant>(getValue());
85 inline BasicBlock *getBasicBlock() {
86 return cast<BasicBlock>(getValue());
88 inline const BasicBlock *getBasicBlock() const {
89 return cast<const BasicBlock>(getValue());
91 inline Instruction *getInstruction() {
92 assert(isInstruction() && "getInstruction() on non instruction node!");
93 return cast<Instruction>(getValue());
95 inline const Instruction *getInstruction() const {
96 assert(isInstruction() && "getInstruction() on non instruction node!");
97 return cast<Instruction>(getValue());
99 inline Instruction *getTemporary() {
100 assert(isTemporary() && "getTemporary() on non temporary node!");
101 return cast<Instruction>(getValue());
103 inline const Instruction *getTemporary() const {
104 assert(isTemporary() && "getTemporary() on non temporary node!");
105 return cast<Instruction>(getValue());
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";
116 case InstructionNode: o << "Instruction: "; break;
117 case TemporaryNode : o << "Temporary : "; break;
118 default: o << "UNKNOWN NODE TYPE: " << getNodeType() << "\n"; abort();
122 if (!isa<Instruction>(getValue())) o << "\n";
124 for (unsigned i = 0; i < getNumChildren(); ++i)
125 getChild(i)->print(o, Indent+1);
129 template<class Payload>
130 inline std::ostream &operator<<(std::ostream &o,
131 const InstTreeNode<Payload> *N) {
132 N->print(o, 0); return o;
135 //===----------------------------------------------------------------------===//
137 //===----------------------------------------------------------------------===//
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.
143 template<class Payload>
144 class InstForest : public std::vector<InstTreeNode<Payload> *> {
145 friend class InstTreeNode<Payload>;
147 // InstMap - Map contains entries for ALL instructions in the method and the
148 // InstTreeNode that they correspond to.
150 std::map<Instruction*, InstTreeNode<Payload> *> InstMap;
152 void addInstMapping(Instruction *I, InstTreeNode<Payload> *IN) {
153 InstMap.insert(std::make_pair(I, IN));
156 void removeInstFromRootList(Instruction *I) {
157 for (unsigned i = size(); i > 0; --i)
158 if (operator[](i-1)->getValue() == I) {
165 // ctor - Create an instruction forest for the specified method...
166 InstForest(Function *F) {
167 for (Function::iterator MI = F->begin(), ME = F->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));
180 // dtor - Free the trees...
182 for (unsigned i = size(); i > 0; --i)
183 delete operator[](i-1);
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.
190 inline InstTreeNode<Payload> *getInstNode(Instruction *Inst) {
191 std::map<Instruction*, InstTreeNode<Payload> *>::iterator I =
193 if (I != InstMap.end()) return I->second;
196 inline const InstTreeNode<Payload> *getInstNode(const Instruction *Inst)const{
197 std::map<Instruction*, InstTreeNode<Payload>*>::const_iterator I =
199 if (I != InstMap.end()) return I->second;
203 // print - Called by operator<< below...
204 void print(std::ostream &out) const {
205 for (const_iterator I = begin(), E = end(); I != E; ++I)
210 template<class Payload>
211 inline std::ostream &operator<<(std::ostream &o, const InstForest<Payload> &IF){
212 IF.print(o); return o;
216 //===----------------------------------------------------------------------===//
217 // Method Implementations
218 //===----------------------------------------------------------------------===//
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
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();
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.
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
241 if (!isa<Instruction>(V)) {
242 assert((isa<Constant>(V) || isa<BasicBlock>(V) ||
243 isa<FunctionArgument>(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;
250 getTreeData().first.second = TemporaryNode;
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!
263 // Otherwise, we are an internal instruction node. We must process our
264 // uses and add them as children of this node.
266 std::vector<InstTreeNode*> Children;
268 // Make sure that the forest knows about us!
269 IF.addInstMapping(I, this);
271 // Walk the operands of the instruction adding children for all of the uses
272 // of the instruction...
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));
281 // No node for this child yet... create one now!
282 Children.push_back(new InstTreeNode(IF, *OI, this));
286 setChildren(Children);
287 getTreeData().first.second = InstructionNode;
290 } // End namespace analysis