From 4ddb4c82d7451f7ab0269a4d0ca948f96e80402e Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 12 Sep 2001 01:28:49 +0000 Subject: [PATCH] * Clean up InstrForest * Fix ins sel problem, test case: void "foo" (int *%x, int *%y) begin seteq int *%x, %y ret void end git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@552 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/InstrForest.h | 100 ++--- lib/CodeGen/InstrSelection/InstrForest.cpp | 400 +++++++----------- .../Sparc/SparcInstrSelection.cpp | 14 +- .../SparcV9/InstrSelection/InstrForest.cpp | 400 +++++++----------- test/Makefile | 2 +- 5 files changed, 365 insertions(+), 551 deletions(-) diff --git a/include/llvm/CodeGen/InstrForest.h b/include/llvm/CodeGen/InstrForest.h index 403a27ac8a4..e987521ea04 100644 --- a/include/llvm/CodeGen/InstrForest.h +++ b/include/llvm/CodeGen/InstrForest.h @@ -128,9 +128,12 @@ protected: Value* val; public: - /*ctor*/ InstrTreeNode (InstrTreeNodeType nodeType, - Value* _val); - /*dtor*/ virtual ~InstrTreeNode () {} + InstrTreeNode(InstrTreeNodeType nodeType, Value* _val) + : treeNodeType(nodeType), val(_val) { + LeftChild = RightChild = Parent = 0; + opLabel = InvalidOp; + } + virtual ~InstrTreeNode() {} InstrTreeNodeType getNodeType () const { return treeNodeType; } @@ -138,7 +141,7 @@ public: inline OpLabel getOpLabel () const { return opLabel; } - inline InstrTreeNode* leftChild () const { + inline InstrTreeNode* leftChild() const { return LeftChild; } @@ -153,59 +156,69 @@ public: return Parent; } - void dump (int dumpChildren, - int indent) const; + void dump(int dumpChildren, int indent) const; protected: - virtual void dumpNode (int indent) const = 0; + virtual void dumpNode(int indent) const = 0; friend class InstrForest; }; -class InstructionNode: public InstrTreeNode { +class InstructionNode : public InstrTreeNode { public: - /*ctor*/ InstructionNode (Instruction* _instr); - Instruction* getInstruction () const { + InstructionNode(Instruction *_instr); + + Instruction *getInstruction() const { assert(treeNodeType == NTInstructionNode); - return (Instruction*) val; + return (Instruction*)val; } protected: - virtual void dumpNode (int indent) const; + virtual void dumpNode(int indent) const; }; -class VRegListNode: public InstrTreeNode { +class VRegListNode : public InstrTreeNode { public: - /*ctor*/ VRegListNode (); + VRegListNode() : InstrTreeNode(NTVRegListNode, 0) { + opLabel = VRegListOp; + } protected: - virtual void dumpNode (int indent) const; + virtual void dumpNode(int indent) const; }; -class VRegNode: public InstrTreeNode { +class VRegNode : public InstrTreeNode { public: - /*ctor*/ VRegNode (Value* _val); + VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) { + opLabel = VRegNodeOp; + } protected: - virtual void dumpNode (int indent) const; + virtual void dumpNode(int indent) const; }; -class ConstantNode: public InstrTreeNode { +class ConstantNode : public InstrTreeNode { public: - /*ctor*/ ConstantNode (ConstPoolVal* constVal); - ConstPoolVal* getConstVal () const { return (ConstPoolVal*) val;} + ConstantNode(ConstPoolVal *constVal) + : InstrTreeNode(NTConstNode, (Value*)constVal) { + opLabel = ConstantNodeOp; + } + ConstPoolVal *getConstVal() const { return (ConstPoolVal*) val;} protected: - virtual void dumpNode ( int indent) const; + virtual void dumpNode(int indent) const; }; -class LabelNode: public InstrTreeNode { +class LabelNode : public InstrTreeNode { public: - /*ctor*/ LabelNode (BasicBlock* _bblock); - BasicBlock* getBasicBlock () const { return (BasicBlock*) val;} + LabelNode(BasicBlock* BB) : InstrTreeNode(NTLabelNode, (Value*)BB) { + opLabel = LabelNodeOp; + } + + BasicBlock *getBasicBlock() const { return (BasicBlock*)val;} protected: - virtual void dumpNode (int indent) const; + virtual void dumpNode(int indent) const; }; @@ -221,22 +234,13 @@ protected: // //------------------------------------------------------------------------ -class InstrForest : - public NonCopyable, - private hash_map { - -private: +class InstrForest : private hash_map { hash_set treeRoots; public: - /*ctor*/ InstrForest () {} - /*dtor*/ ~InstrForest () {} - - void buildTreesForMethod (Method *method); + void buildTreesForMethod(Method *M); - inline InstructionNode* - getTreeNodeForInstr(Instruction* instr) - { + inline InstructionNode *getTreeNodeForInstr(Instruction* instr) { return (*this)[instr]; } @@ -244,28 +248,18 @@ public: return treeRoots; } - void dump () const; + void dump() const; private: // // Private methods for buidling the instruction forest // - void setLeftChild (InstrTreeNode* parent, - InstrTreeNode* child); - - void setRightChild (InstrTreeNode* parent, - InstrTreeNode* child); - - void setParent (InstrTreeNode* child, - InstrTreeNode* parent); - - void noteTreeNodeForInstr (Instruction* instr, - InstructionNode* treeNode); + void setLeftChild (InstrTreeNode* parent, InstrTreeNode* child); + void setRightChild(InstrTreeNode* parent, InstrTreeNode* child); + void setParent (InstrTreeNode* child, InstrTreeNode* parent); + void noteTreeNodeForInstr(Instruction* instr, InstructionNode* treeNode); InstructionNode* buildTreeForInstruction(Instruction* instr); }; - -/***************************************************************************/ - #endif diff --git a/lib/CodeGen/InstrSelection/InstrForest.cpp b/lib/CodeGen/InstrSelection/InstrForest.cpp index 1ff4c881f73..50c4f987217 100644 --- a/lib/CodeGen/InstrSelection/InstrForest.cpp +++ b/lib/CodeGen/InstrSelection/InstrForest.cpp @@ -22,8 +22,6 @@ // //--------------------------------------------------------------------------- -//*************************** User Include Files ***************************/ - #include "llvm/CodeGen/InstrForest.h" #include "llvm/Method.h" #include "llvm/iTerminators.h" @@ -31,123 +29,87 @@ #include "llvm/ConstPoolVals.h" #include "llvm/BasicBlock.h" #include "llvm/CodeGen/MachineInstr.h" - +#include "llvm/Support/STLExtras.h" //------------------------------------------------------------------------ // class InstrTreeNode //------------------------------------------------------------------------ - -InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType, Value* _val) - : treeNodeType(nodeType), val(_val) { - LeftChild = 0; - RightChild = 0; - Parent = 0; - opLabel = InvalidOp; -} - void 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* _instr) - : InstrTreeNode(NTInstructionNode, _instr) -{ - OpLabel opLabel = _instr->getOpcode(); +InstructionNode::InstructionNode(Instruction* I) + : InstrTreeNode(NTInstructionNode, I) { + opLabel = I->getOpcode(); // Distinguish special cases of some instructions such as Ret and Br // - if (opLabel == Instruction::Ret && ((ReturnInst*) _instr)->getReturnValue()) - { - opLabel = RetValueOp; // ret(value) operation - } - else if (opLabel == Instruction::Br && ! ((BranchInst*) _instr)->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 && _instr->getNumOperands() > 0) - { - opLabel = AllocaN; // Alloca(ptr, N) operation - } - else if ((opLabel == Instruction::Load || - opLabel == Instruction::GetElementPtr) - && ((MemAccessInst*)_instr)->getFirstOffsetIdx() > 0) - { - opLabel = opLabel + 100; // load/getElem with index vector + if (opLabel == Instruction::Ret && ((ReturnInst*)I)->getReturnValue()) { + opLabel = RetValueOp; // ret(value) operation + } else if (opLabel == Instruction::Br && + !((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::Load || + opLabel == Instruction::GetElementPtr) && + ((MemAccessInst*)I)->getFirstOffsetIdx() > 0) { + opLabel = opLabel + 100; // load/getElem with index vector + } 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; } - else if (opLabel == Instruction::Cast) - { - const Type* instrValueType = _instr->getType(); - switch(instrValueType->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; - default: - if (instrValueType->isArrayType()) - opLabel = ToArrayTy; - else if (instrValueType->isPointerType()) - opLabel = ToPointerTy; - else - ; // Just use `Cast' opcode otherwise. It's probably ignored. - break; - } - } - - this->opLabel = opLabel; + } } -void -InstructionNode::dumpNode(int indent) const -{ +void InstructionNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; cout << getInstruction()->getOpcodeName(); - const vector& mvec = getInstruction()->getMachineInstrVec(); + const vector &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 << "; "; - } + for (unsigned int i=0; i < mvec.size(); i++) { + mvec[i]->dump(0); + if (i < mvec.size() - 1) + cout << "; "; + } cout << endl; } -VRegListNode::VRegListNode() : InstrTreeNode(NTVRegListNode, 0) { - opLabel = VRegListOp; -} - -void -VRegListNode::dumpNode(int indent) const -{ +void VRegListNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; @@ -155,13 +117,7 @@ VRegListNode::dumpNode(int indent) const } -VRegNode::VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) { - opLabel = VRegNodeOp; -} - -void -VRegNode::dumpNode(int indent) const -{ +void VRegNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; @@ -169,15 +125,7 @@ VRegNode::dumpNode(int indent) const << (int) getValue()->getValueType() << ")" << endl; } - -ConstantNode::ConstantNode(ConstPoolVal *constVal) - : InstrTreeNode(NTConstNode, constVal) { - opLabel = ConstantNodeOp; -} - -void -ConstantNode::dumpNode(int indent) const -{ +void ConstantNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; @@ -185,14 +133,7 @@ ConstantNode::dumpNode(int indent) const << (int) getValue()->getValueType() << ")" << endl; } - -LabelNode::LabelNode(BasicBlock *BB) : InstrTreeNode(NTLabelNode, BB) { - opLabel = LabelNodeOp; -} - -void -LabelNode::dumpNode(int indent) const -{ +void LabelNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; @@ -205,74 +146,53 @@ LabelNode::dumpNode(int indent) const // A forest of instruction trees, usually for a single method. //------------------------------------------------------------------------ -void -InstrForest::buildTreesForMethod(Method *method) -{ - for (Method::inst_iterator instrIter = method->inst_begin(); - instrIter != method->inst_end(); - ++instrIter) - { - Instruction *instr = *instrIter; - (void) this->buildTreeForInstruction(instr); - } -} - - -void -InstrForest::dump() const -{ - for (hash_set::const_iterator - treeRootIter = treeRoots.begin(); - treeRootIter != treeRoots.end(); - ++treeRootIter) - { - (*treeRootIter)->dump(/*dumpChildren*/ 1, /*indent*/ 0); - } +void InstrForest::dump() const { + for (hash_set::const_iterator I = treeRoots.begin(); + I != treeRoots.end(); ++I) + (*I)->dump(/*dumpChildren*/ 1, /*indent*/ 0); } -inline void -InstrForest::noteTreeNodeForInstr(Instruction* instr, - InstructionNode* treeNode) -{ +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 } -inline void -InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child) { - parent->LeftChild = child; - child->Parent = parent; - if (child->getNodeType() == InstrTreeNode::NTInstructionNode) - treeRoots.erase((InstructionNode*) child); // no longer a tree root +inline void InstrForest::setLeftChild(InstrTreeNode *Par, InstrTreeNode *Chld) { + Par->LeftChild = Chld; + Chld->Parent = Par; + if (Chld->getNodeType() == InstrTreeNode::NTInstructionNode) + treeRoots.erase((InstructionNode*)Chld); // no longer a tree root } -inline void -InstrForest::setRightChild(InstrTreeNode* parent, InstrTreeNode* child) -{ - parent->RightChild = child; - child->Parent = parent; - if (child->getNodeType() == InstrTreeNode::NTInstructionNode) - treeRoots.erase((InstructionNode*) child); // no longer a tree root +inline void InstrForest::setRightChild(InstrTreeNode *Par, InstrTreeNode *Chld){ + Par->RightChild = Chld; + Chld->Parent = Par; + if (Chld->getNodeType() == InstrTreeNode::NTInstructionNode) + treeRoots.erase((InstructionNode*)Chld); // no longer a tree root } -InstructionNode* -InstrForest::buildTreeForInstruction(Instruction* instr) -{ - InstructionNode* treeNode = this->getTreeNodeForInstr(instr); - if (treeNode != NULL) - {// treeNode has already been constructed for this instruction - assert(treeNode->getInstruction() == instr); - return treeNode; - } +void InstrForest::buildTreesForMethod(Method *M) { + for_each(M->inst_begin(), M->inst_end(), + bind_obj(this, &InstrForest::buildTreeForInstruction)); +} + +InstructionNode *InstrForest::buildTreeForInstruction(Instruction *Inst) { + InstructionNode *treeNode = getTreeNodeForInstr(Inst); + if (treeNode) { + // treeNode has already been constructed for this instruction + assert(treeNode->getInstruction() == Inst); + return treeNode; + } // Otherwise, create a new tree node for this instruction. // - treeNode = new InstructionNode(instr); - this->noteTreeNodeForInstr(instr, treeNode); + treeNode = new InstructionNode(Inst); + noteTreeNodeForInstr(Inst, treeNode); // If the instruction has more than 2 instruction operands, // then we need to create artificial list nodes to hold them. @@ -287,67 +207,60 @@ InstrForest::buildTreeForInstruction(Instruction* instr) // int numChildren = 0; const unsigned int MAX_CHILD = 8; - static InstrTreeNode* fixedChildArray[MAX_CHILD]; - InstrTreeNode** childArray = - (instr->getNumOperands() > MAX_CHILD) - ? new (InstrTreeNode*)[instr->getNumOperands()] + static InstrTreeNode *fixedChildArray[MAX_CHILD]; + InstrTreeNode **childArray = + (Inst->getNumOperands() > MAX_CHILD) + ? new (InstrTreeNode*)[Inst->getNumOperands()] : fixedChildArray; // // Walk the operands of the instruction // - for (Instruction::op_iterator O=instr->op_begin(); O != instr->op_end(); ++O) - { - Value* operand = *O; - - // Check if the operand is a data value, not an branch label, type, - // method or module. If the operand is an address type (i.e., label - // or method) that is used in an non-branching operation, e.g., `add'. - // that should be considered a data value. + for (Instruction::op_iterator O = Inst->op_begin(); O != Inst->op_end(); ++O){ + Value* operand = *O; - // Check latter condition here just to simplify the next IF. - bool includeAddressOperand = - ((operand->isBasicBlock() || operand->isMethod()) - && !instr->isTerminator()); - - if (includeAddressOperand || operand->isInstruction() || - operand->isConstant() || operand->isMethodArgument()) - {// 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. - // - // (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 (operand->isInstruction() && operand->use_size() == 1 && - ((Instruction*)operand)->getParent() == instr->getParent()) - { - // Recursively create a treeNode for it. - opTreeNode =this->buildTreeForInstruction((Instruction*)operand); - } - else if (ConstPoolVal *CPV = operand->castConstant()) - { - // 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; - numChildren++; - } + // Check if the operand is a data value, not an branch label, type, + // method or module. If the operand is an address type (i.e., label + // or method) that is used in an non-branching operation, e.g., `add'. + // that should be considered a data value. + + // Check latter condition here just to simplify the next IF. + bool includeAddressOperand = + (operand->isBasicBlock() || operand->isMethod()) + && !Inst->isTerminator(); + + if (includeAddressOperand || operand->isInstruction() || + operand->isConstant() || operand->isMethodArgument()) { + // 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. + // + // (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 (operand->isInstruction() && operand->use_size() == 1 && + ((Instruction*)operand)->getParent() == Inst->getParent()) { + // Recursively create a treeNode for it. + opTreeNode = buildTreeForInstruction((Instruction*)operand); + } else if (ConstPoolVal *CPV = operand->castConstant()) { + // 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; } + } //-------------------------------------------------------------------- // Add any selected operands as children in the tree. @@ -358,43 +271,40 @@ InstrForest::buildTreeForInstruction(Instruction* instr) // and VRegList nodes as internal nodes. //-------------------------------------------------------------------- - InstrTreeNode* parent = treeNode; // new VRegListNode(); - int n; + InstrTreeNode *parent = treeNode; - if (numChildren > 2) - { - unsigned instrOpcode = treeNode->getInstruction()->getOpcode(); - assert(instrOpcode == Instruction::PHINode || - instrOpcode == Instruction::Call || - instrOpcode == Instruction::Load || - instrOpcode == Instruction::Store || - instrOpcode == Instruction::GetElementPtr); - } + if (numChildren > 2) { + unsigned instrOpcode = treeNode->getInstruction()->getOpcode(); + assert(instrOpcode == Instruction::PHINode || + instrOpcode == Instruction::Call || + instrOpcode == Instruction::Load || + instrOpcode == Instruction::Store || + instrOpcode == Instruction::GetElementPtr); + } // Insert the first child as a direct child if (numChildren >= 1) - this->setLeftChild(parent, childArray[0]); + setLeftChild(parent, childArray[0]); + + 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(); - this->setRightChild(parent, listNode); - this->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); - this->setRightChild(parent, childArray[numChildren - 1]); - } + if (numChildren >= 2) { + assert(n == 1); + setRightChild(parent, childArray[numChildren - 1]); + } if (childArray != fixedChildArray) - { - delete[] childArray; - } + delete [] childArray; return treeNode; } diff --git a/lib/CodeGen/TargetMachine/Sparc/SparcInstrSelection.cpp b/lib/CodeGen/TargetMachine/Sparc/SparcInstrSelection.cpp index ca2bca65847..ddee541ce6f 100644 --- a/lib/CodeGen/TargetMachine/Sparc/SparcInstrSelection.cpp +++ b/lib/CodeGen/TargetMachine/Sparc/SparcInstrSelection.cpp @@ -540,12 +540,11 @@ ChooseFcmpInstruction(const InstructionNode* instrNode) MachineOpCode opCode = INVALID_OPCODE; Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue(); - switch(operand->getType()->getPrimitiveID()) - { - case Type::FloatTyID: opCode = FCMPS; break; - case Type::DoubleTyID: opCode = FCMPD; break; - default: assert(0 && "Invalid type for FCMP instruction"); break; - } + switch(operand->getType()->getPrimitiveID()) { + case Type::FloatTyID: opCode = FCMPS; break; + case Type::DoubleTyID: opCode = FCMPD; break; + default: assert(0 && "Invalid type for FCMP instruction"); break; + } return opCode; } @@ -1700,7 +1699,8 @@ GetInstructionsByRule(InstructionNode* subtreeRoot, int valueToMove; MachineOpCode movOpCode; - if (subtreeRoot->leftChild()->getValue()->getType()->isIntegral()) + if (subtreeRoot->leftChild()->getValue()->getType()->isIntegral() || + subtreeRoot->leftChild()->getValue()->getType()->isPointerType()) { // integer condition: destination should be %g0 or integer register // if result must be saved but condition is not SetEQ then we need diff --git a/lib/Target/SparcV9/InstrSelection/InstrForest.cpp b/lib/Target/SparcV9/InstrSelection/InstrForest.cpp index 1ff4c881f73..50c4f987217 100644 --- a/lib/Target/SparcV9/InstrSelection/InstrForest.cpp +++ b/lib/Target/SparcV9/InstrSelection/InstrForest.cpp @@ -22,8 +22,6 @@ // //--------------------------------------------------------------------------- -//*************************** User Include Files ***************************/ - #include "llvm/CodeGen/InstrForest.h" #include "llvm/Method.h" #include "llvm/iTerminators.h" @@ -31,123 +29,87 @@ #include "llvm/ConstPoolVals.h" #include "llvm/BasicBlock.h" #include "llvm/CodeGen/MachineInstr.h" - +#include "llvm/Support/STLExtras.h" //------------------------------------------------------------------------ // class InstrTreeNode //------------------------------------------------------------------------ - -InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType, Value* _val) - : treeNodeType(nodeType), val(_val) { - LeftChild = 0; - RightChild = 0; - Parent = 0; - opLabel = InvalidOp; -} - void 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* _instr) - : InstrTreeNode(NTInstructionNode, _instr) -{ - OpLabel opLabel = _instr->getOpcode(); +InstructionNode::InstructionNode(Instruction* I) + : InstrTreeNode(NTInstructionNode, I) { + opLabel = I->getOpcode(); // Distinguish special cases of some instructions such as Ret and Br // - if (opLabel == Instruction::Ret && ((ReturnInst*) _instr)->getReturnValue()) - { - opLabel = RetValueOp; // ret(value) operation - } - else if (opLabel == Instruction::Br && ! ((BranchInst*) _instr)->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 && _instr->getNumOperands() > 0) - { - opLabel = AllocaN; // Alloca(ptr, N) operation - } - else if ((opLabel == Instruction::Load || - opLabel == Instruction::GetElementPtr) - && ((MemAccessInst*)_instr)->getFirstOffsetIdx() > 0) - { - opLabel = opLabel + 100; // load/getElem with index vector + if (opLabel == Instruction::Ret && ((ReturnInst*)I)->getReturnValue()) { + opLabel = RetValueOp; // ret(value) operation + } else if (opLabel == Instruction::Br && + !((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::Load || + opLabel == Instruction::GetElementPtr) && + ((MemAccessInst*)I)->getFirstOffsetIdx() > 0) { + opLabel = opLabel + 100; // load/getElem with index vector + } 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; } - else if (opLabel == Instruction::Cast) - { - const Type* instrValueType = _instr->getType(); - switch(instrValueType->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; - default: - if (instrValueType->isArrayType()) - opLabel = ToArrayTy; - else if (instrValueType->isPointerType()) - opLabel = ToPointerTy; - else - ; // Just use `Cast' opcode otherwise. It's probably ignored. - break; - } - } - - this->opLabel = opLabel; + } } -void -InstructionNode::dumpNode(int indent) const -{ +void InstructionNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; cout << getInstruction()->getOpcodeName(); - const vector& mvec = getInstruction()->getMachineInstrVec(); + const vector &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 << "; "; - } + for (unsigned int i=0; i < mvec.size(); i++) { + mvec[i]->dump(0); + if (i < mvec.size() - 1) + cout << "; "; + } cout << endl; } -VRegListNode::VRegListNode() : InstrTreeNode(NTVRegListNode, 0) { - opLabel = VRegListOp; -} - -void -VRegListNode::dumpNode(int indent) const -{ +void VRegListNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; @@ -155,13 +117,7 @@ VRegListNode::dumpNode(int indent) const } -VRegNode::VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) { - opLabel = VRegNodeOp; -} - -void -VRegNode::dumpNode(int indent) const -{ +void VRegNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; @@ -169,15 +125,7 @@ VRegNode::dumpNode(int indent) const << (int) getValue()->getValueType() << ")" << endl; } - -ConstantNode::ConstantNode(ConstPoolVal *constVal) - : InstrTreeNode(NTConstNode, constVal) { - opLabel = ConstantNodeOp; -} - -void -ConstantNode::dumpNode(int indent) const -{ +void ConstantNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; @@ -185,14 +133,7 @@ ConstantNode::dumpNode(int indent) const << (int) getValue()->getValueType() << ")" << endl; } - -LabelNode::LabelNode(BasicBlock *BB) : InstrTreeNode(NTLabelNode, BB) { - opLabel = LabelNodeOp; -} - -void -LabelNode::dumpNode(int indent) const -{ +void LabelNode::dumpNode(int indent) const { for (int i=0; i < indent; i++) cout << " "; @@ -205,74 +146,53 @@ LabelNode::dumpNode(int indent) const // A forest of instruction trees, usually for a single method. //------------------------------------------------------------------------ -void -InstrForest::buildTreesForMethod(Method *method) -{ - for (Method::inst_iterator instrIter = method->inst_begin(); - instrIter != method->inst_end(); - ++instrIter) - { - Instruction *instr = *instrIter; - (void) this->buildTreeForInstruction(instr); - } -} - - -void -InstrForest::dump() const -{ - for (hash_set::const_iterator - treeRootIter = treeRoots.begin(); - treeRootIter != treeRoots.end(); - ++treeRootIter) - { - (*treeRootIter)->dump(/*dumpChildren*/ 1, /*indent*/ 0); - } +void InstrForest::dump() const { + for (hash_set::const_iterator I = treeRoots.begin(); + I != treeRoots.end(); ++I) + (*I)->dump(/*dumpChildren*/ 1, /*indent*/ 0); } -inline void -InstrForest::noteTreeNodeForInstr(Instruction* instr, - InstructionNode* treeNode) -{ +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 } -inline void -InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child) { - parent->LeftChild = child; - child->Parent = parent; - if (child->getNodeType() == InstrTreeNode::NTInstructionNode) - treeRoots.erase((InstructionNode*) child); // no longer a tree root +inline void InstrForest::setLeftChild(InstrTreeNode *Par, InstrTreeNode *Chld) { + Par->LeftChild = Chld; + Chld->Parent = Par; + if (Chld->getNodeType() == InstrTreeNode::NTInstructionNode) + treeRoots.erase((InstructionNode*)Chld); // no longer a tree root } -inline void -InstrForest::setRightChild(InstrTreeNode* parent, InstrTreeNode* child) -{ - parent->RightChild = child; - child->Parent = parent; - if (child->getNodeType() == InstrTreeNode::NTInstructionNode) - treeRoots.erase((InstructionNode*) child); // no longer a tree root +inline void InstrForest::setRightChild(InstrTreeNode *Par, InstrTreeNode *Chld){ + Par->RightChild = Chld; + Chld->Parent = Par; + if (Chld->getNodeType() == InstrTreeNode::NTInstructionNode) + treeRoots.erase((InstructionNode*)Chld); // no longer a tree root } -InstructionNode* -InstrForest::buildTreeForInstruction(Instruction* instr) -{ - InstructionNode* treeNode = this->getTreeNodeForInstr(instr); - if (treeNode != NULL) - {// treeNode has already been constructed for this instruction - assert(treeNode->getInstruction() == instr); - return treeNode; - } +void InstrForest::buildTreesForMethod(Method *M) { + for_each(M->inst_begin(), M->inst_end(), + bind_obj(this, &InstrForest::buildTreeForInstruction)); +} + +InstructionNode *InstrForest::buildTreeForInstruction(Instruction *Inst) { + InstructionNode *treeNode = getTreeNodeForInstr(Inst); + if (treeNode) { + // treeNode has already been constructed for this instruction + assert(treeNode->getInstruction() == Inst); + return treeNode; + } // Otherwise, create a new tree node for this instruction. // - treeNode = new InstructionNode(instr); - this->noteTreeNodeForInstr(instr, treeNode); + treeNode = new InstructionNode(Inst); + noteTreeNodeForInstr(Inst, treeNode); // If the instruction has more than 2 instruction operands, // then we need to create artificial list nodes to hold them. @@ -287,67 +207,60 @@ InstrForest::buildTreeForInstruction(Instruction* instr) // int numChildren = 0; const unsigned int MAX_CHILD = 8; - static InstrTreeNode* fixedChildArray[MAX_CHILD]; - InstrTreeNode** childArray = - (instr->getNumOperands() > MAX_CHILD) - ? new (InstrTreeNode*)[instr->getNumOperands()] + static InstrTreeNode *fixedChildArray[MAX_CHILD]; + InstrTreeNode **childArray = + (Inst->getNumOperands() > MAX_CHILD) + ? new (InstrTreeNode*)[Inst->getNumOperands()] : fixedChildArray; // // Walk the operands of the instruction // - for (Instruction::op_iterator O=instr->op_begin(); O != instr->op_end(); ++O) - { - Value* operand = *O; - - // Check if the operand is a data value, not an branch label, type, - // method or module. If the operand is an address type (i.e., label - // or method) that is used in an non-branching operation, e.g., `add'. - // that should be considered a data value. + for (Instruction::op_iterator O = Inst->op_begin(); O != Inst->op_end(); ++O){ + Value* operand = *O; - // Check latter condition here just to simplify the next IF. - bool includeAddressOperand = - ((operand->isBasicBlock() || operand->isMethod()) - && !instr->isTerminator()); - - if (includeAddressOperand || operand->isInstruction() || - operand->isConstant() || operand->isMethodArgument()) - {// 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. - // - // (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 (operand->isInstruction() && operand->use_size() == 1 && - ((Instruction*)operand)->getParent() == instr->getParent()) - { - // Recursively create a treeNode for it. - opTreeNode =this->buildTreeForInstruction((Instruction*)operand); - } - else if (ConstPoolVal *CPV = operand->castConstant()) - { - // 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; - numChildren++; - } + // Check if the operand is a data value, not an branch label, type, + // method or module. If the operand is an address type (i.e., label + // or method) that is used in an non-branching operation, e.g., `add'. + // that should be considered a data value. + + // Check latter condition here just to simplify the next IF. + bool includeAddressOperand = + (operand->isBasicBlock() || operand->isMethod()) + && !Inst->isTerminator(); + + if (includeAddressOperand || operand->isInstruction() || + operand->isConstant() || operand->isMethodArgument()) { + // 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. + // + // (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 (operand->isInstruction() && operand->use_size() == 1 && + ((Instruction*)operand)->getParent() == Inst->getParent()) { + // Recursively create a treeNode for it. + opTreeNode = buildTreeForInstruction((Instruction*)operand); + } else if (ConstPoolVal *CPV = operand->castConstant()) { + // 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; } + } //-------------------------------------------------------------------- // Add any selected operands as children in the tree. @@ -358,43 +271,40 @@ InstrForest::buildTreeForInstruction(Instruction* instr) // and VRegList nodes as internal nodes. //-------------------------------------------------------------------- - InstrTreeNode* parent = treeNode; // new VRegListNode(); - int n; + InstrTreeNode *parent = treeNode; - if (numChildren > 2) - { - unsigned instrOpcode = treeNode->getInstruction()->getOpcode(); - assert(instrOpcode == Instruction::PHINode || - instrOpcode == Instruction::Call || - instrOpcode == Instruction::Load || - instrOpcode == Instruction::Store || - instrOpcode == Instruction::GetElementPtr); - } + if (numChildren > 2) { + unsigned instrOpcode = treeNode->getInstruction()->getOpcode(); + assert(instrOpcode == Instruction::PHINode || + instrOpcode == Instruction::Call || + instrOpcode == Instruction::Load || + instrOpcode == Instruction::Store || + instrOpcode == Instruction::GetElementPtr); + } // Insert the first child as a direct child if (numChildren >= 1) - this->setLeftChild(parent, childArray[0]); + setLeftChild(parent, childArray[0]); + + 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(); - this->setRightChild(parent, listNode); - this->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); - this->setRightChild(parent, childArray[numChildren - 1]); - } + if (numChildren >= 2) { + assert(n == 1); + setRightChild(parent, childArray[numChildren - 1]); + } if (childArray != fixedChildArray) - { - delete[] childArray; - } + delete [] childArray; return treeNode; } diff --git a/test/Makefile b/test/Makefile index 8ca72f9aaf4..1370e2d04c5 100644 --- a/test/Makefile +++ b/test/Makefile @@ -4,7 +4,7 @@ LLCOPTS := -dsched t TESTS := $(wildcard *.ll) -LLCTESTS := $(shell /bin/ls *.ll | grep -v testmemory | grep -v testswitch | grep -v sumarray) +LLCTESTS := $(shell /bin/ls *.ll | grep -v testmemory | grep -v testswitch | grep -v sumarray | grep -v globalvars) test all : testasmdis testopt testcodegen -- 2.34.1