-// $Id$
-//---------------------------------------------------------------------------
-// File:
-// InstrForest.cpp
-//
-// Purpose:
-// Convert SSA graph to instruction trees for instruction selection.
-//
-// Strategy:
+//===-- InstrForest.cpp - Build instruction forest for inst selection -----===//
+//
// The key goal is to group instructions into a single
// tree if one or more of them might be potentially combined into a single
// complex instruction in the target machine.
// and (2) O and I are part of the same basic block,
// and (3) O has only a single use, viz., I.
//
-// History:
-// 6/28/01 - Vikram Adve - Created
-//
-//---------------------------------------------------------------------------
+//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/InstrForest.h"
-#include "llvm/Method.h"
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/Function.h"
#include "llvm/iTerminators.h"
#include "llvm/iMemory.h"
-#include "llvm/iOther.h"
-#include "llvm/ConstPoolVals.h"
-#include "llvm/BasicBlock.h"
+#include "llvm/Constant.h"
+#include "llvm/Type.h"
#include "llvm/CodeGen/MachineInstr.h"
-#include "llvm/Support/STLExtras.h"
+#include "Support/STLExtras.h"
+#include <alloca.h>
+using std::cerr;
+using std::vector;
//------------------------------------------------------------------------
// class InstrTreeNode
InstructionNode::InstructionNode(Instruction* I)
- : InstrTreeNode(NTInstructionNode, I)
+ : InstrTreeNode(NTInstructionNode, I),
+ codeIsFoldedIntoParent(false)
{
opLabel = I->getOpcode();
{
opLabel = AllocaN; // Alloca(ptr, N) operation
}
- else if ((opLabel == Instruction::Load ||
- opLabel == Instruction::GetElementPtr) &&
- ((MemAccessInst*)I)->getFirstOffsetIdx() > 0)
+ else if (opLabel == Instruction::GetElementPtr &&
+ cast<GetElementPtrInst>(I)->hasIndices())
+ {
+ opLabel = opLabel + 100; // getElem with index vector
+ }
+ else if (opLabel == Instruction::Xor &&
+ BinaryOperator::isNot(I))
{
- opLabel = opLabel + 100; // load/getElem with index vector
+ opLabel = (I->getType() == Type::BoolTy)? NotOp // boolean Not operator
+ : BNotOp; // bitwise Not operator
+ }
+ else if (opLabel == Instruction::And ||
+ opLabel == Instruction::Or ||
+ opLabel == Instruction::Xor)
+ {
+ // Distinguish bitwise operators from logical operators!
+ if (I->getType() != Type::BoolTy)
+ opLabel = opLabel + 100; // bitwise operator
}
else if (opLabel == Instruction::Cast)
{
InstructionNode::dumpNode(int indent) const
{
for (int i=0; i < indent; i++)
- cout << " ";
-
- cout << getInstruction()->getOpcodeName();
-
- const vector<MachineInstr*> &mvec = getInstruction()->getMachineInstrVec();
- if (mvec.size() > 0)
- cout << "\tMachine Instructions: ";
- for (unsigned int i=0; i < mvec.size(); i++)
- {
- mvec[i]->dump(0);
- if (i < mvec.size() - 1)
- cout << "; ";
- }
-
- cout << endl;
+ cerr << " ";
+ cerr << getInstruction()->getOpcodeName()
+ << " [label " << getOpLabel() << "]" << "\n";
}
VRegListNode::dumpNode(int indent) const
{
for (int i=0; i < indent; i++)
- cout << " ";
+ cerr << " ";
- cout << "List" << endl;
+ cerr << "List" << "\n";
}
VRegNode::dumpNode(int indent) const
{
for (int i=0; i < indent; i++)
- cout << " ";
+ cerr << " ";
- cout << "VReg " << getValue() << "\t(type "
- << (int) getValue()->getValueType() << ")" << endl;
+ cerr << "VReg " << getValue() << "\t(type "
+ << (int) getValue()->getValueType() << ")" << "\n";
}
void
ConstantNode::dumpNode(int indent) const
{
for (int i=0; i < indent; i++)
- cout << " ";
+ cerr << " ";
- cout << "Constant " << getValue() << "\t(type "
- << (int) getValue()->getValueType() << ")" << endl;
+ cerr << "Constant " << getValue() << "\t(type "
+ << (int) getValue()->getValueType() << ")" << "\n";
}
void
LabelNode::dumpNode(int indent) const
{
for (int i=0; i < indent; i++)
- cout << " ";
+ cerr << " ";
- cout << "Label " << getValue() << endl;
+ cerr << "Label " << getValue() << "\n";
}
//------------------------------------------------------------------------
// A forest of instruction trees, usually for a single method.
//------------------------------------------------------------------------
-InstrForest::InstrForest(Method *M)
+InstrForest::InstrForest(Function *F)
{
- for (Method::inst_iterator I = M->inst_begin(); I != M->inst_end(); ++I)
- this->buildTreeForInstruction(*I);
+ for (Function::iterator BB = F->begin(), FE = F->end(); BB != FE; ++BB) {
+ for(BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
+ buildTreeForInstruction(I);
+ }
}
InstrForest::~InstrForest()
{
- for (hash_map<const Instruction*, InstructionNode*>:: iterator I = begin();
- I != end(); ++I)
- delete (*I).second;
+ for_each(treeRoots.begin(), treeRoots.end(), deleter<InstructionNode>);
}
void
InstrForest::dump() const
{
- for (hash_set<InstructionNode*>::const_iterator I = treeRoots.begin();
- I != treeRoots.end(); ++I)
+ for (const_root_iterator I = roots_begin(); I != roots_end(); ++I)
(*I)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
}
+inline void
+InstrForest::eraseRoot(InstructionNode* node)
+{
+ for (RootSet::reverse_iterator RI=treeRoots.rbegin(), RE=treeRoots.rend();
+ RI != RE; ++RI)
+ if (*RI == node)
+ treeRoots.erase(RI.base()-1);
+}
+
inline void
InstrForest::noteTreeNodeForInstr(Instruction *instr,
InstructionNode *treeNode)
{
- assert(treeNode->getNodeType() == InstrTreeNode::NTInstructionNode);
(*this)[instr] = treeNode;
- treeRoots.insert(treeNode); // mark node as root of a new tree
+ treeRoots.push_back(treeNode); // mark node as root of a new tree
}
inline void
-InstrForest::setLeftChild(InstrTreeNode *Par, InstrTreeNode *Chld)
+InstrForest::setLeftChild(InstrTreeNode *parent, InstrTreeNode *child)
{
- Par->LeftChild = Chld;
- Chld->Parent = Par;
- if (Chld->getNodeType() == InstrTreeNode::NTInstructionNode)
- treeRoots.erase((InstructionNode*)Chld); // no longer a tree root
+ parent->LeftChild = child;
+ child->Parent = parent;
+ if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
+ eraseRoot(instrNode); // no longer a tree root
}
inline void
-InstrForest::setRightChild(InstrTreeNode *Par, InstrTreeNode *Chld)
+InstrForest::setRightChild(InstrTreeNode *parent, InstrTreeNode *child)
{
- Par->RightChild = Chld;
- Chld->Parent = Par;
- if (Chld->getNodeType() == InstrTreeNode::NTInstructionNode)
- treeRoots.erase((InstructionNode*)Chld); // no longer a tree root
+ parent->RightChild = child;
+ child->Parent = parent;
+ if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
+ eraseRoot(instrNode); // no longer a tree root
}
// if a fixed array is too small.
//
int numChildren = 0;
- const unsigned int MAX_CHILD = 8;
- static InstrTreeNode *fixedChildArray[MAX_CHILD];
InstrTreeNode **childArray =
- (instr->getNumOperands() > MAX_CHILD)
- ? new (InstrTreeNode*)[instr->getNumOperands()] : fixedChildArray;
+ (InstrTreeNode **)alloca(instr->getNumOperands()*sizeof(InstrTreeNode *));
//
// Walk the operands of the instruction
// Check latter condition here just to simplify the next IF.
bool includeAddressOperand =
- (isa<BasicBlock>(operand) || isa<Method>(operand))
+ (isa<BasicBlock>(operand) || isa<Function>(operand))
&& !instr->isTerminator();
if (includeAddressOperand || isa<Instruction>(operand) ||
- isa<ConstPoolVal>(operand) || isa<MethodArgument>(operand) ||
+ isa<Constant>(operand) || isa<Argument>(operand) ||
isa<GlobalVariable>(operand))
{
// This operand is a data value
InstrTreeNode* opTreeNode;
if (isa<Instruction>(operand) && operand->use_size() == 1 &&
cast<Instruction>(operand)->getParent() == instr->getParent() &&
- !isa<PHINode>(instr) &&
+ instr->getOpcode() != Instruction::PHINode &&
instr->getOpcode() != Instruction::Call)
{
// Recursively create a treeNode for it.
opTreeNode = buildTreeForInstruction((Instruction*)operand);
}
- else if (ConstPoolVal *CPV = dyn_cast<ConstPoolVal>(operand))
+ else if (Constant *CPV = dyn_cast<Constant>(operand))
{
// Create a leaf node for a constant
opTreeNode = new ConstantNode(CPV);
setRightChild(parent, childArray[numChildren - 1]);
}
- if (childArray != fixedChildArray)
- delete [] childArray;
-
return treeNode;
}
-
projects / oota-llvm.git / blobdiff