-// $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/CodeGen/MachineCodeForInstruction.h"
#include "llvm/Function.h"
#include "llvm/iTerminators.h"
#include "llvm/iMemory.h"
-#include "llvm/iPHINode.h"
-#include "llvm/ConstantVals.h"
-#include "llvm/BasicBlock.h"
+#include "llvm/Constant.h"
+#include "llvm/Type.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "Support/STLExtras.h"
-#include <iostream>
+#include <alloca.h>
using std::cerr;
using std::vector;
{
opLabel = AllocaN; // Alloca(ptr, N) operation
}
- else if ((opLabel == Instruction::Load ||
- opLabel == Instruction::GetElementPtr) &&
- cast<MemAccessInst>(I)->hasIndices())
+ else if (opLabel == Instruction::GetElementPtr &&
+ cast<GetElementPtrInst>(I)->hasIndices())
{
- opLabel = opLabel + 100; // load/getElem with index vector
+ opLabel = opLabel + 100; // getElem with index vector
+ }
+ else if (opLabel == Instruction::Xor &&
+ BinaryOperator::isNot(I))
+ {
+ opLabel = (I->getType() == Type::BoolTy)? NotOp // boolean Not operator
+ : BNotOp; // bitwise Not operator
}
else if (opLabel == Instruction::And ||
opLabel == Instruction::Or ||
- opLabel == Instruction::Xor ||
- opLabel == Instruction::Not)
+ opLabel == Instruction::Xor)
{
// Distinguish bitwise operators from logical operators!
if (I->getType() != Type::BoolTy)
{
for (int i=0; i < indent; i++)
cerr << " ";
-
- cerr << getInstruction()->getOpcodeName();
- const MachineCodeForInstruction &mvec =
- MachineCodeForInstruction::get(getInstruction());
-
- if (mvec.size() > 0)
- cerr << "\tMachine Instructions: ";
-
- for (unsigned int i=0; i < mvec.size(); ++i) {
- mvec[i]->dump(0);
- if (i < mvec.size() - 1)
- cerr << "; ";
- }
-
- cerr << "\n";
+ cerr << getInstruction()->getOpcodeName()
+ << " [label " << getOpLabel() << "]" << "\n";
}
InstrForest::InstrForest(Function *F)
{
- for (Function::iterator FI = F->begin(), FE = F->end(); FI != FE; ++FI) {
- BasicBlock *BB = *FI;
- for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
- 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 (std::hash_map<const Instruction*,InstructionNode*>::iterator I=begin();
- I != end(); ++I)
- delete I->second;
+ for_each(treeRoots.begin(), treeRoots.end(), deleter<InstructionNode>);
}
void
InstrForest::noteTreeNodeForInstr(Instruction *instr,
InstructionNode *treeNode)
{
- assert(treeNode->getNodeType() == InstrTreeNode::NTInstructionNode);
(*this)[instr] = treeNode;
treeRoots.push_back(treeNode); // mark node as root of a new tree
}
{
parent->LeftChild = child;
child->Parent = parent;
- if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
- eraseRoot((InstructionNode*) child); // no longer a tree root
+ if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
+ eraseRoot(instrNode); // no longer a tree root
}
inline void
{
parent->RightChild = child;
child->Parent = parent;
- if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
- eraseRoot((InstructionNode*) child); // no longer a tree root
+ 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
&& !instr->isTerminator();
if (includeAddressOperand || isa<Instruction>(operand) ||
- isa<Constant>(operand) || isa<FunctionArgument>(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.
setRightChild(parent, childArray[numChildren - 1]);
}
- if (childArray != fixedChildArray)
- delete [] childArray;
-
return treeNode;
}
-