X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAG.cpp;h=1a1243285976c00a7f832fc681b53f048d5e60cf;hb=e10efce22502d1a1855d25baf1458660f4ba6f33;hp=ed564b2b7b89c1a49a84cb4bd61fd0e07bf0a5c2;hpb=26471c48b3d49bdbcfcc05cb9a575b5fa123fbbf;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index ed564b2b7b8..1a124328597 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -10,7 +10,6 @@ // This implements the SelectionDAG class. // //===----------------------------------------------------------------------===// - #include "llvm/CodeGen/SelectionDAG.h" #include "llvm/Constants.h" #include "llvm/GlobalAlias.h" @@ -465,14 +464,15 @@ void SelectionDAG::RemoveDeadNodes() { // no cycles in the graph. for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { SDNode *Operand = I->Val; - Operand->removeUser(N); + Operand->removeUser(std::distance(N->op_begin(), I), N); // Now that we removed this operand, see if there are no uses of it left. if (Operand->use_empty()) DeadNodes.push_back(Operand); } - if (N->OperandsNeedDelete) + if (N->OperandsNeedDelete) { delete[] N->OperandList; + } N->OperandList = 0; N->NumOperands = 0; @@ -504,14 +504,15 @@ void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){ // no cycles in the graph. for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { SDNode *Operand = I->Val; - Operand->removeUser(N); + Operand->removeUser(std::distance(N->op_begin(), I), N); // Now that we removed this operand, see if there are no uses of it left. if (Operand->use_empty()) DeadNodes.push_back(Operand); } - if (N->OperandsNeedDelete) + if (N->OperandsNeedDelete) { delete[] N->OperandList; + } N->OperandList = 0; N->NumOperands = 0; @@ -538,9 +539,10 @@ void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { // Drop all of the operands and decrement used nodes use counts. for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) - I->Val->removeUser(N); - if (N->OperandsNeedDelete) + I->Val->removeUser(std::distance(N->op_begin(), I), N); + if (N->OperandsNeedDelete) { delete[] N->OperandList; + } N->OperandList = 0; N->NumOperands = 0; @@ -701,8 +703,9 @@ SelectionDAG::~SelectionDAG() { while (!AllNodes.empty()) { SDNode *N = AllNodes.begin(); N->SetNextInBucket(0); - if (N->OperandsNeedDelete) + if (N->OperandsNeedDelete) { delete [] N->OperandList; + } N->OperandList = 0; N->NumOperands = 0; AllNodes.pop_front(); @@ -2444,10 +2447,12 @@ SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain, return SDOperand(N, 0); } -SDOperand SelectionDAG::getLoad(MVT::ValueType VT, - SDOperand Chain, SDOperand Ptr, - const Value *SV, int SVOffset, - bool isVolatile, unsigned Alignment) { +SDOperand +SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, + MVT::ValueType VT, SDOperand Chain, + SDOperand Ptr, SDOperand Offset, + const Value *SV, int SVOffset, MVT::ValueType EVT, + bool isVolatile, unsigned Alignment) { if (Alignment == 0) { // Ensure that codegen never sees alignment 0 const Type *Ty = 0; if (VT != MVT::iPTR) { @@ -2456,81 +2461,69 @@ SDOperand SelectionDAG::getLoad(MVT::ValueType VT, const PointerType *PT = dyn_cast(SV->getType()); assert(PT && "Value for load must be a pointer"); Ty = PT->getElementType(); - } + } assert(Ty && "Could not get type information for load"); Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); } - SDVTList VTs = getVTList(VT, MVT::Other); - SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); - SDOperand Ops[] = { Chain, Ptr, Undef }; + + if (VT == EVT) { + ExtType = ISD::NON_EXTLOAD; + } else if (ExtType == ISD::NON_EXTLOAD) { + assert(VT == EVT && "Non-extending load from different memory type!"); + } else { + // Extending load. + if (MVT::isVector(VT)) + assert(EVT == MVT::getVectorElementType(VT) && "Invalid vector extload!"); + else + assert(MVT::getSizeInBits(EVT) < MVT::getSizeInBits(VT) && + "Should only be an extending load, not truncating!"); + assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) && + "Cannot sign/zero extend a FP/Vector load!"); + assert(MVT::isInteger(VT) == MVT::isInteger(EVT) && + "Cannot convert from FP to Int or Int -> FP!"); + } + + bool Indexed = AM != ISD::UNINDEXED; + assert(Indexed || Offset.getOpcode() == ISD::UNDEF && + "Unindexed load with an offset!"); + + SDVTList VTs = Indexed ? + getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other); + SDOperand Ops[] = { Chain, Ptr, Offset }; FoldingSetNodeID ID; AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); - ID.AddInteger(ISD::UNINDEXED); - ID.AddInteger(ISD::NON_EXTLOAD); - ID.AddInteger((unsigned int)VT); + ID.AddInteger(AM); + ID.AddInteger(ExtType); + ID.AddInteger((unsigned int)EVT); ID.AddInteger(Alignment); ID.AddInteger(isVolatile); void *IP = 0; if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) return SDOperand(E, 0); - SDNode *N = new LoadSDNode(Ops, VTs, ISD::UNINDEXED, - ISD::NON_EXTLOAD, VT, SV, SVOffset, Alignment, - isVolatile); + SDNode *N = new LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset, + Alignment, isVolatile); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); return SDOperand(N, 0); } +SDOperand SelectionDAG::getLoad(MVT::ValueType VT, + SDOperand Chain, SDOperand Ptr, + const Value *SV, int SVOffset, + bool isVolatile, unsigned Alignment) { + SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); + return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, Chain, Ptr, Undef, + SV, SVOffset, VT, isVolatile, Alignment); +} + SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, const Value *SV, int SVOffset, MVT::ValueType EVT, bool isVolatile, unsigned Alignment) { - // If they are asking for an extending load from/to the same thing, return a - // normal load. - if (VT == EVT) - return getLoad(VT, Chain, Ptr, SV, SVOffset, isVolatile, Alignment); - - if (MVT::isVector(VT)) - assert(EVT == MVT::getVectorElementType(VT) && "Invalid vector extload!"); - else - assert(MVT::getSizeInBits(EVT) < MVT::getSizeInBits(VT) && - "Should only be an extending load, not truncating!"); - assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) && - "Cannot sign/zero extend a FP/Vector load!"); - assert(MVT::isInteger(VT) == MVT::isInteger(EVT) && - "Cannot convert from FP to Int or Int -> FP!"); - - if (Alignment == 0) { // Ensure that codegen never sees alignment 0 - const Type *Ty = 0; - if (VT != MVT::iPTR) { - Ty = MVT::getTypeForValueType(VT); - } else if (SV) { - const PointerType *PT = dyn_cast(SV->getType()); - assert(PT && "Value for load must be a pointer"); - Ty = PT->getElementType(); - } - assert(Ty && "Could not get type information for load"); - Alignment = TLI.getTargetData()->getABITypeAlignment(Ty); - } - SDVTList VTs = getVTList(VT, MVT::Other); SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); - SDOperand Ops[] = { Chain, Ptr, Undef }; - FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); - ID.AddInteger(ISD::UNINDEXED); - ID.AddInteger(ExtType); - ID.AddInteger((unsigned int)EVT); - ID.AddInteger(Alignment); - ID.AddInteger(isVolatile); - void *IP = 0; - if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new LoadSDNode(Ops, VTs, ISD::UNINDEXED, ExtType, EVT, - SV, SVOffset, Alignment, isVolatile); - CSEMap.InsertNode(N, IP); - AllNodes.push_back(N); - return SDOperand(N, 0); + return getLoad(ISD::UNINDEXED, ExtType, VT, Chain, Ptr, Undef, + SV, SVOffset, EVT, isVolatile, Alignment); } SDOperand @@ -2539,26 +2532,10 @@ SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base, LoadSDNode *LD = cast(OrigLoad); assert(LD->getOffset().getOpcode() == ISD::UNDEF && "Load is already a indexed load!"); - MVT::ValueType VT = OrigLoad.getValueType(); - SDVTList VTs = getVTList(VT, Base.getValueType(), MVT::Other); - SDOperand Ops[] = { LD->getChain(), Base, Offset }; - FoldingSetNodeID ID; - AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); - ID.AddInteger(AM); - ID.AddInteger(LD->getExtensionType()); - ID.AddInteger((unsigned int)(LD->getMemoryVT())); - ID.AddInteger(LD->getAlignment()); - ID.AddInteger(LD->isVolatile()); - void *IP = 0; - if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) - return SDOperand(E, 0); - SDNode *N = new LoadSDNode(Ops, VTs, AM, - LD->getExtensionType(), LD->getMemoryVT(), - LD->getSrcValue(), LD->getSrcValueOffset(), - LD->getAlignment(), LD->isVolatile()); - CSEMap.InsertNode(N, IP); - AllNodes.push_back(N); - return SDOperand(N, 0); + return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), + LD->getChain(), Base, Offset, LD->getSrcValue(), + LD->getSrcValueOffset(), LD->getMemoryVT(), + LD->isVolatile(), LD->getAlignment()); } SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val, @@ -2920,9 +2897,10 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op) { RemoveNodeFromCSEMaps(N); // Now we update the operands. - N->OperandList[0].Val->removeUser(N); - Op.Val->addUser(N); + N->OperandList[0].Val->removeUser(0, N); N->OperandList[0] = Op; + N->OperandList[0].setUser(N); + Op.Val->addUser(0, N); // If this gets put into a CSE map, add it. if (InsertPos) CSEMap.InsertNode(N, InsertPos); @@ -2949,14 +2927,16 @@ UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { // Now we update the operands. if (N->OperandList[0] != Op1) { - N->OperandList[0].Val->removeUser(N); - Op1.Val->addUser(N); + N->OperandList[0].Val->removeUser(0, N); N->OperandList[0] = Op1; + N->OperandList[0].setUser(N); + Op1.Val->addUser(0, N); } if (N->OperandList[1] != Op2) { - N->OperandList[1].Val->removeUser(N); - Op2.Val->addUser(N); + N->OperandList[1].Val->removeUser(1, N); N->OperandList[1] = Op2; + N->OperandList[1].setUser(N); + Op2.Val->addUser(1, N); } // If this gets put into a CSE map, add it. @@ -2984,7 +2964,6 @@ UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, return UpdateNodeOperands(N, Ops, 5); } - SDOperand SelectionDAG:: UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) { SDNode *N = InN.Val; @@ -3015,9 +2994,10 @@ UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) { // Now we update the operands. for (unsigned i = 0; i != NumOps; ++i) { if (N->OperandList[i] != Ops[i]) { - N->OperandList[i].Val->removeUser(N); - Ops[i].Val->addUser(N); + N->OperandList[i].Val->removeUser(i, N); N->OperandList[i] = Ops[i]; + N->OperandList[i].setUser(N); + Ops[i].Val->addUser(i, N); } } @@ -3026,7 +3006,6 @@ UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) { return InN; } - /// MorphNodeTo - This frees the operands of the current node, resets the /// opcode, types, and operands to the specified value. This should only be /// used by the SelectionDAG class. @@ -3039,13 +3018,14 @@ void SDNode::MorphNodeTo(unsigned Opc, SDVTList L, // Clear the operands list, updating used nodes to remove this from their // use list. for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) - I->Val->removeUser(this); + I->Val->removeUser(std::distance(op_begin(), I), this); // If NumOps is larger than the # of operands we currently have, reallocate // the operand list. if (NumOps > NumOperands) { - if (OperandsNeedDelete) + if (OperandsNeedDelete) { delete [] OperandList; + } OperandList = new SDOperand[NumOps]; OperandsNeedDelete = true; } @@ -3055,8 +3035,10 @@ void SDNode::MorphNodeTo(unsigned Opc, SDVTList L, for (unsigned i = 0, e = NumOps; i != e; ++i) { OperandList[i] = Ops[i]; + OperandList[i].setUser(this); SDNode *N = OperandList[i].Val; - N->Uses.push_back(this); + N->addUser(i, this); + ++N->UsesSize; } } @@ -3324,21 +3306,27 @@ void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To, assert(From->getNumValues() == 1 && FromN.ResNo == 0 && "Cannot replace with this method!"); assert(From != To.Val && "Cannot replace uses of with self"); - + + SmallSetVector Users; while (!From->use_empty()) { - // Process users until they are all gone. - SDNode *U = *From->use_begin(); - + SDNode::use_iterator UI = From->use_begin(); + SDNode *U = UI->getUser(); + + // Remember that this node is about to morph. + if (Users.count(U)) + continue; + Users.insert(U); // This node is about to morph, remove its old self from the CSE maps. RemoveNodeFromCSEMaps(U); - - for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; - I != E; ++I) + int operandNum = 0; + for (SDNode::op_iterator I = U->op_begin(), E = U->op_end(); + I != E; ++I, ++operandNum) if (I->Val == From) { - From->removeUser(U); + From->removeUser(operandNum, U); *I = To; - To.Val->addUser(U); - } + I->setUser(U); + To.Val->addUser(operandNum, U); + } // Now that we have modified U, add it back to the CSE maps. If it already // exists there, recursively merge the results together. @@ -3372,21 +3360,26 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), UpdateListener); + SmallSetVector Users; while (!From->use_empty()) { - // Process users until they are all gone. - SDNode *U = *From->use_begin(); - + SDNode::use_iterator UI = From->use_begin(); + SDNode *U = UI->getUser(); + + // Remember that this node is about to morph. + if (Users.count(U)) + continue; + Users.insert(U); // This node is about to morph, remove its old self from the CSE maps. RemoveNodeFromCSEMaps(U); - - for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; - I != E; ++I) + int operandNum = 0; + for (SDNode::op_iterator I = U->op_begin(), E = U->op_end(); + I != E; ++I, ++operandNum) if (I->Val == From) { - From->removeUser(U); + From->removeUser(operandNum, U); I->Val = To; - To->addUser(U); + To->addUser(operandNum, U); } - + // Now that we have modified U, add it back to the CSE maps. If it already // exists there, recursively merge the results together. if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { @@ -3415,22 +3408,28 @@ void SelectionDAG::ReplaceAllUsesWith(SDNode *From, if (From->getNumValues() == 1) // Handle the simple case efficiently. return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener); + SmallSetVector Users; while (!From->use_empty()) { - // Process users until they are all gone. - SDNode *U = *From->use_begin(); - + SDNode::use_iterator UI = From->use_begin(); + SDNode *U = UI->getUser(); + + // Remember that this node is about to morph. + if (Users.count(U)) + continue; + Users.insert(U); // This node is about to morph, remove its old self from the CSE maps. RemoveNodeFromCSEMaps(U); - - for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; - I != E; ++I) + int operandNum = 0; + for (SDNode::op_iterator I = U->op_begin(), E = U->op_end(); + I != E; ++I, ++operandNum) if (I->Val == From) { const SDOperand &ToOp = To[I->ResNo]; - From->removeUser(U); + From->removeUser(operandNum, U); *I = ToOp; - ToOp.Val->addUser(U); + I->setUser(U); + ToOp.Val->addUser(operandNum, U); } - + // Now that we have modified U, add it back to the CSE maps. If it already // exists there, recursively merge the results together. if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { @@ -3460,7 +3459,7 @@ namespace { ChainedSetUpdaterListener(SmallSetVector &set, SelectionDAG::DAGUpdateListener *chain) : Set(set), Chain(chain) {} - + virtual void NodeDeleted(SDNode *N) { Set.remove(N); if (Chain) Chain->NodeDeleted(N); @@ -3488,7 +3487,13 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, // Get all of the users of From.Val. We want these in a nice, // deterministically ordered and uniqued set, so we use a SmallSetVector. - SmallSetVector Users(From.Val->use_begin(), From.Val->use_end()); + SmallSetVector Users; + for (SDNode::use_iterator UI = From.Val->use_begin(), + E = From.Val->use_end(); UI != E; ++UI) { + SDNode *User = UI->getUser(); + if (!Users.count(User)) + Users.insert(User); + } // When one of the recursive merges deletes nodes from the graph, we need to // make sure that UpdateListener is notified *and* that the node is removed @@ -3502,7 +3507,7 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, Users.pop_back(); // Scan for an operand that matches From. - SDOperand *Op = User->OperandList, *E = User->OperandList+User->NumOperands; + SDNode::op_iterator Op = User->op_begin(), E = User->op_end(); for (; Op != E; ++Op) if (*Op == From) break; @@ -3516,9 +3521,10 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, // Update all operands that match "From" in case there are multiple uses. for (; Op != E; ++Op) { if (*Op == From) { - From.Val->removeUser(User); - *Op = To; - To.Val->addUser(User); + From.Val->removeUser(Op-User->op_begin(), User); + *Op = To; + Op->setUser(User); + To.Val->addUser(Op-User->op_begin(), User); } } @@ -3698,16 +3704,13 @@ bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { SmallPtrSet UsersHandled; - for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) { - SDNode *User = *UI; - if (User->getNumOperands() == 1 || - UsersHandled.insert(User)) // First time we've seen this? - for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) - if (User->getOperand(i) == TheValue) { - if (NUses == 0) - return false; // too many uses - --NUses; - } + // TODO: Only iterate over uses of a given value of the node + for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { + if (*UI == TheValue) { + if (NUses == 0) + return false; + --NUses; + } } // Found exactly the right number of uses? @@ -3726,8 +3729,8 @@ bool SDNode::hasAnyUseOfValue(unsigned Value) const { SmallPtrSet UsersHandled; - for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) { - SDNode *User = *UI; + for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { + SDNode *User = UI->getUser(); if (User->getNumOperands() == 1 || UsersHandled.insert(User)) // First time we've seen this? for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) @@ -3745,7 +3748,7 @@ bool SDNode::hasAnyUseOfValue(unsigned Value) const { bool SDNode::isOnlyUseOf(SDNode *N) const { bool Seen = false; for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { - SDNode *User = *I; + SDNode *User = I->getUser(); if (User == this) Seen = true; else @@ -3757,7 +3760,7 @@ bool SDNode::isOnlyUseOf(SDNode *N) const { /// isOperand - Return true if this node is an operand of N. /// -bool SDOperand::isOperandOf(SDNode *N) const { +bool SDOperandImpl::isOperandOf(SDNode *N) const { for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) if (*this == N->getOperand(i)) return true; @@ -3776,7 +3779,7 @@ bool SDNode::isOperandOf(SDNode *N) const { /// side-effecting instructions. In practice, this looks through token /// factors and non-volatile loads. In order to remain efficient, this only /// looks a couple of nodes in, it does not do an exhaustive search. -bool SDOperand::reachesChainWithoutSideEffects(SDOperand Dest, +bool SDOperandImpl::reachesChainWithoutSideEffects(SDOperandImpl Dest, unsigned Depth) const { if (*this == Dest) return true;