X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FLegalizeTypes.cpp;h=28f7a4db9ca25c96fd8e6a71bafb875a35c68220;hb=b169426272b85ce28a9a56d13154e61b158fc47a;hp=704c537bb45ef7751260d2c45a4d28bacda08074;hpb=87c8a8f304d1ee72829086ce2c41a8fa3813ba6a;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp index 704c537bb45..28f7a4db9ca 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp @@ -15,7 +15,7 @@ #include "LegalizeTypes.h" #include "llvm/CallingConv.h" -#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SetVector.h" #include "llvm/Support/CommandLine.h" #include "llvm/Target/TargetData.h" using namespace llvm; @@ -81,7 +81,7 @@ void DAGTypeLegalizer::PerformExpensiveChecks() { // Check that remapped values are only used by nodes marked NewNode. for (SDNode::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; ++UI) - if (UI.getUse().getSDValue().getResNo() == i) + if (UI.getUse().getResNo() == i) assert(UI->getNodeId() == NewNode && "Remapped value has non-trivial use!"); @@ -328,14 +328,21 @@ ScanOperands: continue; // The node morphed - this is equivalent to legalizing by replacing every - // value of N with the corresponding value of M. So do that now. - N->setNodeId(ReadyToProcess); + // value of N with the corresponding value of M. So do that now. However + // there is no need to remember the replacement - morphing will make sure + // it is never used non-trivially. assert(N->getNumValues() == M->getNumValues() && "Node morphing changed the number of results!"); for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) - // Replacing the value takes care of remapping the new value. - ReplaceValueWith(SDValue(N, i), SDValue(M, i)); - // Fall through. + // Replacing the value takes care of remapping the new value. Do the + // replacement without recording it in ReplacedValues. This does not + // expunge From but that is fine - it is not really a new node. + ReplaceValueWithHelper(SDValue(N, i), SDValue(M, i)); + assert(N->getNodeId() == NewNode && "Unexpected node state!"); + // The node continues to live on as part of the NewNode fungus that + // grows on top of the useful nodes. Nothing more needs to be done + // with it - move on to the next node. + continue; } if (i == NumOperands) { @@ -574,6 +581,12 @@ void DAGTypeLegalizer::ExpungeNode(SDNode *N) { RemapValue(I->second); } + for (DenseMap::iterator I = WidenedVectors.begin(), + E = WidenedVectors.end(); I != E; ++I) { + assert(I->first.getNode() != N); + RemapValue(I->second); + } + for (DenseMap >::iterator I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){ assert(I->first.getNode() != N); @@ -622,13 +635,11 @@ namespace { class VISIBILITY_HIDDEN NodeUpdateListener : public SelectionDAG::DAGUpdateListener { DAGTypeLegalizer &DTL; - SmallVectorImpl &NodesToAnalyze; - SmallPtrSet &NodesDeleted; + SmallSetVector &NodesToAnalyze; public: explicit NodeUpdateListener(DAGTypeLegalizer &dtl, - SmallVectorImpl &nta, - SmallPtrSet &nd) - : DTL(dtl), NodesToAnalyze(nta), NodesDeleted(nd) {} + SmallSetVector &nta) + : DTL(dtl), NodesToAnalyze(nta) {} virtual void NodeDeleted(SDNode *N, SDNode *E) { assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && @@ -640,15 +651,15 @@ namespace { DTL.NoteDeletion(N, E); // In theory the deleted node could also have been scheduled for analysis. - // So add it to the set of nodes which will not be analyzed. - NodesDeleted.insert(N); + // So remove it from the set of nodes which will be analyzed. + NodesToAnalyze.remove(N); // In general nothing needs to be done for E, since it didn't change but // only gained new uses. However N -> E was just added to ReplacedValues, // and the result of a ReplacedValues mapping is not allowed to be marked // NewNode. So if E is marked NewNode, then it needs to be analyzed. if (E->getNodeId() == DAGTypeLegalizer::NewNode) - NodesToAnalyze.push_back(E); + NodesToAnalyze.insert(E); } virtual void NodeUpdated(SDNode *N) { @@ -658,49 +669,40 @@ namespace { assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && N->getNodeId() != DAGTypeLegalizer::Processed && "Invalid node ID for RAUW deletion!"); - NodesToAnalyze.push_back(N); + N->setNodeId(DAGTypeLegalizer::NewNode); + NodesToAnalyze.insert(N); } }; } -/// ReplaceValueWith - The specified value was legalized to the specified other -/// value. Update the DAG and NodeIds replacing any uses of From to use To -/// instead. -void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { - assert(From.getNode()->getNodeId() == ReadyToProcess && - "Only the node being processed may be remapped!"); +/// ReplaceValueWithHelper - Internal helper for ReplaceValueWith. Updates the +/// DAG causing any uses of From to use To instead, but without expunging From +/// or recording the replacement in ReplacedValues. Do not call directly unless +/// you really know what you are doing! +void DAGTypeLegalizer::ReplaceValueWithHelper(SDValue From, SDValue To) { assert(From.getNode() != To.getNode() && "Potential legalization loop!"); // If expansion produced new nodes, make sure they are properly marked. - ExpungeNode(From.getNode()); AnalyzeNewValue(To); // Expunges To. // Anything that used the old node should now use the new one. Note that this // can potentially cause recursive merging. - SmallVector NodesToAnalyze; - SmallPtrSet NodesDeleted; - NodeUpdateListener NUL(*this, NodesToAnalyze, NodesDeleted); + SmallSetVector NodesToAnalyze; + NodeUpdateListener NUL(*this, NodesToAnalyze); DAG.ReplaceAllUsesOfValueWith(From, To, &NUL); - // The old node may still be present in a map like ExpandedIntegers or - // PromotedIntegers. Inform maps about the replacement. - ReplacedValues[From] = To; - // Process the list of nodes that need to be reanalyzed. while (!NodesToAnalyze.empty()) { SDNode *N = NodesToAnalyze.back(); NodesToAnalyze.pop_back(); - - // Do not analyze deleted nodes! - if (NodesDeleted.count(N)) + if (N->getNodeId() != DAGTypeLegalizer::NewNode) + // The node was analyzed while reanalyzing an earlier node - it is safe to + // skip. Note that this is not a morphing node - otherwise it would still + // be marked NewNode. continue; // Analyze the node's operands and recalculate the node ID. - assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess && - N->getNodeId() != DAGTypeLegalizer::Processed && - "Invalid node ID for RAUW analysis!"); - N->setNodeId(NewNode); SDNode *M = AnalyzeNewNode(N); if (M != N) { // The node morphed into a different node. Make everyone use the new node @@ -720,6 +722,25 @@ void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { } } +/// ReplaceValueWith - The specified value was legalized to the specified other +/// value. Update the DAG and NodeIds replacing any uses of From to use To +/// instead. +void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) { + assert(From.getNode()->getNodeId() == ReadyToProcess && + "Only the node being processed may be remapped!"); + + // If expansion produced new nodes, make sure they are properly marked. + ExpungeNode(From.getNode()); + AnalyzeNewValue(To); // Expunges To. + + // The old node may still be present in a map like ExpandedIntegers or + // PromotedIntegers. Inform maps about the replacement. + ReplacedValues[From] = To; + + // Do the replacement. + ReplaceValueWithHelper(From, To); +} + void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) { AnalyzeNewValue(Result); @@ -817,7 +838,7 @@ void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) { AnalyzeNewValue(Result); SDValue &OpEntry = WidenedVectors[Op]; - assert(OpEntry.getNode() == 0 && "Node is already promoted!"); + assert(OpEntry.getNode() == 0 && "Node already widened!"); OpEntry = Result; } @@ -833,30 +854,42 @@ void DAGTypeLegalizer::SetIgnoredNodeResult(SDNode* N) { /// BitConvertToInteger - Convert to an integer of the same size. SDValue DAGTypeLegalizer::BitConvertToInteger(SDValue Op) { unsigned BitWidth = Op.getValueType().getSizeInBits(); - return DAG.getNode(ISD::BIT_CONVERT, MVT::getIntegerVT(BitWidth), Op); + return DAG.getNode(ISD::BIT_CONVERT, Op.getDebugLoc(), + MVT::getIntegerVT(BitWidth), Op); } SDValue DAGTypeLegalizer::CreateStackStoreLoad(SDValue Op, MVT DestVT) { + DebugLoc dl = Op.getDebugLoc(); // Create the stack frame object. Make sure it is aligned for both // the source and destination types. SDValue StackPtr = DAG.CreateStackTemporary(Op.getValueType(), DestVT); // Emit a store to the stack slot. - SDValue Store = DAG.getStore(DAG.getEntryNode(), Op, StackPtr, NULL, 0); + SDValue Store = DAG.getStore(DAG.getEntryNode(), dl, Op, StackPtr, NULL, 0); // Result is a load from the stack slot. - return DAG.getLoad(DestVT, Store, StackPtr, NULL, 0); + return DAG.getLoad(DestVT, dl, Store, StackPtr, NULL, 0); } /// CustomLowerResults - Replace the node's results with custom code provided /// by the target and return "true", or do nothing and return "false". -bool DAGTypeLegalizer::CustomLowerResults(SDNode *N, unsigned ResNo) { +/// The last parameter is FALSE if we are dealing with a node with legal +/// result types and illegal operand. The second parameter denotes the type of +/// illegal OperandNo in that case. +/// The last parameter being TRUE means we are dealing with a +/// node with illegal result types. The second parameter denotes the type of +/// illegal ResNo in that case. +bool DAGTypeLegalizer::CustomLowerResults(SDNode *N, MVT VT, + bool LegalizeResult) { // See if the target wants to custom lower this node. - if (TLI.getOperationAction(N->getOpcode(), N->getValueType(ResNo)) != - TargetLowering::Custom) + if (TLI.getOperationAction(N->getOpcode(), VT) != TargetLowering::Custom) return false; SmallVector Results; - TLI.ReplaceNodeResults(N, Results, DAG); + if (LegalizeResult) + TLI.ReplaceNodeResults(N, Results, DAG); + else + TLI.LowerOperationWrapper(N, Results, DAG); + if (Results.empty()) // The target didn't want to custom lower it after all. return false; @@ -869,46 +902,85 @@ bool DAGTypeLegalizer::CustomLowerResults(SDNode *N, unsigned ResNo) { return true; } +/// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type +/// which is split into two not necessarily identical pieces. +void DAGTypeLegalizer::GetSplitDestVTs(MVT InVT, MVT &LoVT, MVT &HiVT) { + if (!InVT.isVector()) { + LoVT = HiVT = TLI.getTypeToTransformTo(InVT); + } else { + MVT NewEltVT = InVT.getVectorElementType(); + unsigned NumElements = InVT.getVectorNumElements(); + if ((NumElements & (NumElements-1)) == 0) { // Simple power of two vector. + NumElements >>= 1; + LoVT = HiVT = MVT::getVectorVT(NewEltVT, NumElements); + } else { // Non-power-of-two vectors. + unsigned NewNumElts_Lo = 1 << Log2_32(NumElements); + unsigned NewNumElts_Hi = NumElements - NewNumElts_Lo; + LoVT = MVT::getVectorVT(NewEltVT, NewNumElts_Lo); + HiVT = MVT::getVectorVT(NewEltVT, NewNumElts_Hi); + } + } +} + +SDValue DAGTypeLegalizer::GetVectorElementPointer(SDValue VecPtr, MVT EltVT, + SDValue Index) { + DebugLoc dl = Index.getDebugLoc(); + // Make sure the index type is big enough to compute in. + if (Index.getValueType().bitsGT(TLI.getPointerTy())) + Index = DAG.getNode(ISD::TRUNCATE, dl, TLI.getPointerTy(), Index); + else + Index = DAG.getNode(ISD::ZERO_EXTEND, dl, TLI.getPointerTy(), Index); + + // Calculate the element offset and add it to the pointer. + unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size. + + Index = DAG.getNode(ISD::MUL, dl, Index.getValueType(), Index, + DAG.getConstant(EltSize, Index.getValueType())); + return DAG.getNode(ISD::ADD, dl, Index.getValueType(), Index, VecPtr); +} + /// JoinIntegers - Build an integer with low bits Lo and high bits Hi. SDValue DAGTypeLegalizer::JoinIntegers(SDValue Lo, SDValue Hi) { + // Arbitrarily use dlHi for result DebugLoc + DebugLoc dlHi = Hi.getDebugLoc(); + DebugLoc dlLo = Lo.getDebugLoc(); MVT LVT = Lo.getValueType(); MVT HVT = Hi.getValueType(); MVT NVT = MVT::getIntegerVT(LVT.getSizeInBits() + HVT.getSizeInBits()); - Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, Lo); - Hi = DAG.getNode(ISD::ANY_EXTEND, NVT, Hi); - Hi = DAG.getNode(ISD::SHL, NVT, Hi, DAG.getConstant(LVT.getSizeInBits(), - TLI.getShiftAmountTy())); - return DAG.getNode(ISD::OR, NVT, Lo, Hi); + Lo = DAG.getNode(ISD::ZERO_EXTEND, dlLo, NVT, Lo); + Hi = DAG.getNode(ISD::ANY_EXTEND, dlHi, NVT, Hi); + Hi = DAG.getNode(ISD::SHL, dlHi, NVT, Hi, + DAG.getConstant(LVT.getSizeInBits(), TLI.getPointerTy())); + return DAG.getNode(ISD::OR, dlHi, NVT, Lo, Hi); } -/// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT -/// bits in Hi. -void DAGTypeLegalizer::SplitInteger(SDValue Op, - MVT LoVT, MVT HiVT, - SDValue &Lo, SDValue &Hi) { - assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == - Op.getValueType().getSizeInBits() && "Invalid integer splitting!"); - Lo = DAG.getNode(ISD::TRUNCATE, LoVT, Op); - Hi = DAG.getNode(ISD::SRL, Op.getValueType(), Op, - DAG.getConstant(LoVT.getSizeInBits(), - TLI.getShiftAmountTy())); - Hi = DAG.getNode(ISD::TRUNCATE, HiVT, Hi); -} +/// LibCallify - Convert the node into a libcall with the same prototype. +SDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N, + bool isSigned) { + unsigned NumOps = N->getNumOperands(); + DebugLoc dl = N->getDebugLoc(); + if (NumOps == 0) { + return MakeLibCall(LC, N->getValueType(0), 0, 0, isSigned, dl); + } else if (NumOps == 1) { + SDValue Op = N->getOperand(0); + return MakeLibCall(LC, N->getValueType(0), &Op, 1, isSigned, dl); + } else if (NumOps == 2) { + SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) }; + return MakeLibCall(LC, N->getValueType(0), Ops, 2, isSigned, dl); + } + SmallVector Ops(NumOps); + for (unsigned i = 0; i < NumOps; ++i) + Ops[i] = N->getOperand(i); -/// SplitInteger - Return the lower and upper halves of Op's bits in a value -/// type half the size of Op's. -void DAGTypeLegalizer::SplitInteger(SDValue Op, - SDValue &Lo, SDValue &Hi) { - MVT HalfVT = MVT::getIntegerVT(Op.getValueType().getSizeInBits()/2); - SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); + return MakeLibCall(LC, N->getValueType(0), &Ops[0], NumOps, isSigned, dl); } /// MakeLibCall - Generate a libcall taking the given operands as arguments and /// returning a result of type RetVT. SDValue DAGTypeLegalizer::MakeLibCall(RTLIB::Libcall LC, MVT RetVT, const SDValue *Ops, unsigned NumOps, - bool isSigned) { + bool isSigned, DebugLoc dl) { TargetLowering::ArgListTy Args; Args.reserve(NumOps); @@ -926,64 +998,56 @@ SDValue DAGTypeLegalizer::MakeLibCall(RTLIB::Libcall LC, MVT RetVT, const Type *RetTy = RetVT.getTypeForMVT(); std::pair CallInfo = TLI.LowerCallTo(DAG.getEntryNode(), RetTy, isSigned, !isSigned, false, - false, CallingConv::C, false, Callee, Args, DAG); + false, CallingConv::C, false, Callee, Args, DAG, dl); return CallInfo.first; } -/// LibCallify - Convert the node into a libcall with the same prototype. -SDValue DAGTypeLegalizer::LibCallify(RTLIB::Libcall LC, SDNode *N, - bool isSigned) { - unsigned NumOps = N->getNumOperands(); - if (NumOps == 0) { - return MakeLibCall(LC, N->getValueType(0), 0, 0, isSigned); - } else if (NumOps == 1) { - SDValue Op = N->getOperand(0); - return MakeLibCall(LC, N->getValueType(0), &Op, 1, isSigned); - } else if (NumOps == 2) { - SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) }; - return MakeLibCall(LC, N->getValueType(0), Ops, 2, isSigned); +/// PromoteTargetBoolean - Promote the given target boolean to a target boolean +/// of the given type. A target boolean is an integer value, not necessarily of +/// type i1, the bits of which conform to getBooleanContents. +SDValue DAGTypeLegalizer::PromoteTargetBoolean(SDValue Bool, MVT VT) { + DebugLoc dl = Bool.getDebugLoc(); + ISD::NodeType ExtendCode; + switch (TLI.getBooleanContents()) { + default: + assert(false && "Unknown BooleanContent!"); + case TargetLowering::UndefinedBooleanContent: + // Extend to VT by adding rubbish bits. + ExtendCode = ISD::ANY_EXTEND; + break; + case TargetLowering::ZeroOrOneBooleanContent: + // Extend to VT by adding zero bits. + ExtendCode = ISD::ZERO_EXTEND; + break; + case TargetLowering::ZeroOrNegativeOneBooleanContent: { + // Extend to VT by copying the sign bit. + ExtendCode = ISD::SIGN_EXTEND; + break; } - SmallVector Ops(NumOps); - for (unsigned i = 0; i < NumOps; ++i) - Ops[i] = N->getOperand(i); - - return MakeLibCall(LC, N->getValueType(0), &Ops[0], NumOps, isSigned); + } + return DAG.getNode(ExtendCode, dl, VT, Bool); } -SDValue DAGTypeLegalizer::GetVectorElementPointer(SDValue VecPtr, MVT EltVT, - SDValue Index) { - // Make sure the index type is big enough to compute in. - if (Index.getValueType().bitsGT(TLI.getPointerTy())) - Index = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), Index); - else - Index = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), Index); - - // Calculate the element offset and add it to the pointer. - unsigned EltSize = EltVT.getSizeInBits() / 8; // FIXME: should be ABI size. - - Index = DAG.getNode(ISD::MUL, Index.getValueType(), Index, - DAG.getConstant(EltSize, Index.getValueType())); - return DAG.getNode(ISD::ADD, Index.getValueType(), Index, VecPtr); +/// SplitInteger - Return the lower LoVT bits of Op in Lo and the upper HiVT +/// bits in Hi. +void DAGTypeLegalizer::SplitInteger(SDValue Op, + MVT LoVT, MVT HiVT, + SDValue &Lo, SDValue &Hi) { + DebugLoc dl = Op.getDebugLoc(); + assert(LoVT.getSizeInBits() + HiVT.getSizeInBits() == + Op.getValueType().getSizeInBits() && "Invalid integer splitting!"); + Lo = DAG.getNode(ISD::TRUNCATE, dl, LoVT, Op); + Hi = DAG.getNode(ISD::SRL, dl, Op.getValueType(), Op, + DAG.getConstant(LoVT.getSizeInBits(), TLI.getPointerTy())); + Hi = DAG.getNode(ISD::TRUNCATE, dl, HiVT, Hi); } -/// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type -/// which is split into two not necessarily identical pieces. -void DAGTypeLegalizer::GetSplitDestVTs(MVT InVT, MVT &LoVT, MVT &HiVT) { - if (!InVT.isVector()) { - LoVT = HiVT = TLI.getTypeToTransformTo(InVT); - } else { - MVT NewEltVT = InVT.getVectorElementType(); - unsigned NumElements = InVT.getVectorNumElements(); - if ((NumElements & (NumElements-1)) == 0) { // Simple power of two vector. - NumElements >>= 1; - LoVT = HiVT = MVT::getVectorVT(NewEltVT, NumElements); - } else { // Non-power-of-two vectors. - unsigned NewNumElts_Lo = 1 << Log2_32(NumElements); - unsigned NewNumElts_Hi = NumElements - NewNumElts_Lo; - LoVT = MVT::getVectorVT(NewEltVT, NewNumElts_Lo); - HiVT = MVT::getVectorVT(NewEltVT, NewNumElts_Hi); - } - } +/// SplitInteger - Return the lower and upper halves of Op's bits in a value +/// type half the size of Op's. +void DAGTypeLegalizer::SplitInteger(SDValue Op, + SDValue &Lo, SDValue &Hi) { + MVT HalfVT = MVT::getIntegerVT(Op.getValueType().getSizeInBits()/2); + SplitInteger(Op, HalfVT, HalfVT, Lo, Hi); }