-//===- llvm/Analysis/InstForest.h - Partition Method into forest -*- C++ -*--=//
+//===- llvm/Analysis/InstForest.h - Partition Func into forest --*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
//
// This interface is used to partition a method into a forest of instruction
// trees, where the following invariants hold:
#ifndef LLVM_ANALYSIS_INSTFOREST_H
#define LLVM_ANALYSIS_INSTFOREST_H
-#include "llvm/Support/Tree.h"
-#include "llvm/Instruction.h"
+#include "llvm/Function.h"
+#include "Support/Tree.h"
#include <map>
-namespace analysis {
-
-template <class Payload> class InstTreeNode;
-template<class Payload> class InstForest;
+namespace llvm {
+template<class Payload> class InstTreeNode;
+template<class Payload> class InstForest;
//===----------------------------------------------------------------------===//
// Class InstTreeNode
//
template<class Payload>
class InstTreeNode :
- public Tree<InstTreeNode<Payload>, pair<pair<Value*, char>, Payload> > {
+ public Tree<InstTreeNode<Payload>,
+ std::pair<std::pair<Value*, char>, Payload> > {
friend class InstForest<Payload>;
- typedef Tree<InstTreeNode<Payload>, pair<pair<Value*, char>, Payload> > super;
+ typedef Tree<InstTreeNode<Payload>,
+ std::pair<std::pair<Value*, char>, Payload> > super;
// Constants used for the node type value
enum NodeTypeTy {
};
// Helper functions to make accessing our data nicer...
- const Value *getValue() const { return getTreeData().first.first; }
- Value *getValue() { return getTreeData().first.first; }
+ const Value *getValue() const { return this->getTreeData().first.first; }
+ Value *getValue() { return this->getTreeData().first.first; }
enum NodeTypeTy getNodeType() const {
- return (enum NodeTypeTy)getTreeData().first.second;
+ return (enum NodeTypeTy)this->getTreeData().first.second;
}
InstTreeNode(const InstTreeNode &); // Do not implement
bool CanMergeInstIntoTree(Instruction *Inst);
public:
// Accessor functions...
- inline Payload &getData() { return getTreeData().second; }
- inline const Payload &getData() const { return getTreeData().second; }
+ inline Payload &getData() { return this->getTreeData().second; }
+ inline const Payload &getData() const { return this->getTreeData().second; }
// Type checking functions...
inline bool isConstant() const { return getNodeType() == ConstNode; }
inline bool isTemporary() const { return getNodeType() == TemporaryNode; }
// Accessors for different node types...
- inline ConstPoolVal *getConstant() {
- return getValue()->castConstantAsserting();
+ inline Constant *getConstant() {
+ return cast<Constant>(getValue());
}
- inline const ConstPoolVal *getConstant() const {
- return getValue()->castConstantAsserting();
+ inline const Constant *getConstant() const {
+ return cast<Constant>(getValue());
}
inline BasicBlock *getBasicBlock() {
- return getValue()->castBasicBlockAsserting();
+ return cast<BasicBlock>(getValue());
}
inline const BasicBlock *getBasicBlock() const {
- return getValue()->castBasicBlockAsserting();
+ return cast<BasicBlock>(getValue());
}
inline Instruction *getInstruction() {
assert(isInstruction() && "getInstruction() on non instruction node!");
- return getValue()->castInstructionAsserting();
+ return cast<Instruction>(getValue());
}
inline const Instruction *getInstruction() const {
assert(isInstruction() && "getInstruction() on non instruction node!");
- return getValue()->castInstructionAsserting();
+ return cast<Instruction>(getValue());
}
inline Instruction *getTemporary() {
assert(isTemporary() && "getTemporary() on non temporary node!");
- return getValue()->castInstructionAsserting();
+ return cast<Instruction>(getValue());
}
inline const Instruction *getTemporary() const {
assert(isTemporary() && "getTemporary() on non temporary node!");
- return getValue()->castInstructionAsserting();
+ return cast<Instruction>(getValue());
}
public:
// print - Called by operator<< below...
- void print(ostream &o, unsigned Indent) const {
- o << string(Indent*2, ' ');
+ void print(std::ostream &o, unsigned Indent) const {
+ o << std::string(Indent*2, ' ');
switch (getNodeType()) {
case ConstNode : o << "Constant : "; break;
- case BasicBlockNode : o << "BasicBlock : " << getValue()->getName() << endl;
+ case BasicBlockNode : o << "BasicBlock : " << getValue()->getName() << "\n";
return;
case InstructionNode: o << "Instruction: "; break;
case TemporaryNode : o << "Temporary : "; break;
- default: o << "UNKNOWN NODE TYPE: " << getNodeType() << endl; abort();
+ default: o << "UNKNOWN NODE TYPE: " << getNodeType() << "\n"; abort();
}
o << getValue();
- if (!getValue()->isInstruction()) o << "\n";
+ if (!isa<Instruction>(getValue())) o << "\n";
- for (unsigned i = 0; i < getNumChildren(); ++i)
- getChild(i)->print(o, Indent+1);
+ for (unsigned i = 0; i < this->getNumChildren(); ++i)
+ this->getChild(i)->print(o, Indent+1);
}
};
template<class Payload>
-inline ostream &operator<<(ostream &o, const InstTreeNode<Payload> *N) {
+inline std::ostream &operator<<(std::ostream &o,
+ const InstTreeNode<Payload> *N) {
N->print(o, 0); return o;
}
// guaranteed to be an instruction node. The constructor builds the forest.
//
template<class Payload>
-class InstForest : public vector<InstTreeNode<Payload> *> {
+class InstForest : public std::vector<InstTreeNode<Payload> *> {
friend class InstTreeNode<Payload>;
+ typedef typename std::vector<InstTreeNode<Payload> *>::const_iterator const_iterator;
+
// InstMap - Map contains entries for ALL instructions in the method and the
// InstTreeNode that they correspond to.
//
- map<Instruction*, InstTreeNode<Payload> *> InstMap;
+ std::map<Instruction*, InstTreeNode<Payload> *> InstMap;
void addInstMapping(Instruction *I, InstTreeNode<Payload> *IN) {
- InstMap.insert(make_pair(I, IN));
+ InstMap.insert(std::make_pair(I, IN));
}
void removeInstFromRootList(Instruction *I) {
- for (unsigned i = size(); i > 0; --i)
- if (operator[](i-1)->getValue() == I) {
- erase(begin()+i-1);
+ for (unsigned i = this->size(); i > 0; --i)
+ if ((*this)[i-1]->getValue() == I) {
+ this->erase(this->begin()+i-1);
return;
}
}
public:
// ctor - Create an instruction forest for the specified method...
- InstForest(Method *M) {
- for (Method::inst_iterator I = M->inst_begin(), E = M->inst_end();
- I != E; ++I) {
- Instruction *Inst = *I;
- if (!getInstNode(Inst)) // Do we already have a tree for this inst?
- push_back(new InstTreeNode<Payload>(*this, Inst, 0)); // No create one!
- // InstTreeNode ctor automatically adds the created node into our InstMap
- }
+ InstForest(Function *F) {
+ for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
+ if (!getInstNode(I)) { // Do we already have a tree for this inst?
+ // No, create one! InstTreeNode ctor automatically adds the
+ // created node into our InstMap
+ push_back(new InstTreeNode<Payload>(*this, I, 0));
+ }
}
// dtor - Free the trees...
~InstForest() {
- for (unsigned i = size(); i > 0; --i)
- delete operator[](i-1);
+ for (unsigned i = this->size(); i != 0; --i)
+ delete (*this)[i-1];
}
// getInstNode - Return the instruction node that corresponds to the specified
// the parent pointer can be used to find the root of the tree.
//
inline InstTreeNode<Payload> *getInstNode(Instruction *Inst) {
- map<Instruction*, InstTreeNode<Payload> *>::iterator I = InstMap.find(Inst);
+ typename std::map<Instruction*, InstTreeNode<Payload> *>::iterator I =
+ InstMap.find(Inst);
if (I != InstMap.end()) return I->second;
return 0;
}
inline const InstTreeNode<Payload> *getInstNode(const Instruction *Inst)const{
- map<Instruction*, InstTreeNode<Payload>*>::const_iterator I =
+ typename std::map<Instruction*, InstTreeNode<Payload>*>::const_iterator I =
InstMap.find(Inst);
if (I != InstMap.end()) return I->second;
return 0;
}
// print - Called by operator<< below...
- void print(ostream &out) const {
- for (const_iterator I = begin(), E = end(); I != E; ++I)
+ void print(std::ostream &out) const {
+ for (const_iterator I = this->begin(), E = this->end(); I != E; ++I)
out << *I;
}
};
template<class Payload>
-inline ostream &operator<<(ostream &o, const InstForest<Payload> &IF) {
+inline std::ostream &operator<<(std::ostream &o, const InstForest<Payload> &IF){
IF.print(o); return o;
}
//
template <class Payload>
bool InstTreeNode<Payload>::CanMergeInstIntoTree(Instruction *I) {
- if (I->use_size() > 1) return false;
- return I->getParent() == getValue()->castInstructionAsserting()->getParent();
+ if (!I->use_empty() && !I->hasOneUse()) return false;
+ return I->getParent() == cast<Instruction>(getValue())->getParent();
}
template <class Payload>
InstTreeNode<Payload>::InstTreeNode(InstForest<Payload> &IF, Value *V,
InstTreeNode *Parent) : super(Parent) {
- getTreeData().first.first = V; // Save tree node
+ this->getTreeData().first.first = V; // Save tree node
- if (!V->isInstruction()) {
- assert((V->isConstant() || V->isBasicBlock() ||
- V->isMethodArgument() || V->isGlobal()) &&
+ if (!isa<Instruction>(V)) {
+ assert((isa<Constant>(V) || isa<BasicBlock>(V) ||
+ isa<Argument>(V) || isa<GlobalValue>(V)) &&
"Unrecognized value type for InstForest Partition!");
- if (V->isConstant())
- getTreeData().first.second = ConstNode;
- else if (V->isBasicBlock())
- getTreeData().first.second = BasicBlockNode;
+ if (isa<Constant>(V))
+ this->getTreeData().first.second = ConstNode;
+ else if (isa<BasicBlock>(V))
+ this->getTreeData().first.second = BasicBlockNode;
else
- getTreeData().first.second = TemporaryNode;
+ this->getTreeData().first.second = TemporaryNode;
return;
}
// Must be an instruction then... see if we can include it in this tree!
- Instruction *I = V->castInstructionAsserting();
+ Instruction *I = cast<Instruction>(V);
if (Parent && !Parent->CanMergeInstIntoTree(I)) {
// Not root node of tree, but mult uses?
- getTreeData().first.second = TemporaryNode; // Must be a temporary!
+ this->getTreeData().first.second = TemporaryNode; // Must be a temporary!
return;
}
// Otherwise, we are an internal instruction node. We must process our
// uses and add them as children of this node.
//
- vector<InstTreeNode*> Children;
+ std::vector<InstTreeNode*> Children;
// Make sure that the forest knows about us!
IF.addInstMapping(I, this);
//
for (Instruction::op_iterator OI = I->op_begin(); OI != I->op_end(); ++OI) {
Value *Operand = *OI;
- InstTreeNode<Payload> *IN = IF.getInstNode(Operand->castInstruction());
- if (IN && CanMergeInstIntoTree(Operand->castInstructionAsserting())) {
+ InstTreeNode<Payload> *IN = IF.getInstNode(dyn_cast<Instruction>(Operand));
+ if (IN && CanMergeInstIntoTree(cast<Instruction>(Operand))) {
Children.push_back(IN);
- IF.removeInstFromRootList(Operand->castInstructionAsserting());
+ IF.removeInstFromRootList(cast<Instruction>(Operand));
} else {
// No node for this child yet... create one now!
Children.push_back(new InstTreeNode(IF, *OI, this));
}
setChildren(Children);
- getTreeData().first.second = InstructionNode;
+ this->getTreeData().first.second = InstructionNode;
}
-} // End namespace analysis
-
+} // End llvm namespace
#endif