#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;
// 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!");
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) {
RemapValue(I->second);
}
+ for (DenseMap<SDValue, SDValue>::iterator I = WidenedVectors.begin(),
+ E = WidenedVectors.end(); I != E; ++I) {
+ assert(I->first.getNode() != N);
+ RemapValue(I->second);
+ }
+
for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
I = ExpandedIntegers.begin(), E = ExpandedIntegers.end(); I != E; ++I){
assert(I->first.getNode() != N);
class VISIBILITY_HIDDEN NodeUpdateListener :
public SelectionDAG::DAGUpdateListener {
DAGTypeLegalizer &DTL;
- SmallVectorImpl<SDNode*> &NodesToAnalyze;
- SmallPtrSet<SDNode*, 16> &NodesDeleted;
+ SmallSetVector<SDNode*, 16> &NodesToAnalyze;
public:
explicit NodeUpdateListener(DAGTypeLegalizer &dtl,
- SmallVectorImpl<SDNode*> &nta,
- SmallPtrSet<SDNode*, 16> &nd)
- : DTL(dtl), NodesToAnalyze(nta), NodesDeleted(nd) {}
+ SmallSetVector<SDNode*, 16> &nta)
+ : DTL(dtl), NodesToAnalyze(nta) {}
virtual void NodeDeleted(SDNode *N, SDNode *E) {
assert(N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
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) {
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<SDNode*, 16> NodesToAnalyze;
- SmallPtrSet<SDNode*, 16> NodesDeleted;
- NodeUpdateListener NUL(*this, NodesToAnalyze, NodesDeleted);
+ SmallSetVector<SDNode*, 16> 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
}
}
+/// 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);
AnalyzeNewValue(Result);
SDValue &OpEntry = WidenedVectors[Op];
- assert(OpEntry.getNode() == 0 && "Node is already promoted!");
+ assert(OpEntry.getNode() == 0 && "Node already widened!");
OpEntry = Result;
}
/// 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<SDValue, 8> 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;
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<SDValue, 8> 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);
const Type *RetTy = RetVT.getTypeForMVT();
std::pair<SDValue,SDValue> 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<SDValue, 8> 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);
}
projects / oota-llvm.git / blobdiff