X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FSelectionDAG.cpp;h=758f112f78c6e83e4318b50f7c67da32ed994792;hb=ee4c619b3b28a42078fc8033e5dccd42fc6edd42;hp=9e42307fbec0143be2c5e721156c858bbd06883f;hpb=9468a9b6beed640eca64274c8dcc5aed3b94450b;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp index 9e42307fbec..758f112f78c 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -29,6 +29,7 @@ #include "llvm/Target/TargetLowering.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/ADT/SetVector.h" @@ -83,8 +84,10 @@ bool ConstantFPSDNode::isValueValidForType(MVT VT, // convert modifies in place, so make a copy. APFloat Val2 = APFloat(Val); - return Val2.convert(*MVTToAPFloatSemantics(VT), - APFloat::rmNearestTiesToEven) == APFloat::opOK; + bool losesInfo; + (void) Val2.convert(*MVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven, + &losesInfo); + return !losesInfo; } //===----------------------------------------------------------------------===// @@ -117,7 +120,7 @@ bool ISD::isBuildVectorAllOnes(const SDNode *N) { return false; } else if (isa(NotZero)) { if (!cast(NotZero)->getValueAPF(). - convertToAPInt().isAllOnesValue()) + bitcastToAPInt().isAllOnesValue()) return false; } else return false; @@ -213,7 +216,7 @@ ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { unsigned OldG = (Operation >> 1) & 1; return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits (OldL << 1) | // New G bit - (OldG << 2)); // New L bit. + (OldG << 2)); // New L bit. } /// getSetCCInverse - Return the operation corresponding to !(X op Y), where @@ -224,8 +227,10 @@ ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { Operation ^= 7; // Flip L, G, E bits, but not U. else Operation ^= 15; // Flip all of the condition bits. + if (Operation > ISD::SETTRUE2) - Operation &= ~8; // Don't let N and U bits get set. + Operation &= ~8; // Don't let N and U bits get set. + return ISD::CondCode(Operation); } @@ -503,7 +508,8 @@ static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) { /// encodeMemSDNodeFlags - Generic routine for computing a value for use in /// the CSE map that carries both alignment and volatility information. /// -static unsigned encodeMemSDNodeFlags(bool isVolatile, unsigned Alignment) { +static inline unsigned +encodeMemSDNodeFlags(bool isVolatile, unsigned Alignment) { return isVolatile | ((Log2_32(Alignment) + 1) << 1); } @@ -558,9 +564,10 @@ void SelectionDAG::RemoveDeadNodes(SmallVectorImpl &DeadNodes, if (Operand->use_empty()) DeadNodes.push_back(Operand); } - if (N->OperandsNeedDelete) { + + if (N->OperandsNeedDelete) delete[] N->OperandList; - } + N->OperandList = 0; N->NumOperands = 0; @@ -586,12 +593,14 @@ void SelectionDAG::DeleteNode(SDNode *N) { } void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { - - // Drop all of the operands and decrement used nodes use counts. + // Drop all of the operands and decrement used node's use counts. for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) I->getVal()->removeUser(std::distance(N->op_begin(), I), N); - if (N->OperandsNeedDelete) + + if (N->OperandsNeedDelete) { delete[] N->OperandList; + N->OperandList = 0; + } assert(N != AllNodes.begin()); NodeAllocator.Deallocate(AllNodes.remove(N)); @@ -614,11 +623,12 @@ bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { Erased = CondCodeNodes[cast(N)->get()] != 0; CondCodeNodes[cast(N)->get()] = 0; break; - case ISD::Symbol: - Erased = Symbols.erase(cast(N)->getSymbol()); + case ISD::ExternalSymbol: + Erased = ExternalSymbols.erase(cast(N)->getSymbol()); break; - case ISD::TargetSymbol: - Erased = TargetSymbols.erase(cast(N)->getSymbol()); + case ISD::TargetExternalSymbol: + Erased = + TargetExternalSymbols.erase(cast(N)->getSymbol()); break; case ISD::VALUETYPE: { MVT VT = cast(N)->getVT(); @@ -671,13 +681,13 @@ SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { case ISD::DBG_STOPPOINT: case ISD::EH_LABEL: case ISD::DECLARE: - return 0; // Never add these nodes. + return 0; // Never add these nodes. } // Check that remaining values produced are not flags. for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) if (N->getValueType(i) == MVT::Flag) - return 0; // Never CSE anything that produces a flag. + return 0; // Never CSE anything that produces a flag. SDNode *New = CSEMap.GetOrInsertNode(N); if (New != N) return New; // Node already existed. @@ -699,13 +709,13 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op, case ISD::DBG_LABEL: case ISD::DBG_STOPPOINT: case ISD::EH_LABEL: - return 0; // Never add these nodes. + return 0; // Never add these nodes. } // Check that remaining values produced are not flags. for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) if (N->getValueType(i) == MVT::Flag) - return 0; // Never CSE anything that produces a flag. + return 0; // Never CSE anything that produces a flag. SDValue Ops[] = { Op }; FoldingSetNodeID ID; @@ -725,7 +735,7 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, // Check that remaining values produced are not flags. for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) if (N->getValueType(i) == MVT::Flag) - return 0; // Never CSE anything that produces a flag. + return 0; // Never CSE anything that produces a flag. SDValue Ops[] = { Op1, Op2 }; FoldingSetNodeID ID; @@ -751,13 +761,13 @@ SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, case ISD::DBG_STOPPOINT: case ISD::EH_LABEL: case ISD::DECLARE: - return 0; // Never add these nodes. + return 0; // Never add these nodes. } // Check that remaining values produced are not flags. for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) if (N->getValueType(i) == MVT::Flag) - return 0; // Never CSE anything that produces a flag. + return 0; // Never CSE anything that produces a flag. FoldingSetNodeID ID; AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps); @@ -787,10 +797,14 @@ void SelectionDAG::VerifyNode(SDNode *N) { assert(N->getValueType(0).isVector() && "Wrong BUILD_VECTOR return type!"); assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() && "Wrong number of BUILD_VECTOR operands!"); - MVT EltVT = N->getValueType(0).getVectorElementType(); - for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) - assert(I->getSDValue().getValueType() == EltVT && - "Wrong BUILD_VECTOR operand type!"); + // FIXME: Change vector_shuffle to a variadic node with mask elements being + // operands of the node. Currently the mask is a BUILD_VECTOR passed as an + // operand, and it is not always possible to legalize it. Turning off the + // following checks at least makes it possible to legalize most of the time. +// MVT EltVT = N->getValueType(0).getVectorElementType(); +// for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) +// assert(I->getSDValue().getValueType() == EltVT && +// "Wrong BUILD_VECTOR operand type!"); break; } } @@ -829,8 +843,12 @@ void SelectionDAG::allnodes_clear() { while (!AllNodes.empty()) { SDNode *N = AllNodes.remove(AllNodes.begin()); N->SetNextInBucket(0); - if (N->OperandsNeedDelete) + + if (N->OperandsNeedDelete) { delete [] N->OperandList; + N->OperandList = 0; + } + NodeAllocator.Deallocate(N); } } @@ -841,8 +859,8 @@ void SelectionDAG::clear() { CSEMap.clear(); ExtendedValueTypeNodes.clear(); - Symbols.clear(); - TargetSymbols.clear(); + ExternalSymbols.clear(); + TargetExternalSymbols.clear(); std::fill(CondCodeNodes.begin(), CondCodeNodes.end(), static_cast(0)); std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(), @@ -955,10 +973,15 @@ SDValue SelectionDAG::getConstantFP(double Val, MVT VT, bool isTarget) { } SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, - MVT VT, int Offset, + MVT VT, int64_t Offset, bool isTargetGA) { unsigned Opc; + // Truncate (with sign-extension) the offset value to the pointer size. + unsigned BitWidth = TLI.getPointerTy().getSizeInBits(); + if (BitWidth < 64) + Offset = (Offset << (64 - BitWidth) >> (64 - BitWidth)); + const GlobalVariable *GVar = dyn_cast(GV); if (!GVar) { // If GV is an alias then use the aliasee for determining thread-localness. @@ -1018,6 +1041,9 @@ SDValue SelectionDAG::getJumpTable(int JTI, MVT VT, bool isTarget){ SDValue SelectionDAG::getConstantPool(Constant *C, MVT VT, unsigned Alignment, int Offset, bool isTarget) { + if (Alignment == 0) + Alignment = + TLI.getTargetData()->getPreferredTypeAlignmentShift(C->getType()); unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; FoldingSetNodeID ID; AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); @@ -1038,6 +1064,9 @@ SDValue SelectionDAG::getConstantPool(Constant *C, MVT VT, SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, MVT VT, unsigned Alignment, int Offset, bool isTarget) { + if (Alignment == 0) + Alignment = + TLI.getTargetData()->getPreferredTypeAlignmentShift(C->getType()); unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; FoldingSetNodeID ID; AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); @@ -1097,22 +1126,20 @@ SDValue SelectionDAG::getValueType(MVT VT) { return SDValue(N, 0); } -SDValue SelectionDAG::getSymbol(const char *Sym, MVT VT, - GlobalValue::LinkageTypes LT) { - SDNode *&N = Symbols[Sym]; +SDValue SelectionDAG::getExternalSymbol(const char *Sym, MVT VT) { + SDNode *&N = ExternalSymbols[Sym]; if (N) return SDValue(N, 0); - N = NodeAllocator.Allocate(); - new (N) SymbolSDNode(false, Sym, VT, LT); + N = NodeAllocator.Allocate(); + new (N) ExternalSymbolSDNode(false, Sym, VT); AllNodes.push_back(N); return SDValue(N, 0); } -SDValue SelectionDAG::getTargetSymbol(const char *Sym, MVT VT, - GlobalValue::LinkageTypes LT) { - SDNode *&N = TargetSymbols[Sym]; +SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT VT) { + SDNode *&N = TargetExternalSymbols[Sym]; if (N) return SDValue(N, 0); - N = NodeAllocator.Allocate(); - new (N) SymbolSDNode(true, Sym, VT, LT); + N = NodeAllocator.Allocate(); + new (N) ExternalSymbolSDNode(true, Sym, VT); AllNodes.push_back(N); return SDValue(N, 0); } @@ -2009,6 +2036,7 @@ unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ bool SelectionDAG::isVerifiedDebugInfoDesc(SDValue Op) const { GlobalAddressSDNode *GA = dyn_cast(Op); if (!GA) return false; + if (GA->getOffset() != 0) return false; GlobalVariable *GV = dyn_cast(GA->getGlobal()); if (!GV) return false; MachineModuleInfo *MMI = getMachineModuleInfo(); @@ -2118,29 +2146,32 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue Operand) { V.clearSign(); return getConstantFP(V, VT); case ISD::FP_ROUND: - case ISD::FP_EXTEND: + case ISD::FP_EXTEND: { + bool ignored; // This can return overflow, underflow, or inexact; we don't care. // FIXME need to be more flexible about rounding mode. (void)V.convert(*MVTToAPFloatSemantics(VT), - APFloat::rmNearestTiesToEven); + APFloat::rmNearestTiesToEven, &ignored); return getConstantFP(V, VT); + } case ISD::FP_TO_SINT: case ISD::FP_TO_UINT: { integerPart x; + bool ignored; assert(integerPartWidth >= 64); // FIXME need to be more flexible about rounding mode. APFloat::opStatus s = V.convertToInteger(&x, 64U, Opcode==ISD::FP_TO_SINT, - APFloat::rmTowardZero); + APFloat::rmTowardZero, &ignored); if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual break; return getConstant(x, VT); } case ISD::BIT_CONVERT: if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) - return getConstant((uint32_t)V.convertToAPInt().getZExtValue(), VT); + return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT); else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) - return getConstant(V.convertToAPInt().getZExtValue(), VT); + return getConstant(V.bitcastToAPInt().getZExtValue(), VT); break; } } @@ -2266,6 +2297,42 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue Operand) { return SDValue(N, 0); } +SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, + MVT VT, + ConstantSDNode *Cst1, + ConstantSDNode *Cst2) { + const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue(); + + switch (Opcode) { + case ISD::ADD: return getConstant(C1 + C2, VT); + case ISD::SUB: return getConstant(C1 - C2, VT); + case ISD::MUL: return getConstant(C1 * C2, VT); + case ISD::UDIV: + if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT); + break; + case ISD::UREM: + if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT); + break; + case ISD::SDIV: + if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT); + break; + case ISD::SREM: + if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT); + break; + case ISD::AND: return getConstant(C1 & C2, VT); + case ISD::OR: return getConstant(C1 | C2, VT); + case ISD::XOR: return getConstant(C1 ^ C2, VT); + case ISD::SHL: return getConstant(C1 << C2, VT); + case ISD::SRL: return getConstant(C1.lshr(C2), VT); + case ISD::SRA: return getConstant(C1.ashr(C2), VT); + case ISD::ROTL: return getConstant(C1.rotl(C2), VT); + case ISD::ROTR: return getConstant(C1.rotr(C2), VT); + default: break; + } + + return SDValue(); +} + SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, SDValue N1, SDValue N2) { ConstantSDNode *N1C = dyn_cast(N1.getNode()); @@ -2278,6 +2345,7 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, // Fold trivial token factors. if (N1.getOpcode() == ISD::EntryToken) return N2; if (N2.getOpcode() == ISD::EntryToken) return N1; + if (N1 == N2) return N1; break; case ISD::CONCAT_VECTORS: // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to @@ -2452,33 +2520,8 @@ SDValue SelectionDAG::getNode(unsigned Opcode, MVT VT, if (N1C) { if (N2C) { - const APInt &C1 = N1C->getAPIntValue(), &C2 = N2C->getAPIntValue(); - switch (Opcode) { - case ISD::ADD: return getConstant(C1 + C2, VT); - case ISD::SUB: return getConstant(C1 - C2, VT); - case ISD::MUL: return getConstant(C1 * C2, VT); - case ISD::UDIV: - if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT); - break; - case ISD::UREM : - if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT); - break; - case ISD::SDIV : - if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT); - break; - case ISD::SREM : - if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT); - break; - case ISD::AND : return getConstant(C1 & C2, VT); - case ISD::OR : return getConstant(C1 | C2, VT); - case ISD::XOR : return getConstant(C1 ^ C2, VT); - case ISD::SHL : return getConstant(C1 << C2, VT); - case ISD::SRL : return getConstant(C1.lshr(C2), VT); - case ISD::SRA : return getConstant(C1.ashr(C2), VT); - case ISD::ROTL : return getConstant(C1.rotl(C2), VT); - case ISD::ROTR : return getConstant(C1.rotr(C2), VT); - default: break; - } + SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C); + if (SV.getNode()) return SV; } else { // Cannonicalize constant to RHS if commutative if (isCommutativeBinOp(Opcode)) { std::swap(N1C, N2C); @@ -2909,7 +2952,7 @@ static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, // Expand memcpy to a series of load and store ops if the size operand falls // below a certain threshold. std::vector MemOps; - uint64_t Limit = -1; + uint64_t Limit = -1ULL; if (!AlwaysInline) Limit = TLI.getMaxStoresPerMemcpy(); unsigned DstAlign = Align; // Destination alignment can change. @@ -2967,7 +3010,7 @@ static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, // Expand memmove to a series of load and store ops if the size operand falls // below a certain threshold. std::vector MemOps; - uint64_t Limit = -1; + uint64_t Limit = -1ULL; if (!AlwaysInline) Limit = TLI.getMaxStoresPerMemmove(); unsigned DstAlign = Align; // Destination alignment can change. @@ -3098,8 +3141,8 @@ SDValue SelectionDAG::getMemcpy(SDValue Chain, SDValue Dst, Entry.Node = Size; Args.push_back(Entry); std::pair CallResult = TLI.LowerCallTo(Chain, Type::VoidTy, - false, false, false, CallingConv::C, false, - getSymbol("memcpy", TLI.getPointerTy()), + false, false, false, false, CallingConv::C, false, + getExternalSymbol("memcpy", TLI.getPointerTy()), Args, *this); return CallResult.second; } @@ -3143,8 +3186,8 @@ SDValue SelectionDAG::getMemmove(SDValue Chain, SDValue Dst, Entry.Node = Size; Args.push_back(Entry); std::pair CallResult = TLI.LowerCallTo(Chain, Type::VoidTy, - false, false, false, CallingConv::C, false, - getSymbol("memmove", TLI.getPointerTy()), + false, false, false, false, CallingConv::C, false, + getExternalSymbol("memmove", TLI.getPointerTy()), Args, *this); return CallResult.second; } @@ -3194,8 +3237,8 @@ SDValue SelectionDAG::getMemset(SDValue Chain, SDValue Dst, Args.push_back(Entry); std::pair CallResult = TLI.LowerCallTo(Chain, Type::VoidTy, - false, false, false, CallingConv::C, false, - getSymbol("memset", TLI.getPointerTy()), + false, false, false, false, CallingConv::C, false, + getExternalSymbol("memset", TLI.getPointerTy()), Args, *this); return CallResult.second; } @@ -3311,9 +3354,49 @@ SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps, return getNode(ISD::MERGE_VALUES, getVTList(&VTs[0], NumOps), Ops, NumOps); } +SDValue +SelectionDAG::getMemIntrinsicNode(unsigned Opcode, + const MVT *VTs, unsigned NumVTs, + const SDValue *Ops, unsigned NumOps, + MVT MemVT, const Value *srcValue, int SVOff, + unsigned Align, bool Vol, + bool ReadMem, bool WriteMem) { + return getMemIntrinsicNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps, + MemVT, srcValue, SVOff, Align, Vol, + ReadMem, WriteMem); +} + +SDValue +SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDVTList VTList, + const SDValue *Ops, unsigned NumOps, + MVT MemVT, const Value *srcValue, int SVOff, + unsigned Align, bool Vol, + bool ReadMem, bool WriteMem) { + // Memoize the node unless it returns a flag. + MemIntrinsicSDNode *N; + if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { + FoldingSetNodeID ID; + AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); + void *IP = 0; + if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) + return SDValue(E, 0); + + N = NodeAllocator.Allocate(); + new (N) MemIntrinsicSDNode(Opcode, VTList, Ops, NumOps, MemVT, + srcValue, SVOff, Align, Vol, ReadMem, WriteMem); + CSEMap.InsertNode(N, IP); + } else { + N = NodeAllocator.Allocate(); + new (N) MemIntrinsicSDNode(Opcode, VTList, Ops, NumOps, MemVT, + srcValue, SVOff, Align, Vol, ReadMem, WriteMem); + } + AllNodes.push_back(N); + return SDValue(N, 0); +} + SDValue SelectionDAG::getCall(unsigned CallingConv, bool IsVarArgs, bool IsTailCall, - SDVTList VTs, + bool IsInreg, SDVTList VTs, const SDValue *Operands, unsigned NumOperands) { // Do not include isTailCall in the folding set profile. FoldingSetNodeID ID; @@ -3329,7 +3412,7 @@ SelectionDAG::getCall(unsigned CallingConv, bool IsVarArgs, bool IsTailCall, return SDValue(E, 0); } SDNode *N = NodeAllocator.Allocate(); - new (N) CallSDNode(CallingConv, IsVarArgs, IsTailCall, + new (N) CallSDNode(CallingConv, IsVarArgs, IsTailCall, IsInreg, VTs, Operands, NumOperands); CSEMap.InsertNode(N, IP); AllNodes.push_back(N); @@ -4139,6 +4222,7 @@ SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, if (NumOps > N->NumOperands) { if (N->OperandsNeedDelete) delete[] N->OperandList; + if (N->isMachineOpcode()) { // We're creating a final node that will live unmorphed for the // remainder of the current SelectionDAG iteration, so we can allocate @@ -4553,38 +4637,74 @@ void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From, /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG /// based on their topological order. It returns the maximum id and a vector /// of the SDNodes* in assigned order by reference. -unsigned SelectionDAG::AssignTopologicalOrder(std::vector &TopOrder) { - unsigned DAGSize = AllNodes.size(); - std::vector Sources; +unsigned SelectionDAG::AssignTopologicalOrder() { + + unsigned DAGSize = 0; + + // SortedPos tracks the progress of the algorithm. Nodes before it are + // sorted, nodes after it are unsorted. When the algorithm completes + // it is at the end of the list. + allnodes_iterator SortedPos = allnodes_begin(); + + // Visit all the nodes. Add nodes with no operands to the TopOrder result + // array immediately. Annotate nodes that do have operands with their + // operand count. Before we do this, the Node Id fields of the nodes + // may contain arbitrary values. After, the Node Id fields for nodes + // before SortedPos will contain the topological sort index, and the + // Node Id fields for nodes At SortedPos and after will contain the + // count of outstanding operands. + for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) { + SDNode *N = I++; + unsigned Degree = N->getNumOperands(); + if (Degree == 0) { + // A node with no uses, add it to the result array immediately. + N->setNodeId(DAGSize++); + allnodes_iterator Q = N; + if (Q != SortedPos) + SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q)); + ++SortedPos; + } else { + // Temporarily use the Node Id as scratch space for the degree count. + N->setNodeId(Degree); + } + } - for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){ + // Visit all the nodes. As we iterate, moves nodes into sorted order, + // such that by the time the end is reached all nodes will be sorted. + for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) { SDNode *N = I; - unsigned Degree = N->use_size(); - // Temporarily use the Node Id as scratch space for the degree count. - N->setNodeId(Degree); - if (Degree == 0) - Sources.push_back(N); - } - - TopOrder.clear(); - TopOrder.reserve(DAGSize); - int Id = 0; - while (!Sources.empty()) { - SDNode *N = Sources.back(); - Sources.pop_back(); - TopOrder.push_back(N); - N->setNodeId(Id++); - for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { - SDNode *P = I->getVal(); + for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); + UI != UE; ++UI) { + SDNode *P = *UI; unsigned Degree = P->getNodeId(); --Degree; - P->setNodeId(Degree); - if (Degree == 0) - Sources.push_back(P); + if (Degree == 0) { + // All of P's operands are sorted, so P may sorted now. + P->setNodeId(DAGSize++); + if (P != SortedPos) + SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P)); + ++SortedPos; + } else { + // Update P's outstanding operand count. + P->setNodeId(Degree); + } } } - return Id; + assert(SortedPos == AllNodes.end() && + "Topological sort incomplete!"); + assert(AllNodes.front().getOpcode() == ISD::EntryToken && + "First node in topological sort is not the entry token!"); + assert(AllNodes.front().getNodeId() == 0 && + "First node in topological sort has non-zero id!"); + assert(AllNodes.front().getNumOperands() == 0 && + "First node in topological sort has operands!"); + assert(AllNodes.back().getNodeId() == (int)DAGSize-1 && + "Last node in topologic sort has unexpected id!"); + assert(AllNodes.back().use_empty() && + "Last node in topologic sort has users!"); + assert(DAGSize == allnodes_size() && "TopOrder result count mismatch!"); + return DAGSize; } @@ -4611,7 +4731,7 @@ void MemOperandSDNode::ANCHOR() {} void RegisterSDNode::ANCHOR() {} void DbgStopPointSDNode::ANCHOR() {} void LabelSDNode::ANCHOR() {} -void SymbolSDNode::ANCHOR() {} +void ExternalSymbolSDNode::ANCHOR() {} void CondCodeSDNode::ANCHOR() {} void ARG_FLAGSSDNode::ANCHOR() {} void VTSDNode::ANCHOR() {} @@ -4619,6 +4739,7 @@ void MemSDNode::ANCHOR() {} void LoadSDNode::ANCHOR() {} void StoreSDNode::ANCHOR() {} void AtomicSDNode::ANCHOR() {} +void MemIntrinsicSDNode::ANCHOR() {} void CallSDNode::ANCHOR() {} HandleSDNode::~HandleSDNode() { @@ -4626,7 +4747,7 @@ HandleSDNode::~HandleSDNode() { } GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA, - MVT VT, int o) + MVT VT, int64_t o) : SDNode(isa(GA) && cast(GA)->isThreadLocal() ? // Thread Local @@ -4648,6 +4769,17 @@ MemSDNode::MemSDNode(unsigned Opc, SDVTList VTs, MVT memvt, assert(isVolatile() == vol && "Volatile representation error!"); } +MemSDNode::MemSDNode(unsigned Opc, SDVTList VTs, const SDValue *Ops, + unsigned NumOps, MVT memvt, const Value *srcValue, + int SVO, unsigned alignment, bool vol) + : SDNode(Opc, VTs, Ops, NumOps), + MemoryVT(memvt), SrcValue(srcValue), SVOffset(SVO), + Flags(vol | ((Log2_32(alignment) + 1) << 1)) { + assert(isPowerOf2_32(alignment) && "Alignment is not a power of 2!"); + assert(getAlignment() == alignment && "Alignment representation error!"); + assert(isVolatile() == vol && "Volatile representation error!"); +} + /// getMemOperand - Return a MachineMemOperand object describing the memory /// reference performed by this memory reference. MachineMemOperand MemSDNode::getMemOperand() const { @@ -4656,10 +4788,15 @@ MachineMemOperand MemSDNode::getMemOperand() const { Flags = MachineMemOperand::MOLoad; else if (isa(this)) Flags = MachineMemOperand::MOStore; - else { - assert(isa(this) && "Unknown MemSDNode opcode!"); + else if (isa(this)) { Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore; } + else { + const MemIntrinsicSDNode* MemIntrinNode = dyn_cast(this); + assert(MemIntrinNode && "Unknown MemSDNode opcode!"); + if (MemIntrinNode->readMem()) Flags |= MachineMemOperand::MOLoad; + if (MemIntrinNode->writeMem()) Flags |= MachineMemOperand::MOStore; + } int Size = (getMemoryVT().getSizeInBits() + 7) >> 3; if (isVolatile()) Flags |= MachineMemOperand::MOVolatile; @@ -4915,14 +5052,14 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const { case ISD::FrameIndex: return "FrameIndex"; case ISD::JumpTable: return "JumpTable"; case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE"; - case ISD::RETURNADDR: return "RETURNADDR"; - case ISD::FRAMEADDR: return "FRAMEADDR"; + case ISD::RETURNADDR: return "RETURNADDR"; + case ISD::FRAMEADDR: return "FRAMEADDR"; case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET"; case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR"; - case ISD::EHSELECTION: return "EHSELECTION"; - case ISD::EH_RETURN: return "EH_RETURN"; + case ISD::EHSELECTION: return "EHSELECTION"; + case ISD::EH_RETURN: return "EH_RETURN"; case ISD::ConstantPool: return "ConstantPool"; - case ISD::Symbol: return "Symbol"; + case ISD::ExternalSymbol: return "ExternalSymbol"; case ISD::INTRINSIC_WO_CHAIN: { unsigned IID = cast(getOperand(0))->getZExtValue(); return Intrinsic::getName((Intrinsic::ID)IID); @@ -4941,7 +5078,7 @@ std::string SDNode::getOperationName(const SelectionDAG *G) const { case ISD::TargetFrameIndex: return "TargetFrameIndex"; case ISD::TargetJumpTable: return "TargetJumpTable"; case ISD::TargetConstantPool: return "TargetConstantPool"; - case ISD::TargetSymbol: return "TargetSymbol"; + case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; case ISD::CopyToReg: return "CopyToReg"; case ISD::CopyFromReg: return "CopyFromReg"; @@ -5191,12 +5328,12 @@ void SDNode::print(raw_ostream &OS, const SelectionDAG *G) const { OS << '<' << CSDN->getValueAPF().convertToDouble() << '>'; else { OS << "getValueAPF().convertToAPInt().dump(); + CSDN->getValueAPF().bitcastToAPInt().dump(); OS << ")>"; } } else if (const GlobalAddressSDNode *GADN = dyn_cast(this)) { - int offset = GADN->getOffset(); + int64_t offset = GADN->getOffset(); OS << '<'; WriteAsOperand(OS, GADN->getGlobal()); OS << '>'; @@ -5231,23 +5368,9 @@ void SDNode::print(raw_ostream &OS, const SelectionDAG *G) const { } else { OS << " #" << R->getReg(); } - } else if (const SymbolSDNode *S = - dyn_cast(this)) { - OS << "'" << S->getSymbol() << "' "; - - switch (S->getLinkage()) { - default: assert(0 && "Invalid linkage type!"); break; - case GlobalValue::ExternalLinkage: OS << "[external]"; break; - case GlobalValue::LinkOnceLinkage: OS << "[once]"; break; - case GlobalValue::WeakLinkage: OS << "[weak]"; break; - case GlobalValue::AppendingLinkage: OS << "[appending]"; break; - case GlobalValue::InternalLinkage: OS << "[internal]"; break; - case GlobalValue::DLLImportLinkage: OS << "[dllimport]"; break; - case GlobalValue::DLLExportLinkage: OS << "[dllexport]"; break; - case GlobalValue::ExternalWeakLinkage: OS << "[externweak]"; break; - case GlobalValue::GhostLinkage: OS << "[ghost]"; break; - case GlobalValue::CommonLinkage: OS << "[common]"; break; - } + } else if (const ExternalSymbolSDNode *ES = + dyn_cast(this)) { + OS << "'" << ES->getSymbol() << "'"; } else if (const SrcValueSDNode *M = dyn_cast(this)) { if (M->getValue()) OS << "<" << M->getValue() << ">";