aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMisha Brukman <brukman+llvm@gmail.com>2003-10-23 17:39:37 +0000
committerMisha Brukman <brukman+llvm@gmail.com>2003-10-23 17:39:37 +0000
commit5e152593e05f93882b1f5ee46288d19d24544e4b (patch)
tree6b4ee4db746d6f9e63bf75174341619f509a0859
parenteea7cca3663393bc218089139ec8df6302863203 (diff)
Make code layout more consistent.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9426 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--lib/CodeGen/InstrSelection/InstrForest.cpp304
-rw-r--r--lib/CodeGen/InstrSelection/InstrSelection.cpp166
-rw-r--r--lib/CodeGen/InstrSelection/InstrSelectionSupport.cpp107
-rw-r--r--lib/Target/SparcV9/InstrSelection/InstrForest.cpp304
-rw-r--r--lib/Target/SparcV9/InstrSelection/InstrSelection.cpp166
-rw-r--r--lib/Target/SparcV9/InstrSelection/InstrSelectionSupport.cpp107
6 files changed, 518 insertions, 636 deletions
diff --git a/lib/CodeGen/InstrSelection/InstrForest.cpp b/lib/CodeGen/InstrSelection/InstrForest.cpp
index 90993b7a8d..5496502d5e 100644
--- a/lib/CodeGen/InstrSelection/InstrForest.cpp
+++ b/lib/CodeGen/InstrSelection/InstrForest.cpp
@@ -19,13 +19,13 @@
//
//===----------------------------------------------------------------------===//
-#include "llvm/CodeGen/InstrForest.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/Constant.h"
#include "llvm/Function.h"
#include "llvm/iTerminators.h"
#include "llvm/iMemory.h"
-#include "llvm/Constant.h"
#include "llvm/Type.h"
+#include "llvm/CodeGen/InstrForest.h"
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "Support/STLExtras.h"
#include "Config/alloca.h"
@@ -35,102 +35,82 @@
//------------------------------------------------------------------------
void
-InstrTreeNode::dump(int dumpChildren, int indent) const
-{
+InstrTreeNode::dump(int dumpChildren, int indent) const {
dumpNode(indent);
- if (dumpChildren)
- {
- if (LeftChild)
- LeftChild->dump(dumpChildren, indent+1);
- if (RightChild)
- RightChild->dump(dumpChildren, indent+1);
- }
+ if (dumpChildren) {
+ if (LeftChild)
+ LeftChild->dump(dumpChildren, indent+1);
+ if (RightChild)
+ RightChild->dump(dumpChildren, indent+1);
+ }
}
InstructionNode::InstructionNode(Instruction* I)
- : InstrTreeNode(NTInstructionNode, I),
- codeIsFoldedIntoParent(false)
+ : InstrTreeNode(NTInstructionNode, I), codeIsFoldedIntoParent(false)
{
opLabel = I->getOpcode();
// Distinguish special cases of some instructions such as Ret and Br
//
- if (opLabel == Instruction::Ret && cast<ReturnInst>(I)->getReturnValue())
- {
- opLabel = RetValueOp; // ret(value) operation
- }
+ if (opLabel == Instruction::Ret && cast<ReturnInst>(I)->getReturnValue()) {
+ opLabel = RetValueOp; // ret(value) operation
+ }
else if (opLabel ==Instruction::Br && !cast<BranchInst>(I)->isUnconditional())
+ {
+ opLabel = BrCondOp; // br(cond) operation
+ } else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT) {
+ opLabel = SetCCOp; // common label for all SetCC ops
+ } else if (opLabel == Instruction::Alloca && I->getNumOperands() > 0) {
+ opLabel = AllocaN; // Alloca(ptr, N) operation
+ } 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 = (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) {
+ const Type *ITy = I->getType();
+ switch(ITy->getPrimitiveID())
{
- opLabel = BrCondOp; // br(cond) operation
- }
- else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT)
- {
- opLabel = SetCCOp; // common label for all SetCC ops
- }
- else if (opLabel == Instruction::Alloca && I->getNumOperands() > 0)
- {
- opLabel = AllocaN; // Alloca(ptr, N) operation
- }
- 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 = (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)
- {
- const Type *ITy = I->getType();
- switch(ITy->getPrimitiveID())
- {
- case Type::BoolTyID: opLabel = ToBoolTy; break;
- case Type::UByteTyID: opLabel = ToUByteTy; break;
- case Type::SByteTyID: opLabel = ToSByteTy; break;
- case Type::UShortTyID: opLabel = ToUShortTy; break;
- case Type::ShortTyID: opLabel = ToShortTy; break;
- case Type::UIntTyID: opLabel = ToUIntTy; break;
- case Type::IntTyID: opLabel = ToIntTy; break;
- case Type::ULongTyID: opLabel = ToULongTy; break;
- case Type::LongTyID: opLabel = ToLongTy; break;
- case Type::FloatTyID: opLabel = ToFloatTy; break;
- case Type::DoubleTyID: opLabel = ToDoubleTy; break;
- case Type::ArrayTyID: opLabel = ToArrayTy; break;
- case Type::PointerTyID: opLabel = ToPointerTy; break;
- default:
- // Just use `Cast' opcode otherwise. It's probably ignored.
- break;
- }
+ case Type::BoolTyID: opLabel = ToBoolTy; break;
+ case Type::UByteTyID: opLabel = ToUByteTy; break;
+ case Type::SByteTyID: opLabel = ToSByteTy; break;
+ case Type::UShortTyID: opLabel = ToUShortTy; break;
+ case Type::ShortTyID: opLabel = ToShortTy; break;
+ case Type::UIntTyID: opLabel = ToUIntTy; break;
+ case Type::IntTyID: opLabel = ToIntTy; break;
+ case Type::ULongTyID: opLabel = ToULongTy; break;
+ case Type::LongTyID: opLabel = ToLongTy; break;
+ case Type::FloatTyID: opLabel = ToFloatTy; break;
+ case Type::DoubleTyID: opLabel = ToDoubleTy; break;
+ case Type::ArrayTyID: opLabel = ToArrayTy; break;
+ case Type::PointerTyID: opLabel = ToPointerTy; break;
+ default:
+ // Just use `Cast' opcode otherwise. It's probably ignored.
+ break;
}
+ }
}
void
-InstructionNode::dumpNode(int indent) const
-{
+InstructionNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
std::cerr << getInstruction()->getOpcodeName()
<< " [label " << getOpLabel() << "]" << "\n";
}
-
void
-VRegListNode::dumpNode(int indent) const
-{
+VRegListNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
@@ -139,8 +119,7 @@ VRegListNode::dumpNode(int indent) const
void
-VRegNode::dumpNode(int indent) const
-{
+VRegNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
@@ -149,8 +128,7 @@ VRegNode::dumpNode(int indent) const
}
void
-ConstantNode::dumpNode(int indent) const
-{
+ConstantNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
@@ -158,9 +136,7 @@ ConstantNode::dumpNode(int indent) const
<< (int) getValue()->getValueType() << ")" << "\n";
}
-void
-LabelNode::dumpNode(int indent) const
-{
+void LabelNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
@@ -173,56 +149,46 @@ LabelNode::dumpNode(int indent) const
// A forest of instruction trees, usually for a single method.
//------------------------------------------------------------------------
-InstrForest::InstrForest(Function *F)
-{
+InstrForest::InstrForest(Function *F) {
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()
-{
+InstrForest::~InstrForest() {
for_each(treeRoots.begin(), treeRoots.end(), deleter<InstructionNode>);
}
-void
-InstrForest::dump() const
-{
+void InstrForest::dump() const {
for (const_root_iterator I = roots_begin(); I != roots_end(); ++I)
(*I)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
}
-inline void
-InstrForest::eraseRoot(InstructionNode* node)
-{
+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)
-{
+inline void InstrForest::noteTreeNodeForInstr(Instruction *instr,
+ InstructionNode *treeNode) {
(*this)[instr] = treeNode;
treeRoots.push_back(treeNode); // mark node as root of a new tree
}
-inline void
-InstrForest::setLeftChild(InstrTreeNode *parent, InstrTreeNode *child)
-{
+inline void InstrForest::setLeftChild(InstrTreeNode *parent,
+ InstrTreeNode *child) {
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 *parent, InstrTreeNode *child)
-{
+inline void InstrForest::setRightChild(InstrTreeNode *parent,
+ InstrTreeNode *child) {
parent->RightChild = child;
child->Parent = parent;
if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
@@ -230,26 +196,23 @@ InstrForest::setRightChild(InstrTreeNode *parent, InstrTreeNode *child)
}
-InstructionNode*
-InstrForest::buildTreeForInstruction(Instruction *instr)
-{
+InstructionNode* InstrForest::buildTreeForInstruction(Instruction *instr) {
InstructionNode *treeNode = getTreeNodeForInstr(instr);
- if (treeNode)
- {
- // treeNode has already been constructed for this instruction
- assert(treeNode->getInstruction() == instr);
- return treeNode;
- }
+ if (treeNode) {
+ // treeNode has already been constructed for this instruction
+ assert(treeNode->getInstruction() == instr);
+ return treeNode;
+ }
// Otherwise, create a new tree node for this instruction.
//
treeNode = new InstructionNode(instr);
noteTreeNodeForInstr(instr, treeNode);
- if (instr->getOpcode() == Instruction::Call)
- { // Operands of call instruction
- return treeNode;
- }
+ if (instr->getOpcode() == Instruction::Call) {
+ // Operands of call instruction
+ return treeNode;
+ }
// If the instruction has more than 2 instruction operands,
// then we need to create artificial list nodes to hold them.
@@ -285,46 +248,42 @@ InstrForest::buildTreeForInstruction(Instruction *instr)
if (includeAddressOperand || isa<Instruction>(operand) ||
isa<Constant>(operand) || isa<Argument>(operand) ||
isa<GlobalVariable>(operand))
- {
- // This operand is a data value
+ {
+ // This operand is a data value
- // An instruction that computes the incoming value is added as a
- // child of the current instruction if:
- // the value has only a single use
- // AND both instructions are in the same basic block.
- // AND the current instruction is not a PHI (because the incoming
- // value is conceptually in a predecessor block,
- // even though it may be in the same static block)
- //
- // (Note that if the value has only a single use (viz., `instr'),
- // the def of the value can be safely moved just before instr
- // and therefore it is safe to combine these two instructions.)
- //
- // In all other cases, the virtual register holding the value
- // is used directly, i.e., made a child of the instruction node.
- //
- InstrTreeNode* opTreeNode;
- if (isa<Instruction>(operand) && operand->hasOneUse() &&
- cast<Instruction>(operand)->getParent() == instr->getParent() &&
- instr->getOpcode() != Instruction::PHI &&
- instr->getOpcode() != Instruction::Call)
- {
- // Recursively create a treeNode for it.
- opTreeNode = buildTreeForInstruction((Instruction*)operand);
- }
- else if (Constant *CPV = dyn_cast<Constant>(operand))
- {
- // Create a leaf node for a constant
- opTreeNode = new ConstantNode(CPV);
- }
- else
- {
- // Create a leaf node for the virtual register
- opTreeNode = new VRegNode(operand);
- }
+ // An instruction that computes the incoming value is added as a
+ // child of the current instruction if:
+ // the value has only a single use
+ // AND both instructions are in the same basic block.
+ // AND the current instruction is not a PHI (because the incoming
+ // value is conceptually in a predecessor block,
+ // even though it may be in the same static block)
+ //
+ // (Note that if the value has only a single use (viz., `instr'),
+ // the def of the value can be safely moved just before instr
+ // and therefore it is safe to combine these two instructions.)
+ //
+ // In all other cases, the virtual register holding the value
+ // is used directly, i.e., made a child of the instruction node.
+ //
+ InstrTreeNode* opTreeNode;
+ if (isa<Instruction>(operand) && operand->hasOneUse() &&
+ cast<Instruction>(operand)->getParent() == instr->getParent() &&
+ instr->getOpcode() != Instruction::PHI &&
+ instr->getOpcode() != Instruction::Call)
+ {
+ // Recursively create a treeNode for it.
+ opTreeNode = buildTreeForInstruction((Instruction*)operand);
+ } else if (Constant *CPV = dyn_cast<Constant>(operand)) {
+ // Create a leaf node for a constant
+ opTreeNode = new ConstantNode(CPV);
+ } else {
+ // Create a leaf node for the virtual register
+ opTreeNode = new VRegNode(operand);
+ }
- childArray[numChildren++] = opTreeNode;
- }
+ childArray[numChildren++] = opTreeNode;
+ }
}
//--------------------------------------------------------------------
@@ -338,15 +297,14 @@ InstrForest::buildTreeForInstruction(Instruction *instr)
InstrTreeNode *parent = treeNode;
- if (numChildren > 2)
- {
- unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
- assert(instrOpcode == Instruction::PHI ||
- instrOpcode == Instruction::Call ||
- instrOpcode == Instruction::Load ||
- instrOpcode == Instruction::Store ||
- instrOpcode == Instruction::GetElementPtr);
- }
+ if (numChildren > 2) {
+ unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
+ assert(instrOpcode == Instruction::PHI ||
+ instrOpcode == Instruction::Call ||
+ instrOpcode == Instruction::Load ||
+ instrOpcode == Instruction::Store ||
+ instrOpcode == Instruction::GetElementPtr);
+ }
// Insert the first child as a direct child
if (numChildren >= 1)
@@ -355,21 +313,19 @@ InstrForest::buildTreeForInstruction(Instruction *instr)
int n;
// Create a list node for children 2 .. N-1, if any
- for (n = numChildren-1; n >= 2; n--)
- {
- // We have more than two children
- InstrTreeNode *listNode = new VRegListNode();
- setRightChild(parent, listNode);
- setLeftChild(listNode, childArray[numChildren - n]);
- parent = listNode;
- }
+ for (n = numChildren-1; n >= 2; n--) {
+ // We have more than two children
+ InstrTreeNode *listNode = new VRegListNode();
+ setRightChild(parent, listNode);
+ setLeftChild(listNode, childArray[numChildren - n]);
+ parent = listNode;
+ }
// Now insert the last remaining child (if any).
- if (numChildren >= 2)
- {
- assert(n == 1);
- setRightChild(parent, childArray[numChildren - 1]);
- }
+ if (numChildren >= 2) {
+ assert(n == 1);
+ setRightChild(parent, childArray[numChildren - 1]);
+ }
delete [] childArray;
return treeNode;
diff --git a/lib/CodeGen/InstrSelection/InstrSelection.cpp b/lib/CodeGen/InstrSelection/InstrSelection.cpp
index 32dc65e6e1..0e3e2cdbf2 100644
--- a/lib/CodeGen/InstrSelection/InstrSelection.cpp
+++ b/lib/CodeGen/InstrSelection/InstrSelection.cpp
@@ -14,19 +14,19 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/Function.h"
+#include "llvm/iPHINode.h"
+#include "llvm/Pass.h"
+#include "llvm/CodeGen/InstrForest.h"
#include "llvm/CodeGen/InstrSelection.h"
#include "llvm/CodeGen/InstrSelectionSupport.h"
-#include "llvm/CodeGen/InstrForest.h"
#include "llvm/CodeGen/MachineCodeForInstruction.h"
#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/Target/TargetRegInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/Function.h"
-#include "llvm/iPHINode.h"
-#include "llvm/Pass.h"
+#include "llvm/Target/TargetRegInfo.h"
#include "Support/CommandLine.h"
#include "Support/LeakDetector.h"
-using std::vector;
+#include <vector>
std::vector<MachineInstr*>
FixConstantOperandsForInstr(Instruction* vmInstr, MachineInstr* minstr,
@@ -66,7 +66,7 @@ namespace {
TargetMachine &Target;
void InsertCodeForPhis(Function &F);
void InsertPhiElimInstructions(BasicBlock *BB,
- const vector<MachineInstr*>& CpVec);
+ const std::vector<MachineInstr*>& CpVec);
void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt);
void PostprocessMachineCodeForTree(InstructionNode* instrNode,
int ruleForNode, short* nts);
@@ -89,9 +89,8 @@ TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
mcfi.addTemp(this);
Operands.push_back(Use(s1, this)); // s1 must be non-null
- if (s2) {
+ if (s2)
Operands.push_back(Use(s2, this));
- }
// TmpInstructions should not be garbage checked.
LeakDetector::removeGarbageObject(this);
@@ -106,8 +105,10 @@ TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
{
mcfi.addTemp(this);
- if (s1) { Operands.push_back(Use(s1, this)); }
- if (s2) { Operands.push_back(Use(s2, this)); }
+ if (s1)
+ Operands.push_back(Use(s1, this));
+ if (s2)
+ Operands.push_back(Use(s2, this));
// TmpInstructions should not be garbage checked.
LeakDetector::removeGarbageObject(this);
@@ -121,37 +122,34 @@ bool InstructionSelection::runOnFunction(Function &F)
//
InstrForest instrForest(&F);
- if (SelectDebugLevel >= Select_DebugInstTrees)
- {
- std::cerr << "\n\n*** Input to instruction selection for function "
- << F.getName() << "\n\n" << F
- << "\n\n*** Instruction trees for function "
- << F.getName() << "\n\n";
- instrForest.dump();
- }
+ if (SelectDebugLevel >= Select_DebugInstTrees) {
+ std::cerr << "\n\n*** Input to instruction selection for function "
+ << F.getName() << "\n\n" << F
+ << "\n\n*** Instruction trees for function "
+ << F.getName() << "\n\n";
+ instrForest.dump();
+ }
//
// Invoke BURG instruction selection for each tree
//
for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
- RI != instrForest.roots_end(); ++RI)
- {
- InstructionNode* basicNode = *RI;
- assert(basicNode->parent() == NULL && "A `root' node has a parent?");
-
- // Invoke BURM to label each tree node with a state
- burm_label(basicNode);
+ RI != instrForest.roots_end(); ++RI) {
+ InstructionNode* basicNode = *RI;
+ assert(basicNode->parent() == NULL && "A `root' node has a parent?");
- if (SelectDebugLevel >= Select_DebugBurgTrees)
- {
- printcover(basicNode, 1, 0);
- std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
- printMatches(basicNode);
- }
+ // Invoke BURM to label each tree node with a state
+ burm_label(basicNode);
- // Then recursively walk the tree to select instructions
- SelectInstructionsForTree(basicNode, /*goalnt*/1);
+ if (SelectDebugLevel >= Select_DebugBurgTrees) {
+ printcover(basicNode, 1, 0);
+ std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
+ printMatches(basicNode);
}
+
+ // Then recursively walk the tree to select instructions
+ SelectInstructionsForTree(basicNode, /*goalnt*/1);
+ }
//
// Create the MachineBasicBlock records and add all of the MachineInstrs
@@ -172,11 +170,10 @@ bool InstructionSelection::runOnFunction(Function &F)
// Insert phi elimination code
InsertCodeForPhis(F);
- if (SelectDebugLevel >= Select_PrintMachineCode)
- {
- std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
- MachineFunction::get(&F).dump();
- }
+ if (SelectDebugLevel >= Select_PrintMachineCode) {
+ std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
+ MachineFunction::get(&F).dump();
+ }
return true;
}
@@ -187,8 +184,7 @@ bool InstructionSelection::runOnFunction(Function &F)
//-------------------------------------------------------------------------
void
-InstructionSelection::InsertCodeForPhis(Function &F)
-{
+InstructionSelection::InsertCodeForPhis(Function &F) {
// for all basic blocks in function
//
MachineFunction &MF = MachineFunction::get(&F);
@@ -207,12 +203,12 @@ InstructionSelection::InsertCodeForPhis(Function &F)
//
for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
// insert the copy instruction to the predecessor BB
- vector<MachineInstr*> mvec, CpVec;
+ std::vector<MachineInstr*> mvec, CpVec;
Target.getRegInfo().cpValue2Value(PN->getIncomingValue(i), PhiCpRes,
mvec);
- for (vector<MachineInstr*>::iterator MI=mvec.begin();
+ for (std::vector<MachineInstr*>::iterator MI=mvec.begin();
MI != mvec.end(); ++MI) {
- vector<MachineInstr*> CpVec2 =
+ std::vector<MachineInstr*> CpVec2 =
FixConstantOperandsForInstr(const_cast<PHINode*>(PN), *MI, Target);
CpVec2.push_back(*MI);
CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
@@ -221,7 +217,7 @@ InstructionSelection::InsertCodeForPhis(Function &F)
InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
}
- vector<MachineInstr*> mvec;
+ std::vector<MachineInstr*> mvec;
Target.getRegInfo().cpValue2Value(PhiCpRes, const_cast<PHINode*>(PN),
mvec);
BB->insert(BB->begin(), mvec.begin(), mvec.end());
@@ -236,7 +232,7 @@ InstructionSelection::InsertCodeForPhis(Function &F)
void
InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB,
- const vector<MachineInstr*>& CpVec)
+ const std::vector<MachineInstr*>& CpVec)
{
Instruction *TermInst = (Instruction*)BB->getTerminator();
MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
@@ -304,50 +300,47 @@ InstructionSelection::SelectInstructionsForTree(InstrTreeNode* treeRoot,
// (If this is a list node, not an instruction, then skip this step).
// This function is specific to the target architecture.
//
- if (treeRoot->opLabel != VRegListOp)
- {
- vector<MachineInstr*> minstrVec;
+ if (treeRoot->opLabel != VRegListOp) {
+ std::vector<MachineInstr*> minstrVec;
- InstructionNode* instrNode = (InstructionNode*)treeRoot;
- assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
+ InstructionNode* instrNode = (InstructionNode*)treeRoot;
+ assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
- GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
+ GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
- MachineCodeForInstruction &mvec =
- MachineCodeForInstruction::get(instrNode->getInstruction());
- mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
- }
+ MachineCodeForInstruction &mvec =
+ MachineCodeForInstruction::get(instrNode->getInstruction());
+ mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
+ }
// Then, recursively compile the child nodes, if any.
//
- if (nts[0])
- { // i.e., there is at least one kid
- InstrTreeNode* kids[2];
- int currentRule = ruleForNode;
- burm_kids(treeRoot, currentRule, kids);
+ if (nts[0]) {
+ // i.e., there is at least one kid
+ InstrTreeNode* kids[2];
+ int currentRule = ruleForNode;
+ burm_kids(treeRoot, currentRule, kids);
- // First skip over any chain rules so that we don't visit
- // the current node again.
- //
- while (ThisIsAChainRule(currentRule))
- {
- currentRule = burm_rule(treeRoot->state, nts[0]);
- nts = burm_nts[currentRule];
- burm_kids(treeRoot, currentRule, kids);
- }
+ // First skip over any chain rules so that we don't visit
+ // the current node again.
+ //
+ while (ThisIsAChainRule(currentRule)) {
+ currentRule = burm_rule(treeRoot->state, nts[0]);
+ nts = burm_nts[currentRule];
+ burm_kids(treeRoot, currentRule, kids);
+ }
- // Now we have the first non-chain rule so we have found
- // the actual child nodes. Recursively compile them.
- //
- for (unsigned i = 0; nts[i]; i++)
- {
- assert(i < 2);
- InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
- if (nodeType == InstrTreeNode::NTVRegListNode ||
- nodeType == InstrTreeNode::NTInstructionNode)
- SelectInstructionsForTree(kids[i], nts[i]);
- }
+ // Now we have the first non-chain rule so we have found
+ // the actual child nodes. Recursively compile them.
+ //
+ for (unsigned i = 0; nts[i]; i++) {
+ assert(i < 2);
+ InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
+ if (nodeType == InstrTreeNode::NTVRegListNode ||
+ nodeType == InstrTreeNode::NTInstructionNode)
+ SelectInstructionsForTree(kids[i], nts[i]);
}
+ }
// Finally, do any post-processing on this node after its children
// have been translated
@@ -373,13 +366,12 @@ InstructionSelection::PostprocessMachineCodeForTree(InstructionNode* instrNode,
//
Instruction* vmInstr = instrNode->getInstruction();
MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
- for (unsigned i = mvec.size(); i != 0; --i)
- {
- vector<MachineInstr*> loadConstVec =
- FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
+ for (unsigned i = mvec.size(); i != 0; --i) {
+ std::vector<MachineInstr*> loadConstVec =
+ FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
- mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
- }
+ mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
+ }
}
diff --git a/lib/CodeGen/InstrSelection/InstrSelectionSupport.cpp b/lib/CodeGen/InstrSelection/InstrSelectionSupport.cpp
index f177e460b1..93f7618641 100644
--- a/lib/CodeGen/InstrSelection/InstrSelectionSupport.cpp
+++ b/lib/CodeGen/InstrSelection/InstrSelectionSupport.cpp
@@ -66,17 +66,14 @@ ChooseRegOrImmed(int64_t intValue,
getImmedValue = 0;
if (canUseImmed &&
- target.getInstrInfo().constantFitsInImmedField(opCode, intValue))
- {
+ target.getInstrInfo().constantFitsInImmedField(opCode, intValue)) {
opType = isSigned? MachineOperand::MO_SignExtendedImmed
: MachineOperand::MO_UnextendedImmed;
getImmedValue = intValue;
- }
- else if (intValue == 0 && target.getRegInfo().getZeroRegNum() >= 0)
- {
- opType = MachineOperand::MO_MachineRegister;
- getMachineRegNum = target.getRegInfo().getZeroRegNum();
- }
+ } else if (intValue == 0 && target.getRegInfo().getZeroRegNum() >= 0) {
+ opType = MachineOperand::MO_MachineRegister;
+ getMachineRegNum = target.getRegInfo().getZeroRegNum();
+ }
return opType;
}
@@ -158,52 +155,48 @@ FixConstantOperandsForInstr(Instruction* vmInstr,
MachineOperand::MO_VirtualRegister;
// Operand may be a virtual register or a compile-time constant
- if (mop.getType() == MachineOperand::MO_VirtualRegister)
- {
- assert(mop.getVRegValue() != NULL);
- opValue = mop.getVRegValue();
- if (Constant *opConst = dyn_cast<Constant>(opValue)) {
- opType = ChooseRegOrImmed(opConst, opCode, target,
- (immedPos == (int)op), machineRegNum,
- immedValue);
- if (opType == MachineOperand::MO_VirtualRegister)
- constantThatMustBeLoaded = true;
- }
+ if (mop.getType() == MachineOperand::MO_VirtualRegister) {
+ assert(mop.getVRegValue() != NULL);
+ opValue = mop.getVRegValue();
+ if (Constant *opConst = dyn_cast<Constant>(opValue)) {
+ opType = ChooseRegOrImmed(opConst, opCode, target,
+ (immedPos == (int)op), machineRegNum,
+ immedValue);
+ if (opType == MachineOperand::MO_VirtualRegister)
+ constantThatMustBeLoaded = true;
}
- else
- {
- assert(mop.isImmediate());
- bool isSigned = mop.getType() == MachineOperand::MO_SignExtendedImmed;
+ } else {
+ assert(mop.isImmediate());
+ bool isSigned = mop.getType() == MachineOperand::MO_SignExtendedImmed;
- // Bit-selection flags indicate an instruction that is extracting
- // bits from its operand so ignore this even if it is a big constant.
- if (mop.opHiBits32() || mop.opLoBits32() ||
- mop.opHiBits64() || mop.opLoBits64())
- continue;
+ // Bit-selection flags indicate an instruction that is extracting
+ // bits from its operand so ignore this even if it is a big constant.
+ if (mop.opHiBits32() || mop.opLoBits32() ||
+ mop.opHiBits64() || mop.opLoBits64())
+ continue;
- opType = ChooseRegOrImmed(mop.getImmedValue(), isSigned,
- opCode, target, (immedPos == (int)op),
- machineRegNum, immedValue);
+ opType = ChooseRegOrImmed(mop.getImmedValue(), isSigned,
+ opCode, target, (immedPos == (int)op),
+ machineRegNum, immedValue);
- if (opType == MachineOperand::MO_SignExtendedImmed ||
- opType == MachineOperand::MO_UnextendedImmed) {
- // The optype is an immediate value
- // This means we need to change the opcode, e.g. ADDr -> ADDi
- unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
- minstr->setOpcode(newOpcode);
- }
+ if (opType == MachineOperand::MO_SignExtendedImmed ||
+ opType == MachineOperand::MO_UnextendedImmed) {
+ // The optype is an immediate value
+ // This means we need to change the opcode, e.g. ADDr -> ADDi
+ unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
+ minstr->setOpcode(newOpcode);
+ }
- if (opType == mop.getType())
- continue; // no change: this is the most common case
+ if (opType == mop.getType())
+ continue; // no change: this is the most common case
- if (opType == MachineOperand::MO_VirtualRegister)
- {
- constantThatMustBeLoaded = true;
- opValue = isSigned
- ? (Value*)ConstantSInt::get(Type::LongTy, immedValue)
- : (Value*)ConstantUInt::get(Type::ULongTy,(uint64_t)immedValue);
- }
+ if (opType == MachineOperand::MO_VirtualRegister) {
+ constantThatMustBeLoaded = true;
+ opValue = isSigned
+ ? (Value*)ConstantSInt::get(Type::LongTy, immedValue)
+ : (Value*)ConstantUInt::get(Type::ULongTy,(uint64_t)immedValue);
}
+ }
if (opType == MachineOperand::MO_MachineRegister)
minstr->SetMachineOperandReg(op, machineRegNum);
@@ -250,16 +243,16 @@ FixConstantOperandsForInstr(Instruction* vmInstr,
InsertCodeToLoadConstant(F, oldVal, vmInstr, MVec, target);
minstr->setImplicitRef(i, tmpReg);
- if (isCall)
- { // find and replace the argument in the CallArgsDescriptor
- unsigned i=lastCallArgNum;
- while (argDesc->getArgInfo(i).getArgVal() != oldVal)
- ++i;
- assert(i < argDesc->getNumArgs() &&
- "Constant operands to a call *must* be in the arg list");
- lastCallArgNum = i;
- argDesc->getArgInfo(i).replaceArgVal(tmpReg);
- }
+ if (isCall) {
+ // find and replace the argument in the CallArgsDescriptor
+ unsigned i=lastCallArgNum;
+ while (argDesc->getArgInfo(i).getArgVal() != oldVal)
+ ++i;
+ assert(i < argDesc->getNumArgs() &&
+ "Constant operands to a call *must* be in the arg list");
+ lastCallArgNum = i;
+ argDesc->getArgInfo(i).replaceArgVal(tmpReg);
+ }
}
return MVec;
diff --git a/lib/Target/SparcV9/InstrSelection/InstrForest.cpp b/lib/Target/SparcV9/InstrSelection/InstrForest.cpp
index 90993b7a8d..5496502d5e 100644
--- a/lib/Target/SparcV9/InstrSelection/InstrForest.cpp
+++ b/lib/Target/SparcV9/InstrSelection/InstrForest.cpp
@@ -19,13 +19,13 @@
//
//===----------------------------------------------------------------------===//
-#include "llvm/CodeGen/InstrForest.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/Constant.h"
#include "llvm/Function.h"
#include "llvm/iTerminators.h"
#include "llvm/iMemory.h"
-#include "llvm/Constant.h"
#include "llvm/Type.h"
+#include "llvm/CodeGen/InstrForest.h"
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "Support/STLExtras.h"
#include "Config/alloca.h"
@@ -35,102 +35,82 @@
//------------------------------------------------------------------------
void
-InstrTreeNode::dump(int dumpChildren, int indent) const
-{
+InstrTreeNode::dump(int dumpChildren, int indent) const {
dumpNode(indent);
- if (dumpChildren)
- {
- if (LeftChild)
- LeftChild->dump(dumpChildren, indent+1);
- if (RightChild)
- RightChild->dump(dumpChildren, indent+1);
- }
+ if (dumpChildren) {
+ if (LeftChild)
+ LeftChild->dump(dumpChildren, indent+1);
+ if (RightChild)
+ RightChild->dump(dumpChildren, indent+1);
+ }
}
InstructionNode::InstructionNode(Instruction* I)
- : InstrTreeNode(NTInstructionNode, I),
- codeIsFoldedIntoParent(false)
+ : InstrTreeNode(NTInstructionNode, I), codeIsFoldedIntoParent(false)
{
opLabel = I->getOpcode();
// Distinguish special cases of some instructions such as Ret and Br
//
- if (opLabel == Instruction::Ret && cast<ReturnInst>(I)->getReturnValue())
- {
- opLabel = RetValueOp; // ret(value) operation
- }
+ if (opLabel == Instruction::Ret && cast<ReturnInst>(I)->getReturnValue()) {
+ opLabel = RetValueOp; // ret(value) operation
+ }
else if (opLabel ==Instruction::Br && !cast<BranchInst>(I)->isUnconditional())
+ {
+ opLabel = BrCondOp; // br(cond) operation
+ } else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT) {
+ opLabel = SetCCOp; // common label for all SetCC ops
+ } else if (opLabel == Instruction::Alloca && I->getNumOperands() > 0) {
+ opLabel = AllocaN; // Alloca(ptr, N) operation
+ } 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 = (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) {
+ const Type *ITy = I->getType();
+ switch(ITy->getPrimitiveID())
{
- opLabel = BrCondOp; // br(cond) operation
- }
- else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT)
- {
- opLabel = SetCCOp; // common label for all SetCC ops
- }
- else if (opLabel == Instruction::Alloca && I->getNumOperands() > 0)
- {
- opLabel = AllocaN; // Alloca(ptr, N) operation
- }
- 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 = (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)
- {
- const Type *ITy = I->getType();
- switch(ITy->getPrimitiveID())
- {
- case Type::BoolTyID: opLabel = ToBoolTy; break;
- case Type::UByteTyID: opLabel = ToUByteTy; break;
- case Type::SByteTyID: opLabel = ToSByteTy; break;
- case Type::UShortTyID: opLabel = ToUShortTy; break;
- case Type::ShortTyID: opLabel = ToShortTy; break;
- case Type::UIntTyID: opLabel = ToUIntTy; break;
- case Type::IntTyID: opLabel = ToIntTy; break;
- case Type::ULongTyID: opLabel = ToULongTy; break;
- case Type::LongTyID: opLabel = ToLongTy; break;
- case Type::FloatTyID: opLabel = ToFloatTy; break;
- case Type::DoubleTyID: opLabel = ToDoubleTy; break;
- case Type::ArrayTyID: opLabel = ToArrayTy; break;
- case Type::PointerTyID: opLabel = ToPointerTy; break;
- default:
- // Just use `Cast' opcode otherwise. It's probably ignored.
- break;
- }
+ case Type::BoolTyID: opLabel = ToBoolTy; break;
+ case Type::UByteTyID: opLabel = ToUByteTy; break;
+ case Type::SByteTyID: opLabel = ToSByteTy; break;
+ case Type::UShortTyID: opLabel = ToUShortTy; break;
+ case Type::ShortTyID: opLabel = ToShortTy; break;
+ case Type::UIntTyID: opLabel = ToUIntTy; break;
+ case Type::IntTyID: opLabel = ToIntTy; break;
+ case Type::ULongTyID: opLabel = ToULongTy; break;
+ case Type::LongTyID: opLabel = ToLongTy; break;
+ case Type::FloatTyID: opLabel = ToFloatTy; break;
+ case Type::DoubleTyID: opLabel = ToDoubleTy; break;
+ case Type::ArrayTyID: opLabel = ToArrayTy; break;
+ case Type::PointerTyID: opLabel = ToPointerTy; break;
+ default:
+ // Just use `Cast' opcode otherwise. It's probably ignored.
+ break;
}
+ }
}
void
-InstructionNode::dumpNode(int indent) const
-{
+InstructionNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
std::cerr << getInstruction()->getOpcodeName()
<< " [label " << getOpLabel() << "]" << "\n";
}
-
void
-VRegListNode::dumpNode(int indent) const
-{
+VRegListNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
@@ -139,8 +119,7 @@ VRegListNode::dumpNode(int indent) const
void
-VRegNode::dumpNode(int indent) const
-{
+VRegNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
@@ -149,8 +128,7 @@ VRegNode::dumpNode(int indent) const
}
void
-ConstantNode::dumpNode(int indent) const
-{
+ConstantNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
@@ -158,9 +136,7 @@ ConstantNode::dumpNode(int indent) const
<< (int) getValue()->getValueType() << ")" << "\n";
}
-void
-LabelNode::dumpNode(int indent) const
-{
+void LabelNode::dumpNode(int indent) const {
for (int i=0; i < indent; i++)
std::cerr << " ";
@@ -173,56 +149,46 @@ LabelNode::dumpNode(int indent) const
// A forest of instruction trees, usually for a single method.
//------------------------------------------------------------------------
-InstrForest::InstrForest(Function *F)
-{
+InstrForest::InstrForest(Function *F) {
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()
-{
+InstrForest::~InstrForest() {
for_each(treeRoots.begin(), treeRoots.end(), deleter<InstructionNode>);
}
-void
-InstrForest::dump() const
-{
+void InstrForest::dump() const {
for (const_root_iterator I = roots_begin(); I != roots_end(); ++I)
(*I)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
}
-inline void
-InstrForest::eraseRoot(InstructionNode* node)
-{
+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)
-{
+inline void InstrForest::noteTreeNodeForInstr(Instruction *instr,
+ InstructionNode *treeNode) {
(*this)[instr] = treeNode;
treeRoots.push_back(treeNode); // mark node as root of a new tree
}
-inline void
-InstrForest::setLeftChild(InstrTreeNode *parent, InstrTreeNode *child)
-{
+inline void InstrForest::setLeftChild(InstrTreeNode *parent,
+ InstrTreeNode *child) {
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 *parent, InstrTreeNode *child)
-{
+inline void InstrForest::setRightChild(InstrTreeNode *parent,
+ InstrTreeNode *child) {
parent->RightChild = child;
child->Parent = parent;
if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
@@ -230,26 +196,23 @@ InstrForest::setRightChild(InstrTreeNode *parent, InstrTreeNode *child)
}
-InstructionNode*
-InstrForest::buildTreeForInstruction(Instruction *instr)
-{
+InstructionNode* InstrForest::buildTreeForInstruction(Instruction *instr) {
InstructionNode *treeNode = getTreeNodeForInstr(instr);
- if (treeNode)
- {
- // treeNode has already been constructed for this instruction
- assert(treeNode->getInstruction() == instr);
- return treeNode;
- }
+ if (treeNode) {
+ // treeNode has already been constructed for this instruction
+ assert(treeNode->getInstruction() == instr);
+ return treeNode;
+ }
// Otherwise, create a new tree node for this instruction.
//
treeNode = new InstructionNode(instr);
noteTreeNodeForInstr(instr, treeNode);
- if (instr->getOpcode() == Instruction::Call)
- { // Operands of call instruction
- return treeNode;
- }
+ if (instr->getOpcode() == Instruction::Call) {
+ // Operands of call instruction
+ return treeNode;
+ }
// If the instruction has more than 2 instruction operands,
// then we need to create artificial list nodes to hold them.
@@ -285,46 +248,42 @@ InstrForest::buildTreeForInstruction(Instruction *instr)
if (includeAddressOperand || isa<Instruction>(operand) ||
isa<Constant>(operand) || isa<Argument>(operand) ||
isa<GlobalVariable>(operand))
- {
- // This operand is a data value
+ {
+ // This operand is a data value
- // An instruction that computes the incoming value is added as a
- // child of the current instruction if:
- // the value has only a single use
- // AND both instructions are in the same basic block.
- // AND the current instruction is not a PHI (because the incoming
- // value is conceptually in a predecessor block,
- // even though it may be in the same static block)
- //
- // (Note that if the value has only a single use (viz., `instr'),
- // the def of the value can be safely moved just before instr
- // and therefore it is safe to combine these two instructions.)
- //
- // In all other cases, the virtual register holding the value
- // is used directly, i.e., made a child of the instruction node.
- //
- InstrTreeNode* opTreeNode;
- if (isa<Instruction>(operand) && operand->hasOneUse() &&
- cast<Instruction>(operand)->getParent() == instr->getParent() &&
- instr->getOpcode() != Instruction::PHI &&
- instr->getOpcode() != Instruction::Call)
- {
- // Recursively create a treeNode for it.
- opTreeNode = buildTreeForInstruction((Instruction*)operand);
- }
- else if (Constant *CPV = dyn_cast<Constant>(operand))
- {
- // Create a leaf node for a constant
- opTreeNode = new ConstantNode(CPV);
- }
- else
- {
- // Create a leaf node for the virtual register
- opTreeNode = new VRegNode(operand);
- }
+ // An instruction that computes the incoming value is added as a
+ // child of the current instruction if:
+ // the value has only a single use
+ // AND both instructions are in the same basic block.
+ // AND the current instruction is not a PHI (because the incoming
+ // value is conceptually in a predecessor block,
+ // even though it may be in the same static block)
+ //
+ // (Note that if the value has only a single use (viz., `instr'),
+ // the def of the value can be safely moved just before instr
+ // and therefore it is safe to combine these two instructions.)
+ //
+ // In all other cases, the virtual register holding the value
+ // is used directly, i.e., made a child of the instruction node.
+ //
+ InstrTreeNode* opTreeNode;
+ if (isa<Instruction>(operand) && operand->hasOneUse() &&
+ cast<Instruction>(operand)->getParent() == instr->getParent() &&
+ instr->getOpcode() != Instruction::PHI &&
+ instr->getOpcode() != Instruction::Call)
+ {
+ // Recursively create a treeNode for it.
+ opTreeNode = buildTreeForInstruction((Instruction*)operand);
+ } else if (Constant *CPV = dyn_cast<Constant>(operand)) {
+ // Create a leaf node for a constant
+ opTreeNode = new ConstantNode(CPV);
+ } else {
+ // Create a leaf node for the virtual register
+ opTreeNode = new VRegNode(operand);
+ }
- childArray[numChildren++] = opTreeNode;
- }
+ childArray[numChildren++] = opTreeNode;
+ }
}
//--------------------------------------------------------------------
@@ -338,15 +297,14 @@ InstrForest::buildTreeForInstruction(Instruction *instr)
InstrTreeNode *parent = treeNode;
- if (numChildren > 2)
- {
- unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
- assert(instrOpcode == Instruction::PHI ||
- instrOpcode == Instruction::Call ||
- instrOpcode == Instruction::Load ||
- instrOpcode == Instruction::Store ||
- instrOpcode == Instruction::GetElementPtr);
- }
+ if (numChildren > 2) {
+ unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
+ assert(instrOpcode == Instruction::PHI ||
+ instrOpcode == Instruction::Call ||
+ instrOpcode == Instruction::Load ||
+ instrOpcode == Instruction::Store ||
+ instrOpcode == Instruction::GetElementPtr);
+ }
// Insert the first child as a direct child
if (numChildren >= 1)
@@ -355,21 +313,19 @@ InstrForest::buildTreeForInstruction(Instruction *instr)
int n;
// Create a list node for children 2 .. N-1, if any
- for (n = numChildren-1; n >= 2; n--)
- {
- // We have more than two children
- InstrTreeNode *listNode = new VRegListNode();
- setRightChild(parent, listNode);
- setLeftChild(listNode, childArray[numChildren - n]);
- parent = listNode;
- }
+ for (n = numChildren-1; n >= 2; n--) {
+ // We have more than two children
+ InstrTreeNode *listNode = new VRegListNode();
+ setRightChild(parent, listNode);
+ setLeftChild(listNode, childArray[numChildren - n]);
+ parent = listNode;
+ }
// Now insert the last remaining child (if any).
- if (numChildren >= 2)
- {
- assert(n == 1);
- setRightChild(parent, childArray[numChildren - 1]);
- }
+ if (numChildren >= 2) {
+ assert(n == 1);
+ setRightChild(parent, childArray[numChildren - 1]);
+ }
delete [] childArray;
return treeNode;
diff --git a/lib/Target/SparcV9/InstrSelection/InstrSelection.cpp b/lib/Target/SparcV9/InstrSelection/InstrSelection.cpp
index 32dc65e6e1..0e3e2cdbf2 100644
--- a/lib/Target/SparcV9/InstrSelection/InstrSelection.cpp
+++ b/lib/Target/SparcV9/InstrSelection/InstrSelection.cpp
@@ -14,19 +14,19 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/Function.h"
+#include "llvm/iPHINode.h"
+#include "llvm/Pass.h"
+#include "llvm/CodeGen/InstrForest.h"
#include "llvm/CodeGen/InstrSelection.h"
#include "llvm/CodeGen/InstrSelectionSupport.h"
-#include "llvm/CodeGen/InstrForest.h"
#include "llvm/CodeGen/MachineCodeForInstruction.h"
#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/Target/TargetRegInfo.h"
#include "llvm/Target/TargetMachine.h"
-#include "llvm/Function.h"
-#include "llvm/iPHINode.h"
-#include "llvm/Pass.h"
+#include "llvm/Target/TargetRegInfo.h"
#include "Support/CommandLine.h"
#include "Support/LeakDetector.h"
-using std::vector;
+#include <vector>
std::vector<MachineInstr*>
FixConstantOperandsForInstr(Instruction* vmInstr, MachineInstr* minstr,
@@ -66,7 +66,7 @@ namespace {
TargetMachine &Target;
void InsertCodeForPhis(Function &F);
void InsertPhiElimInstructions(BasicBlock *BB,
- const vector<MachineInstr*>& CpVec);
+ const std::vector<MachineInstr*>& CpVec);
void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt);
void PostprocessMachineCodeForTree(InstructionNode* instrNode,
int ruleForNode, short* nts);
@@ -89,9 +89,8 @@ TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
mcfi.addTemp(this);
Operands.push_back(Use(s1, this)); // s1 must be non-null
- if (s2) {
+ if (s2)
Operands.push_back(Use(s2, this));
- }
// TmpInstructions should not be garbage checked.
LeakDetector::removeGarbageObject(this);
@@ -106,8 +105,10 @@ TmpInstruction::TmpInstruction(MachineCodeForInstruction& mcfi,
{
mcfi.addTemp(this);
- if (s1) { Operands.push_back(Use(s1, this)); }
- if (s2) { Operands.push_back(Use(s2, this)); }
+ if (s1)
+ Operands.push_back(Use(s1, this));
+ if (s2)
+ Operands.push_back(Use(s2, this));
// TmpInstructions should not be garbage checked.
LeakDetector::removeGarbageObject(this);
@@ -121,37 +122,34 @@ bool InstructionSelection::runOnFunction(Function &F)
//
InstrForest instrForest(&F);
- if (SelectDebugLevel >= Select_DebugInstTrees)
- {
- std::cerr << "\n\n*** Input to instruction selection for function "
- << F.getName() << "\n\n" << F
- << "\n\n*** Instruction trees for function "
- << F.getName() << "\n\n";
- instrForest.dump();
- }
+ if (SelectDebugLevel >= Select_DebugInstTrees) {
+ std::cerr << "\n\n*** Input to instruction selection for function "
+ << F.getName() << "\n\n" << F
+ << "\n\n*** Instruction trees for function "
+ << F.getName() << "\n\n";
+ instrForest.dump();
+ }
//
// Invoke BURG instruction selection for each tree
//
for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
- RI != instrForest.roots_end(); ++RI)
- {
- InstructionNode* basicNode = *RI;
- assert(basicNode->parent() == NULL && "A `root' node has a parent?");
-
- // Invoke BURM to label each tree node with a state
- burm_label(basicNode);
+ RI != instrForest.roots_end(); ++RI) {
+ InstructionNode* basicNode = *RI;
+ assert(basicNode->parent() == NULL && "A `root' node has a parent?");
- if (SelectDebugLevel >= Select_DebugBurgTrees)
- {
- printcover(basicNode, 1, 0);
- std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
- printMatches(basicNode);
- }
+ // Invoke BURM to label each tree node with a state
+ burm_label(basicNode);
- // Then recursively walk the tree to select instructions
- SelectInstructionsForTree(basicNode, /*goalnt*/1);
+ if (SelectDebugLevel >= Select_DebugBurgTrees) {
+ printcover(basicNode, 1, 0);
+ std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
+ printMatches(basicNode);
}
+
+ // Then recursively walk the tree to select instructions
+ SelectInstructionsForTree(basicNode, /*goalnt*/1);
+ }
//
// Create the MachineBasicBlock records and add all of the MachineInstrs
@@ -172,11 +170,10 @@ bool InstructionSelection::runOnFunction(Function &F)
// Insert phi elimination code
InsertCodeForPhis(F);
- if (SelectDebugLevel >= Select_PrintMachineCode)
- {
- std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
- MachineFunction::get(&F).dump();
- }
+ if (SelectDebugLevel >= Select_PrintMachineCode) {
+ std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
+ MachineFunction::get(&F).dump();
+ }
return true;
}
@@ -187,8 +184,7 @@ bool InstructionSelection::runOnFunction(Function &F)
//-------------------------------------------------------------------------
void
-InstructionSelection::InsertCodeForPhis(Function &F)
-{
+InstructionSelection::InsertCodeForPhis(Function &F) {
// for all basic blocks in function
//
MachineFunction &MF = MachineFunction::get(&F);
@@ -207,12 +203,12 @@ InstructionSelection::InsertCodeForPhis(Function &F)
//
for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
// insert the copy instruction to the predecessor BB
- vector<MachineInstr*> mvec, CpVec;
+ std::vector<MachineInstr*> mvec, CpVec;
Target.getRegInfo().cpValue2Value(PN->getIncomingValue(i), PhiCpRes,
mvec);
- for (vector<MachineInstr*>::iterator MI=mvec.begin();
+ for (std::vector<MachineInstr*>::iterator MI=mvec.begin();
MI != mvec.end(); ++MI) {
- vector<MachineInstr*> CpVec2 =
+ std::vector<MachineInstr*> CpVec2 =
FixConstantOperandsForInstr(const_cast<PHINode*>(PN), *MI, Target);
CpVec2.push_back(*MI);
CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
@@ -221,7 +217,7 @@ InstructionSelection::InsertCodeForPhis(Function &F)
InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
}
- vector<MachineInstr*> mvec;
+ std::vector<MachineInstr*> mvec;
Target.getRegInfo().cpValue2Value(PhiCpRes, const_cast<PHINode*>(PN),
mvec);
BB->insert(BB->begin(), mvec.begin(), mvec.end());
@@ -236,7 +232,7 @@ InstructionSelection::InsertCodeForPhis(Function &F)
void
InstructionSelection::InsertPhiElimInstructions(BasicBlock *BB,
- const vector<MachineInstr*>& CpVec)
+ const std::vector<MachineInstr*>& CpVec)
{
Instruction *TermInst = (Instruction*)BB->getTerminator();
MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
@@ -304,50 +300,47 @@ InstructionSelection::SelectInstructionsForTree(InstrTreeNode* treeRoot,
// (If this is a list node, not an instruction, then skip this step).
// This function is specific to the target architecture.
//
- if (treeRoot->opLabel != VRegListOp)
- {
- vector<MachineInstr*> minstrVec;
+ if (treeRoot->opLabel != VRegListOp) {
+ std::vector<MachineInstr*> minstrVec;
- InstructionNode* instrNode = (InstructionNode*)treeRoot;
- assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
+ InstructionNode* instrNode = (InstructionNode*)treeRoot;
+ assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
- GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
+ GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
- MachineCodeForInstruction &mvec =
- MachineCodeForInstruction::get(instrNode->getInstruction());
- mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
- }
+ MachineCodeForInstruction &mvec =
+ MachineCodeForInstruction::get(instrNode->getInstruction());
+ mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
+ }
// Then, recursively compile the child nodes, if any.
//
- if (nts[0])
- { // i.e., there is at least one kid
- InstrTreeNode* kids[2];
- int currentRule = ruleForNode;
- burm_kids(treeRoot, currentRule, kids);
+ if (nts[0]) {
+ // i.e., there is at least one kid
+ InstrTreeNode* kids[2];
+ int currentRule = ruleForNode;
+ burm_kids(treeRoot, currentRule, kids);
- // First skip over any chain rules so that we don't visit
- // the current node again.
- //
- while (ThisIsAChainRule(currentRule))
- {
- currentRule = burm_rule(treeRoot->state, nts[0]);
- nts = burm_nts[currentRule];
- burm_kids(treeRoot, currentRule, kids);
- }
+ // First skip over any chain rules so that we don't visit
+ // the current node again.
+ //
+ while (ThisIsAChainRule(currentRule)) {
+ currentRule = burm_rule(treeRoot->state, nts[0]);
+ nts = burm_nts[currentRule];
+ burm_kids(treeRoot, currentRule, kids);
+ }
- // Now we have the first non-chain rule so we have found
- // the actual child nodes. Recursively compile them.
- //
- for (unsigned i = 0; nts[i]; i++)
- {
- assert(i < 2);
- InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
- if (nodeType == InstrTreeNode::NTVRegListNode ||
- nodeType == InstrTreeNode::NTInstructionNode)
- SelectInstructionsForTree(kids[i], nts[i]);
- }
+ // Now we have the first non-chain rule so we have found
+ // the actual child nodes. Recursively compile them.
+ //
+ for (unsigned i = 0; nts[i]; i++) {
+ assert(i < 2);
+ InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
+ if (nodeType == InstrTreeNode::NTVRegListNode ||
+ nodeType == InstrTreeNode::NTInstructionNode)
+ SelectInstructionsForTree(kids[i], nts[i]);
}
+ }
// Finally, do any post-processing on this node after its children
// have been translated
@@ -373,13 +366,12 @@ InstructionSelection::PostprocessMachineCodeForTree(InstructionNode* instrNode,
//
Instruction* vmInstr = instrNode->getInstruction();
MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
- for (unsigned i = mvec.size(); i != 0; --i)
- {
- vector<MachineInstr*> loadConstVec =
- FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
+ for (unsigned i = mvec.size(); i != 0; --i) {
+ std::vector<MachineInstr*> loadConstVec =
+ FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
- mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
- }
+ mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
+ }
}
diff --git a/lib/Target/SparcV9/InstrSelection/InstrSelectionSupport.cpp b/lib/Target/SparcV9/InstrSelection/InstrSelectionSupport.cpp
index f177e460b1..93f7618641 100644
--- a/lib/Target/SparcV9/InstrSelection/InstrSelectionSupport.cpp
+++ b/lib/Target/SparcV9/InstrSelection/InstrSelectionSupport.cpp
@@ -66,17 +66,14 @@ ChooseRegOrImmed(int64_t intValue,
getImmedValue = 0;
if (canUseImmed &&
- target.getInstrInfo().constantFitsInImmedField(opCode, intValue))
- {
+ target.getInstrInfo().constantFitsInImmedField(opCode, intValue)) {
opType = isSigned? MachineOperand::MO_SignExtendedImmed
: MachineOperand::MO_UnextendedImmed;
getImmedValue = intValue;
- }
- else if (intValue == 0 && target.getRegInfo().getZeroRegNum() >= 0)
- {
- opType = MachineOperand::MO_MachineRegister;
- getMachineRegNum = target.getRegInfo().getZeroRegNum();
- }
+ } else if (intValue == 0 && target.getRegInfo().getZeroRegNum() >= 0) {
+ opType = MachineOperand::MO_MachineRegister;
+ getMachineRegNum = target.getRegInfo().getZeroRegNum();
+ }
return opType;
}
@@ -158,52 +155,48 @@ FixConstantOperandsForInstr(Instruction* vmInstr,
MachineOperand::MO_VirtualRegister;
// Operand may be a virtual register or a compile-time constant
- if (mop.getType() == MachineOperand::MO_VirtualRegister)
- {
- assert(mop.getVRegValue() != NULL);
- opValue = mop.getVRegValue();
- if (Constant *opConst = dyn_cast<Constant>(opValue)) {
- opType = ChooseRegOrImmed(opConst, opCode, target,
- (immedPos == (int)op), machineRegNum,
- immedValue);
- if (opType == MachineOperand::MO_VirtualRegister)
- constantThatMustBeLoaded = true;
- }
+ if (mop.getType() == MachineOperand::MO_VirtualRegister) {
+ assert(mop.getVRegValue() != NULL);
+ opValue = mop.getVRegValue();
+ if (Constant *opConst = dyn_cast<Constant>(opValue)) {
+ opType = ChooseRegOrImmed(opConst, opCode, target,
+ (immedPos == (int)op), machineRegNum,
+ immedValue);
+ if (opType == MachineOperand::MO_VirtualRegister)
+ constantThatMustBeLoaded = true;
}
- else
- {
- assert(mop.isImmediate());
- bool isSigned = mop.getType() == MachineOperand::MO_SignExtendedImmed;
+ } else {
+ assert(mop.isImmediate());
+ bool isSigned = mop.getType() == MachineOperand::MO_SignExtendedImmed;
- // Bit-selection flags indicate an instruction that is extracting
- // bits from its operand so ignore this even if it is a big constant.
- if (mop.opHiBits32() || mop.opLoBits32() ||
- mop.opHiBits64() || mop.opLoBits64())
- continue;
+ // Bit-selection flags indicate an instruction that is extracting
+ // bits from its operand so ignore this even if it is a big constant.
+ if (mop.opHiBits32() || mop.opLoBits32() ||
+ mop.opHiBits64() || mop.opLoBits64())
+ continue;
- opType = ChooseRegOrImmed(mop.getImmedValue(), isSigned,
- opCode, target, (immedPos == (int)op),
- machineRegNum, immedValue);
+ opType = ChooseRegOrImmed(mop.getImmedValue(), isSigned,
+ opCode, target, (immedPos == (int)op),
+ machineRegNum, immedValue);
- if (opType == MachineOperand::MO_SignExtendedImmed ||
- opType == MachineOperand::MO_UnextendedImmed) {
- // The optype is an immediate value
- // This means we need to change the opcode, e.g. ADDr -> ADDi
- unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
- minstr->setOpcode(newOpcode);
- }
+ if (opType == MachineOperand::MO_SignExtendedImmed ||
+ opType == MachineOperand::MO_UnextendedImmed) {
+ // The optype is an immediate value
+ // This means we need to change the opcode, e.g. ADDr -> ADDi
+ unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
+ minstr->setOpcode(newOpcode);
+ }
- if (opType == mop.getType())
- continue; // no change: this is the most common case
+ if (opType == mop.getType())
+ continue; // no change: this is the most common case
- if (opType == MachineOperand::MO_VirtualRegister)
- {
- constantThatMustBeLoaded = true;
- opValue = isSigned
- ? (Value*)ConstantSInt::get(Type::LongTy, immedValue)
- : (Value*)ConstantUInt::get(Type::ULongTy,(uint64_t)immedValue);
- }
+ if (opType == MachineOperand::MO_VirtualRegister) {
+ constantThatMustBeLoaded = true;
+ opValue = isSigned
+ ? (Value*)ConstantSInt::get(Type::LongTy, immedValue)
+ : (Value*)ConstantUInt::get(Type::ULongTy,(uint64_t)immedValue);
}
+ }
if (opType == MachineOperand::MO_MachineRegister)
minstr->SetMachineOperandReg(op, machineRegNum);
@@ -250,16 +243,16 @@ FixConstantOperandsForInstr(Instruction* vmInstr,
InsertCodeToLoadConstant(F, oldVal, vmInstr, MVec, target);
minstr->setImplicitRef(i, tmpReg);
- if (isCall)
- { // find and replace the argument in the CallArgsDescriptor
- unsigned i=lastCallArgNum;
- while (argDesc->getArgInfo(i).getArgVal() != oldVal)
- ++i;
- assert(i < argDesc->getNumArgs() &&
- "Constant operands to a call *must* be in the arg list");
- lastCallArgNum = i;
- argDesc->getArgInfo(i).replaceArgVal(tmpReg);
- }
+ if (isCall) {
+ // find and replace the argument in the CallArgsDescriptor
+ unsigned i=lastCallArgNum;
+ while (argDesc->getArgInfo(i).getArgVal() != oldVal)
+ ++i;
+ assert(i < argDesc->getNumArgs() &&
+ "Constant operands to a call *must* be in the arg list");
+ lastCallArgNum = i;
+ argDesc->getArgInfo(i).replaceArgVal(tmpReg);
+ }
}
return MVec;