1 //===- llvm/Analysis/InstForest.h - Partition Func into forest --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This interface is used to partition a method into a forest of instruction
11 // trees, where the following invariants hold:
13 // 1. The instructions in a tree are all related to each other through use
15 // 2. All instructions in a tree are members of the same basic block
16 // 3. All instructions in a tree (with the exception of the root), may have only
19 //===----------------------------------------------------------------------===//
21 #ifndef LLVM_ANALYSIS_INSTFOREST_H
22 #define LLVM_ANALYSIS_INSTFOREST_H
24 #include "llvm/Function.h"
25 #include "Support/Tree.h"
30 template<class Payload> class InstTreeNode;
31 template<class Payload> class InstForest;
33 //===----------------------------------------------------------------------===//
35 //===----------------------------------------------------------------------===//
37 // There is an instance of this class for each node in the instruction forest.
38 // There should be a node for every instruction in the tree, as well as
39 // Temporary nodes that correspond to other trees in the forest and to variables
40 // and global variables. Constants have their own special node.
42 template<class Payload>
44 public Tree<InstTreeNode<Payload>,
45 std::pair<std::pair<Value*, char>, Payload> > {
47 friend class InstForest<Payload>;
48 typedef Tree<InstTreeNode<Payload>,
49 std::pair<std::pair<Value*, char>, Payload> > super;
51 // Constants used for the node type value
53 ConstNode = Value::ConstantVal,
54 BasicBlockNode = Value::BasicBlockVal,
55 InstructionNode = Value::InstructionVal,
59 // Helper functions to make accessing our data nicer...
60 const Value *getValue() const { return getTreeData().first.first; }
61 Value *getValue() { return getTreeData().first.first; }
62 enum NodeTypeTy getNodeType() const {
63 return (enum NodeTypeTy)getTreeData().first.second;
66 InstTreeNode(const InstTreeNode &); // Do not implement
67 void operator=(const InstTreeNode &); // Do not implement
69 // Only creatable by InstForest
70 InstTreeNode(InstForest<Payload> &IF, Value *V, InstTreeNode *Parent);
71 bool CanMergeInstIntoTree(Instruction *Inst);
73 // Accessor functions...
74 inline Payload &getData() { return getTreeData().second; }
75 inline const Payload &getData() const { return getTreeData().second; }
77 // Type checking functions...
78 inline bool isConstant() const { return getNodeType() == ConstNode; }
79 inline bool isBasicBlock() const { return getNodeType() == BasicBlockNode; }
80 inline bool isInstruction() const { return getNodeType() == InstructionNode; }
81 inline bool isTemporary() const { return getNodeType() == TemporaryNode; }
83 // Accessors for different node types...
84 inline Constant *getConstant() {
85 return cast<Constant>(getValue());
87 inline const Constant *getConstant() const {
88 return cast<Constant>(getValue());
90 inline BasicBlock *getBasicBlock() {
91 return cast<BasicBlock>(getValue());
93 inline const BasicBlock *getBasicBlock() const {
94 return cast<BasicBlock>(getValue());
96 inline Instruction *getInstruction() {
97 assert(isInstruction() && "getInstruction() on non instruction node!");
98 return cast<Instruction>(getValue());
100 inline const Instruction *getInstruction() const {
101 assert(isInstruction() && "getInstruction() on non instruction node!");
102 return cast<Instruction>(getValue());
104 inline Instruction *getTemporary() {
105 assert(isTemporary() && "getTemporary() on non temporary node!");
106 return cast<Instruction>(getValue());
108 inline const Instruction *getTemporary() const {
109 assert(isTemporary() && "getTemporary() on non temporary node!");
110 return cast<Instruction>(getValue());
114 // print - Called by operator<< below...
115 void print(std::ostream &o, unsigned Indent) const {
116 o << std::string(Indent*2, ' ');
117 switch (getNodeType()) {
118 case ConstNode : o << "Constant : "; break;
119 case BasicBlockNode : o << "BasicBlock : " << getValue()->getName() << "\n";
121 case InstructionNode: o << "Instruction: "; break;
122 case TemporaryNode : o << "Temporary : "; break;
123 default: o << "UNKNOWN NODE TYPE: " << getNodeType() << "\n"; abort();
127 if (!isa<Instruction>(getValue())) o << "\n";
129 for (unsigned i = 0; i < getNumChildren(); ++i)
130 getChild(i)->print(o, Indent+1);
134 template<class Payload>
135 inline std::ostream &operator<<(std::ostream &o,
136 const InstTreeNode<Payload> *N) {
137 N->print(o, 0); return o;
140 //===----------------------------------------------------------------------===//
142 //===----------------------------------------------------------------------===//
144 // This class represents the instruction forest itself. It exposes iterators
145 // to an underlying vector of Instruction Trees. Each root of the tree is
146 // guaranteed to be an instruction node. The constructor builds the forest.
148 template<class Payload>
149 class InstForest : public std::vector<InstTreeNode<Payload> *> {
150 friend class InstTreeNode<Payload>;
152 typedef typename std::vector<InstTreeNode<Payload> *>::const_iterator const_iterator;
154 // InstMap - Map contains entries for ALL instructions in the method and the
155 // InstTreeNode that they correspond to.
157 std::map<Instruction*, InstTreeNode<Payload> *> InstMap;
159 void addInstMapping(Instruction *I, InstTreeNode<Payload> *IN) {
160 InstMap.insert(std::make_pair(I, IN));
163 void removeInstFromRootList(Instruction *I) {
164 for (unsigned i = size(); i > 0; --i)
165 if (operator[](i-1)->getValue() == I) {
172 // ctor - Create an instruction forest for the specified method...
173 InstForest(Function *F) {
174 for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
175 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
176 if (!getInstNode(I)) { // Do we already have a tree for this inst?
177 // No, create one! InstTreeNode ctor automatically adds the
178 // created node into our InstMap
179 push_back(new InstTreeNode<Payload>(*this, I, 0));
183 // dtor - Free the trees...
185 for (unsigned i = size(); i != 0; --i)
186 delete operator[](i-1);
189 // getInstNode - Return the instruction node that corresponds to the specified
190 // instruction... This node may be embeded in a larger tree, in which case
191 // the parent pointer can be used to find the root of the tree.
193 inline InstTreeNode<Payload> *getInstNode(Instruction *Inst) {
194 typename std::map<Instruction*, InstTreeNode<Payload> *>::iterator I =
196 if (I != InstMap.end()) return I->second;
199 inline const InstTreeNode<Payload> *getInstNode(const Instruction *Inst)const{
200 typename std::map<Instruction*, InstTreeNode<Payload>*>::const_iterator I =
202 if (I != InstMap.end()) return I->second;
206 // print - Called by operator<< below...
207 void print(std::ostream &out) const {
208 for (const_iterator I = begin(), E = end(); I != E; ++I)
213 template<class Payload>
214 inline std::ostream &operator<<(std::ostream &o, const InstForest<Payload> &IF){
215 IF.print(o); return o;
219 //===----------------------------------------------------------------------===//
220 // Method Implementations
221 //===----------------------------------------------------------------------===//
223 // CanMergeInstIntoTree - Return true if it is allowed to merge the specified
224 // instruction into 'this' instruction tree. This is allowed iff:
225 // 1. The instruction is in the same basic block as the current one
226 // 2. The instruction has only one use
228 template <class Payload>
229 bool InstTreeNode<Payload>::CanMergeInstIntoTree(Instruction *I) {
230 if (!I->use_empty() && !I->hasOneUse()) return false;
231 return I->getParent() == cast<Instruction>(getValue())->getParent();
235 // InstTreeNode ctor - This constructor creates the instruction tree for the
236 // specified value. If the value is an instruction, it recursively creates the
237 // internal/child nodes and adds them to the instruction forest.
239 template <class Payload>
240 InstTreeNode<Payload>::InstTreeNode(InstForest<Payload> &IF, Value *V,
241 InstTreeNode *Parent) : super(Parent) {
242 getTreeData().first.first = V; // Save tree node
244 if (!isa<Instruction>(V)) {
245 assert((isa<Constant>(V) || isa<BasicBlock>(V) ||
246 isa<Argument>(V) || isa<GlobalValue>(V)) &&
247 "Unrecognized value type for InstForest Partition!");
248 if (isa<Constant>(V))
249 getTreeData().first.second = ConstNode;
250 else if (isa<BasicBlock>(V))
251 getTreeData().first.second = BasicBlockNode;
253 getTreeData().first.second = TemporaryNode;
258 // Must be an instruction then... see if we can include it in this tree!
259 Instruction *I = cast<Instruction>(V);
260 if (Parent && !Parent->CanMergeInstIntoTree(I)) {
261 // Not root node of tree, but mult uses?
262 getTreeData().first.second = TemporaryNode; // Must be a temporary!
266 // Otherwise, we are an internal instruction node. We must process our
267 // uses and add them as children of this node.
269 std::vector<InstTreeNode*> Children;
271 // Make sure that the forest knows about us!
272 IF.addInstMapping(I, this);
274 // Walk the operands of the instruction adding children for all of the uses
275 // of the instruction...
277 for (Instruction::op_iterator OI = I->op_begin(); OI != I->op_end(); ++OI) {
278 Value *Operand = *OI;
279 InstTreeNode<Payload> *IN = IF.getInstNode(dyn_cast<Instruction>(Operand));
280 if (IN && CanMergeInstIntoTree(cast<Instruction>(Operand))) {
281 Children.push_back(IN);
282 IF.removeInstFromRootList(cast<Instruction>(Operand));
284 // No node for this child yet... create one now!
285 Children.push_back(new InstTreeNode(IF, *OI, this));
289 setChildren(Children);
290 getTreeData().first.second = InstructionNode;
293 } // End llvm namespace