// done. Set it to null to avoid confusion.
DAG.setRoot(SDValue());
- // Walk all nodes in the graph, assigning them a NodeID of 'ReadyToProcess'
+ // Walk all nodes in the graph, assigning them a NodeId of 'ReadyToProcess'
// (and remembering them) if they are leaves and assigning 'NewNode' if
// non-leaves.
for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
UI != E; ++UI) {
SDNode *User = *UI;
- int NodeID = User->getNodeId();
- assert(NodeID != ReadyToProcess && NodeID != Processed &&
+ int NodeId = User->getNodeId();
+ assert(NodeId != ReadyToProcess && NodeId != Processed &&
"Invalid node id for user of unprocessed node!");
// This node has two options: it can either be a new node or its Node ID
// may be a count of the number of operands it has that are not ready.
- if (NodeID > 0) {
- User->setNodeId(NodeID-1);
+ if (NodeId > 0) {
+ User->setNodeId(NodeId-1);
// If this was the last use it was waiting on, add it to the ready list.
- if (NodeID-1 == ReadyToProcess)
+ if (NodeId-1 == ReadyToProcess)
Worklist.push_back(User);
continue;
}
// Otherwise, this node is new: this is the first operand of it that
- // became ready. Its new NodeID is the number of operands it has minus 1
+ // became ready. Its new NodeId is the number of operands it has minus 1
// (as this node is now processed).
- assert(NodeID == NewNode && "Unknown node ID!");
+ assert(NodeId == NewNode && "Unknown node ID!");
User->setNodeId(User->getNumOperands()-1);
// If the node only has a single operand, it is now ready.
/// AnalyzeNewNode - The specified node is the root of a subtree of potentially
/// new nodes. Correct any processed operands (this may change the node) and
-/// calculate the NodeId.
-void DAGTypeLegalizer::AnalyzeNewNode(SDValue &Val) {
- SDNode * const N(Val.getNode());
+/// calculate the NodeId. If the node itself changes to a processed node, it
+/// is not remapped - the caller needs to take care of this.
+/// Returns the potentially changed node.
+SDNode *DAGTypeLegalizer::AnalyzeNewNode(SDNode *N) {
// If this was an existing node that is already done, we're done.
if (N->getNodeId() != NewNode)
- return;
+ return N;
// Remove any stale map entries.
ExpungeNode(N);
SDValue Op = OrigOp;
if (Op.getNode()->getNodeId() == Processed)
- RemapNode(Op);
+ RemapValue(Op);
+ else if (Op.getNode()->getNodeId() == NewNode)
+ AnalyzeNewValue(Op);
- if (Op.getNode()->getNodeId() == NewNode)
- AnalyzeNewNode(Op);
- else if (Op.getNode()->getNodeId() == Processed)
+ if (Op.getNode()->getNodeId() == Processed)
++NumProcessed;
if (!NewOps.empty()) {
}
// Some operands changed - update the node.
- if (!NewOps.empty())
- Val.setNode(DAG.UpdateNodeOperands(SDValue(N, 0),
- &NewOps[0],
- NewOps.size()).getNode());
-
- SDNode * const Nu(Val.getNode());
- Nu->setNodeId(Nu->getNumOperands()-NumProcessed);
- if (Nu->getNodeId() == ReadyToProcess)
- Worklist.push_back(Nu);
+ if (!NewOps.empty()) {
+ SDNode *M = DAG.UpdateNodeOperands(SDValue(N, 0), &NewOps[0],
+ NewOps.size()).getNode();
+ if (M != N) {
+ if (M->getNodeId() != NewNode)
+ // It morphed into a previously analyzed node - nothing more to do.
+ return M;
+
+ // It morphed into a different new node. Do the equivalent of passing
+ // it to AnalyzeNewNode: expunge it and calculate the NodeId.
+ N = M;
+ ExpungeNode(N);
+ }
+ }
+
+ // Calculate the NodeId.
+ N->setNodeId(N->getNumOperands()-NumProcessed);
+ if (N->getNodeId() == ReadyToProcess)
+ Worklist.push_back(N);
+
+ return N;
}
+/// AnalyzeNewValue - Call AnalyzeNewNode, updating the node in Val if needed.
+/// If the node changes to a processed node, then remap it.
+void DAGTypeLegalizer::AnalyzeNewValue(SDValue &Val) {
+ SDNode *N(Val.getNode());
+ // If this was an existing node that is already done, avoid remapping it.
+ if (N->getNodeId() != NewNode)
+ return;
+ SDNode *M(AnalyzeNewNode(N));
+ if (M != N)
+ Val.setNode(M);
+ if (M->getNodeId() == Processed)
+ // It morphed into an already processed node - remap it.
+ RemapValue(Val);
+}
+
+
namespace {
/// NodeUpdateListener - This class is a DAGUpdateListener that listens for
/// updates to nodes and recomputes their ready state.
N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
"RAUW deleted processed node!");
// It is possible, though rare, for the deleted node N to occur as a
- // target in a map, so note the replacement N -> E in ReplacedNodes.
+ // target in a map, so note the replacement N -> E in ReplacedValues.
assert(E && "Node not replaced?");
DTL.NoteDeletion(N, E);
}
/// ReplaceValueWith - The specified value was legalized to the specified other
-/// value. If they are different, update the DAG and NodeIDs replacing any uses
+/// value. If they are different, update the DAG and NodeIds replacing any uses
/// of From to use To instead.
void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) {
if (From == To) return;
// If expansion produced new nodes, make sure they are properly marked.
ExpungeNode(From.getNode());
- AnalyzeNewNode(To); // Expunges To.
+ AnalyzeNewValue(To); // Expunges To.
// Anything that used the old node should now use the new one. Note that this
// can potentially cause recursive merging.
// The old node may still be present in a map like ExpandedIntegers or
// PromotedIntegers. Inform maps about the replacement.
- ReplacedNodes[From] = To;
+ ReplacedValues[From] = To;
}
/// ReplaceNodeWith - Replace uses of the 'from' node's results with the 'to'
// If expansion produced new nodes, make sure they are properly marked.
ExpungeNode(From);
- SDValue ToNode(To, 0);
- AnalyzeNewNode(ToNode); // Expunges To.
- To = ToNode.getNode();
+ To = AnalyzeNewNode(To); // Expunges To.
+ // If To morphed into an already processed node, its values may need
+ // remapping. This is done below.
assert(From->getNumValues() == To->getNumValues() &&
"Node results don't match");
// Anything that used the old node should now use the new one. Note that this
// can potentially cause recursive merging.
NodeUpdateListener NUL(*this);
- DAG.ReplaceAllUsesWith(From, To, &NUL);
-
- // The old node may still be present in a map like ExpandedIntegers or
- // PromotedIntegers. Inform maps about the replacement.
for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) {
- assert(From->getValueType(i) == To->getValueType(i) &&
- "Node results don't match");
- ReplacedNodes[SDValue(From, i)] = SDValue(To, i);
+ SDValue FromVal(From, i);
+ SDValue ToVal(To, i);
+
+ // AnalyzeNewNode may have morphed a new node into a processed node. Remap
+ // values now.
+ if (To->getNodeId() == Processed)
+ RemapValue(ToVal);
+
+ assert(FromVal.getValueType() == ToVal.getValueType() &&
+ "Node results don't match!");
+
+ // Make anything that used the old value use the new value.
+ DAG.ReplaceAllUsesOfValueWith(FromVal, ToVal, &NUL);
+
+ // The old node may still be present in a map like ExpandedIntegers or
+ // PromotedIntegers. Inform maps about the replacement.
+ ReplacedValues[FromVal] = ToVal;
}
}
-/// RemapNode - If the specified value was already legalized to another value,
+/// RemapValue - If the specified value was already legalized to another value,
/// replace it by that value.
-void DAGTypeLegalizer::RemapNode(SDValue &N) {
- DenseMap<SDValue, SDValue>::iterator I = ReplacedNodes.find(N);
- if (I != ReplacedNodes.end()) {
+void DAGTypeLegalizer::RemapValue(SDValue &N) {
+ DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.find(N);
+ if (I != ReplacedValues.end()) {
// Use path compression to speed up future lookups if values get multiply
// replaced with other values.
- RemapNode(I->second);
+ RemapValue(I->second);
N = I->second;
}
+ assert(N.getNode()->getNodeId() != NewNode && "Mapped to unanalyzed node!");
}
-/// ExpungeNode - If N has a bogus mapping in ReplacedNodes, eliminate it.
+/// ExpungeNode - If N has a bogus mapping in ReplacedValues, eliminate it.
/// This can occur when a node is deleted then reallocated as a new node -
-/// the mapping in ReplacedNodes applies to the deleted node, not the new
+/// the mapping in ReplacedValues applies to the deleted node, not the new
/// one.
-/// The only map that can have a deleted node as a source is ReplacedNodes.
+/// The only map that can have a deleted node as a source is ReplacedValues.
/// Other maps can have deleted nodes as targets, but since their looked-up
-/// values are always immediately remapped using RemapNode, resulting in a
-/// not-deleted node, this is harmless as long as ReplacedNodes/RemapNode
+/// values are always immediately remapped using RemapValue, resulting in a
+/// not-deleted node, this is harmless as long as ReplacedValues/RemapValue
/// always performs correct mappings. In order to keep the mapping correct,
/// ExpungeNode should be called on any new nodes *before* adding them as
-/// either source or target to ReplacedNodes (which typically means calling
+/// either source or target to ReplacedValues (which typically means calling
/// Expunge when a new node is first seen, since it may no longer be marked
-/// NewNode by the time it is added to ReplacedNodes).
+/// NewNode by the time it is added to ReplacedValues).
void DAGTypeLegalizer::ExpungeNode(SDNode *N) {
if (N->getNodeId() != NewNode)
return;
- // If N is not remapped by ReplacedNodes then there is nothing to do.
+ // If N is not remapped by ReplacedValues then there is nothing to do.
unsigned i, e;
for (i = 0, e = N->getNumValues(); i != e; ++i)
- if (ReplacedNodes.find(SDValue(N, i)) != ReplacedNodes.end())
+ if (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end())
break;
if (i == e)
for (DenseMap<SDValue, SDValue>::iterator I = PromotedIntegers.begin(),
E = PromotedIntegers.end(); I != E; ++I) {
assert(I->first.getNode() != N);
- RemapNode(I->second);
+ RemapValue(I->second);
}
for (DenseMap<SDValue, SDValue>::iterator I = SoftenedFloats.begin(),
E = SoftenedFloats.end(); I != E; ++I) {
assert(I->first.getNode() != N);
- RemapNode(I->second);
+ RemapValue(I->second);
}
for (DenseMap<SDValue, SDValue>::iterator I = ScalarizedVectors.begin(),
E = ScalarizedVectors.end(); I != E; ++I) {
assert(I->first.getNode() != N);
- RemapNode(I->second);
+ 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);
- RemapNode(I->second.first);
- RemapNode(I->second.second);
+ RemapValue(I->second.first);
+ RemapValue(I->second.second);
}
for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) {
assert(I->first.getNode() != N);
- RemapNode(I->second.first);
- RemapNode(I->second.second);
+ RemapValue(I->second.first);
+ RemapValue(I->second.second);
}
for (DenseMap<SDValue, std::pair<SDValue, SDValue> >::iterator
I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) {
assert(I->first.getNode() != N);
- RemapNode(I->second.first);
- RemapNode(I->second.second);
+ RemapValue(I->second.first);
+ RemapValue(I->second.second);
}
- for (DenseMap<SDValue, SDValue>::iterator I = ReplacedNodes.begin(),
- E = ReplacedNodes.end(); I != E; ++I)
- RemapNode(I->second);
+ for (DenseMap<SDValue, SDValue>::iterator I = ReplacedValues.begin(),
+ E = ReplacedValues.end(); I != E; ++I)
+ RemapValue(I->second);
for (unsigned i = 0, e = N->getNumValues(); i != e; ++i)
- ReplacedNodes.erase(SDValue(N, i));
+ ReplacedValues.erase(SDValue(N, i));
}
void DAGTypeLegalizer::SetPromotedInteger(SDValue Op, SDValue Result) {
- AnalyzeNewNode(Result);
+ AnalyzeNewValue(Result);
SDValue &OpEntry = PromotedIntegers[Op];
assert(OpEntry.getNode() == 0 && "Node is already promoted!");
}
void DAGTypeLegalizer::SetSoftenedFloat(SDValue Op, SDValue Result) {
- AnalyzeNewNode(Result);
+ AnalyzeNewValue(Result);
SDValue &OpEntry = SoftenedFloats[Op];
assert(OpEntry.getNode() == 0 && "Node is already converted to integer!");
}
void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) {
- AnalyzeNewNode(Result);
+ AnalyzeNewValue(Result);
SDValue &OpEntry = ScalarizedVectors[Op];
assert(OpEntry.getNode() == 0 && "Node is already scalarized!");
void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo,
SDValue &Hi) {
std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
- RemapNode(Entry.first);
- RemapNode(Entry.second);
+ RemapValue(Entry.first);
+ RemapValue(Entry.second);
assert(Entry.first.getNode() && "Operand isn't expanded");
Lo = Entry.first;
Hi = Entry.second;
void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo,
SDValue Hi) {
// Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
- AnalyzeNewNode(Lo);
- AnalyzeNewNode(Hi);
+ AnalyzeNewValue(Lo);
+ AnalyzeNewValue(Hi);
// Remember that this is the result of the node.
std::pair<SDValue, SDValue> &Entry = ExpandedIntegers[Op];
void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo,
SDValue &Hi) {
std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
- RemapNode(Entry.first);
- RemapNode(Entry.second);
+ RemapValue(Entry.first);
+ RemapValue(Entry.second);
assert(Entry.first.getNode() && "Operand isn't expanded");
Lo = Entry.first;
Hi = Entry.second;
void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo,
SDValue Hi) {
// Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
- AnalyzeNewNode(Lo);
- AnalyzeNewNode(Hi);
+ AnalyzeNewValue(Lo);
+ AnalyzeNewValue(Hi);
// Remember that this is the result of the node.
std::pair<SDValue, SDValue> &Entry = ExpandedFloats[Op];
void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo,
SDValue &Hi) {
std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
- RemapNode(Entry.first);
- RemapNode(Entry.second);
+ RemapValue(Entry.first);
+ RemapValue(Entry.second);
assert(Entry.first.getNode() && "Operand isn't split");
Lo = Entry.first;
Hi = Entry.second;
void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo,
SDValue Hi) {
// Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
- AnalyzeNewNode(Lo);
- AnalyzeNewNode(Hi);
+ AnalyzeNewValue(Lo);
+ AnalyzeNewValue(Hi);
// Remember that this is the result of the node.
std::pair<SDValue, SDValue> &Entry = SplitVectors[Op];
Hi = DAG.getNode(ISD::TRUNCATE, HiVT, Hi);
}
-/// SplitInteger - Return the lower and upper halves of Op's bits in a value type
-/// half the size of Op's.
+/// 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);
Args.push_back(Entry);
}
SDValue Callee = DAG.getExternalSymbol(TLI.getLibcallName(LC),
- TLI.getPointerTy());
+ TLI.getPointerTy());
const Type *RetTy = RetVT.getTypeForMVT();
std::pair<SDValue,SDValue> CallInfo =
TLI.LowerCallTo(DAG.getEntryNode(), RetTy, isSigned, !isSigned, false,
- CallingConv::C, false, Callee, Args, DAG);
+ false, CallingConv::C, false, Callee, Args, DAG);
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);
+ }
+ 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);
+}
+
SDValue DAGTypeLegalizer::GetVectorElementPointer(SDValue VecPtr, MVT EltVT,
SDValue Index) {
// Make sure the index type is big enough to compute in.
projects / oota-llvm.git / blobdiff