Index: llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h =================================================================== --- llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h +++ llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h @@ -93,46 +93,81 @@ N->getOpcode() == ISD::Register; } + // Bijection from SDValue to unique id. As each created node gets a + // new id we do not need to worry about reuse expunging. Should we + // run out of ids, we can do a one time expensive compactifcation. + typedef unsigned TableId; + + TableId NextValueId = 1; + + SmallDenseMap ValueToIdMap; + SmallDenseMap IdToValueMap; + /// For integer nodes that are below legal width, this map indicates what /// promoted value to use. - SmallDenseMap PromotedIntegers; + SmallDenseMap PromotedIntegers; /// For integer nodes that need to be expanded this map indicates which /// operands are the expanded version of the input. - SmallDenseMap, 8> ExpandedIntegers; + SmallDenseMap, 8> ExpandedIntegers; /// For floating-point nodes converted to integers of the same size, this map /// indicates the converted value to use. - SmallDenseMap SoftenedFloats; + SmallDenseMap SoftenedFloats; /// For floating-point nodes that have a smaller precision than the smallest /// supported precision, this map indicates what promoted value to use. - SmallDenseMap PromotedFloats; + SmallDenseMap PromotedFloats; /// For float nodes that need to be expanded this map indicates which operands /// are the expanded version of the input. - SmallDenseMap, 8> ExpandedFloats; + SmallDenseMap, 8> ExpandedFloats; /// For nodes that are <1 x ty>, this map indicates the scalar value of type /// 'ty' to use. - SmallDenseMap ScalarizedVectors; + SmallDenseMap ScalarizedVectors; /// For nodes that need to be split this map indicates which operands are the /// expanded version of the input. - SmallDenseMap, 8> SplitVectors; + SmallDenseMap, 8> SplitVectors; /// For vector nodes that need to be widened, indicates the widened value to /// use. - SmallDenseMap WidenedVectors; + SmallDenseMap WidenedVectors; /// For values that have been replaced with another, indicates the replacement /// value to use. - SmallDenseMap ReplacedValues; + SmallDenseMap ReplacedValues; /// This defines a worklist of nodes to process. In order to be pushed onto /// this worklist, all operands of a node must have already been processed. SmallVector Worklist; + TableId getTableId(SDValue V) { + assert(V.getNode() && "Getting TableId on SDValue()"); + + auto I = ValueToIdMap.find(V); + if (I != ValueToIdMap.end()) { + // replace if there's been a shift. + RemapId(I->second); + assert(I->second && "All Ids should be nonzero"); + return I->second; + } + // Add if it's not there. + ValueToIdMap.insert(std::make_pair(V, NextValueId)); + IdToValueMap.insert(std::make_pair(NextValueId, V)); + ++NextValueId; + assert(NextValueId != 0 && + "Ran out of Ids. Increase id type size or add compactification"); + return NextValueId - 1; + } + + const SDValue &getSDValue(TableId &Id) { + RemapId(Id); + assert(Id && "TableId should be non-zero"); + return IdToValueMap[Id]; + } + public: explicit DAGTypeLegalizer(SelectionDAG &dag) : TLI(dag.getTargetLoweringInfo()), DAG(dag), @@ -147,10 +182,24 @@ bool run(); void NoteDeletion(SDNode *Old, SDNode *New) { - ExpungeNode(Old); - ExpungeNode(New); - for (unsigned i = 0, e = Old->getNumValues(); i != e; ++i) - ReplacedValues[SDValue(Old, i)] = SDValue(New, i); + for (unsigned i = 0, e = Old->getNumValues(); i != e; ++i) { + auto NewId = getTableId(SDValue(New, i)); + auto OldId = getTableId(SDValue(Old, i)); + + ReplacedValues[OldId] = NewId; + + // Delete Node from tables. + ValueToIdMap.erase(SDValue(Old, i)); + IdToValueMap.erase(OldId); + PromotedIntegers.erase(OldId); + ExpandedIntegers.erase(OldId); + SoftenedFloats.erase(OldId); + PromotedFloats.erase(OldId); + ExpandedFloats.erase(OldId); + ScalarizedVectors.erase(OldId); + SplitVectors.erase(OldId); + WidenedVectors.erase(OldId); + } } SelectionDAG &getDAG() const { return DAG; } @@ -158,9 +207,9 @@ private: SDNode *AnalyzeNewNode(SDNode *N); void AnalyzeNewValue(SDValue &Val); - void ExpungeNode(SDNode *N); void PerformExpensiveChecks(); - void RemapValue(SDValue &N); + void RemapId(TableId &N); + void RemapValue(SDValue &V); // Common routines. SDValue BitConvertToInteger(SDValue Op); @@ -207,8 +256,8 @@ /// returns an i32, the lower 16 bits of which coincide with Op, and the upper /// 16 bits of which contain rubbish. SDValue GetPromotedInteger(SDValue Op) { - SDValue &PromotedOp = PromotedIntegers[Op]; - RemapValue(PromotedOp); + auto &PromotedId = PromotedIntegers[getTableId(Op)]; + auto PromotedOp = getSDValue(PromotedId); assert(PromotedOp.getNode() && "Operand wasn't promoted?"); return PromotedOp; } @@ -402,16 +451,15 @@ /// stay in a register, the Op is not converted to an integer. /// In that case, the given op is returned. SDValue GetSoftenedFloat(SDValue Op) { - auto Iter = SoftenedFloats.find(Op); + auto Id = getTableId(Op); + auto Iter = SoftenedFloats.find(Id); if (Iter == SoftenedFloats.end()) { assert(isSimpleLegalType(Op.getValueType()) && "Operand wasn't converted to integer?"); return Op; } - - SDValue &SoftenedOp = Iter->second; + SDValue SoftenedOp = getSDValue(Iter->second); assert(SoftenedOp.getNode() && "Unconverted op in SoftenedFloats?"); - RemapValue(SoftenedOp); return SoftenedOp; } void SetSoftenedFloat(SDValue Op, SDValue Result); @@ -548,8 +596,8 @@ //===--------------------------------------------------------------------===// SDValue GetPromotedFloat(SDValue Op) { - SDValue &PromotedOp = PromotedFloats[Op]; - RemapValue(PromotedOp); + auto PromotedId = PromotedFloats[getTableId(Op)]; + SDValue PromotedOp = getSDValue(PromotedId); assert(PromotedOp.getNode() && "Operand wasn't promoted?"); return PromotedOp; } @@ -588,8 +636,8 @@ /// element type, this returns the element. For example, if Op is a v1i32, /// Op = < i32 val >, this method returns val, an i32. SDValue GetScalarizedVector(SDValue Op) { - SDValue &ScalarizedOp = ScalarizedVectors[Op]; - RemapValue(ScalarizedOp); + auto &ScalarizedId = ScalarizedVectors[getTableId(Op)]; + SDValue ScalarizedOp = getSDValue(ScalarizedId); assert(ScalarizedOp.getNode() && "Operand wasn't scalarized?"); return ScalarizedOp; } @@ -700,8 +748,8 @@ /// method returns a v4i32 for which the first two elements are the same as /// those of Op, while the last two elements contain rubbish. SDValue GetWidenedVector(SDValue Op) { - SDValue &WidenedOp = WidenedVectors[Op]; - RemapValue(WidenedOp); + auto &WidenedId = WidenedVectors[getTableId(Op)]; + SDValue WidenedOp = getSDValue(WidenedId); assert(WidenedOp.getNode() && "Operand wasn't widened?"); return WidenedOp; } Index: llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp =================================================================== --- llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp +++ llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp @@ -84,9 +84,10 @@ SDValue Res(&Node, i); EVT VT = Res.getValueType(); bool Failed = false; + auto ResId = getTableId(Res); unsigned Mapped = 0; - if (ReplacedValues.find(Res) != ReplacedValues.end()) { + if (ReplacedValues.find(ResId) != ReplacedValues.end()) { Mapped |= 1; // Check that remapped values are only used by nodes marked NewNode. for (SDNode::use_iterator UI = Node.use_begin(), UE = Node.use_end(); @@ -97,30 +98,31 @@ // Check that the final result of applying ReplacedValues is not // marked NewNode. - SDValue NewVal = ReplacedValues[Res]; - DenseMap::iterator I = ReplacedValues.find(NewVal); + auto NewValId = ReplacedValues[ResId]; + DenseMap::iterator I = ReplacedValues.find(NewValId); while (I != ReplacedValues.end()) { - NewVal = I->second; - I = ReplacedValues.find(NewVal); + NewValId = I->second; + I = ReplacedValues.find(NewValId); } + SDValue NewVal = getSDValue(NewValId); assert(NewVal.getNode()->getNodeId() != NewNode && "ReplacedValues maps to a new node!"); } - if (PromotedIntegers.find(Res) != PromotedIntegers.end()) + if (PromotedIntegers.find(ResId) != PromotedIntegers.end()) Mapped |= 2; - if (SoftenedFloats.find(Res) != SoftenedFloats.end()) + if (SoftenedFloats.find(ResId) != SoftenedFloats.end()) Mapped |= 4; - if (ScalarizedVectors.find(Res) != ScalarizedVectors.end()) + if (ScalarizedVectors.find(ResId) != ScalarizedVectors.end()) Mapped |= 8; - if (ExpandedIntegers.find(Res) != ExpandedIntegers.end()) + if (ExpandedIntegers.find(ResId) != ExpandedIntegers.end()) Mapped |= 16; - if (ExpandedFloats.find(Res) != ExpandedFloats.end()) + if (ExpandedFloats.find(ResId) != ExpandedFloats.end()) Mapped |= 32; - if (SplitVectors.find(Res) != SplitVectors.end()) + if (SplitVectors.find(ResId) != SplitVectors.end()) Mapped |= 64; - if (WidenedVectors.find(Res) != WidenedVectors.end()) + if (WidenedVectors.find(ResId) != WidenedVectors.end()) Mapped |= 128; - if (PromotedFloats.find(Res) != PromotedFloats.end()) + if (PromotedFloats.find(ResId) != PromotedFloats.end()) Mapped |= 256; if (Node.getNodeId() != Processed) { @@ -491,9 +493,6 @@ if (N->getNodeId() != NewNode && N->getNodeId() != Unanalyzed) return N; - // Remove any stale map entries. - ExpungeNode(N); - // Okay, we know that this node is new. Recursively walk all of its operands // to see if they are new also. The depth of this walk is bounded by the size // of the new tree that was constructed (usually 2-3 nodes), so we don't worry @@ -544,7 +543,6 @@ // to remap the operands, since they are the same as the operands we // remapped above. N = M; - ExpungeNode(N); } } @@ -565,106 +563,24 @@ RemapValue(Val); } -/// 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 ReplacedValues applies to the deleted node, not the new -/// one. -/// 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 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 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 ReplacedValues). -void DAGTypeLegalizer::ExpungeNode(SDNode *N) { - if (N->getNodeId() != NewNode) - return; - - // 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 (ReplacedValues.find(SDValue(N, i)) != ReplacedValues.end()) - break; - - if (i == e) - return; - - // Remove N from all maps - this is expensive but rare. - - for (DenseMap::iterator I = PromotedIntegers.begin(), - E = PromotedIntegers.end(); I != E; ++I) { - assert(I->first.getNode() != N); - RemapValue(I->second); - } - - for (DenseMap::iterator I = PromotedFloats.begin(), - E = PromotedFloats.end(); I != E; ++I) { - assert(I->first.getNode() != N); - RemapValue(I->second); - } - - for (DenseMap::iterator I = SoftenedFloats.begin(), - E = SoftenedFloats.end(); I != E; ++I) { - assert(I->first.getNode() != N); - RemapValue(I->second); - } - - for (DenseMap::iterator I = ScalarizedVectors.begin(), - E = ScalarizedVectors.end(); I != E; ++I) { - assert(I->first.getNode() != 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); - RemapValue(I->second.first); - RemapValue(I->second.second); - } - - for (DenseMap >::iterator - I = ExpandedFloats.begin(), E = ExpandedFloats.end(); I != E; ++I) { - assert(I->first.getNode() != N); - RemapValue(I->second.first); - RemapValue(I->second.second); - } - - for (DenseMap >::iterator - I = SplitVectors.begin(), E = SplitVectors.end(); I != E; ++I) { - assert(I->first.getNode() != N); - RemapValue(I->second.first); - RemapValue(I->second.second); - } - - for (DenseMap::iterator I = ReplacedValues.begin(), - E = ReplacedValues.end(); I != E; ++I) - RemapValue(I->second); - - for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) - ReplacedValues.erase(SDValue(N, i)); -} - /// If the specified value was already legalized to another value, /// replace it by that value. -void DAGTypeLegalizer::RemapValue(SDValue &N) { - DenseMap::iterator I = ReplacedValues.find(N); +void DAGTypeLegalizer::RemapValue(SDValue &V) { + auto Id = getTableId(V); + V = getSDValue(Id); +} + +void DAGTypeLegalizer::RemapId(TableId &Id) { + DenseMap::iterator I = ReplacedValues.find(Id); if (I != ReplacedValues.end()) { // Use path compression to speed up future lookups if values get multiply // replaced with other values. - RemapValue(I->second); - N = I->second; + RemapId(I->second); + Id = I->second; - // Note that it is possible to have N.getNode()->getNodeId() == NewNode at - // this point because it is possible for a node to be put in the map before - // being processed. + // Note that N = IdToValueMap[Id] it is possible to have + // N.getNode()->getNodeId() == NewNode at this point because it is possible + // for a node to be put in the map before being processed. } } @@ -721,19 +637,21 @@ 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. + AnalyzeNewValue(To); // Anything that used the old node should now use the new one. Note that this // can potentially cause recursive merging. SmallSetVector NodesToAnalyze; NodeUpdateListener NUL(*this, NodesToAnalyze); do { - DAG.ReplaceAllUsesOfValueWith(From, To); - // The old node may still be present in a map like ExpandedIntegers or - // PromotedIntegers. Inform maps about the replacement. - ReplacedValues[From] = To; + // The old node may be present in a map like ExpandedIntegers or + // PromotedIntegers. Inform maps about the replacement. + auto FromId = getTableId(From); + auto ToId = getTableId(To); + + ReplacedValues[FromId] = ToId; + DAG.ReplaceAllUsesOfValueWith(From, To); // Process the list of nodes that need to be reanalyzed. while (!NodesToAnalyze.empty()) { @@ -758,12 +676,14 @@ SDValue NewVal(M, i); if (M->getNodeId() == Processed) RemapValue(NewVal); - DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal); // OldVal may be a target of the ReplacedValues map which was marked // NewNode to force reanalysis because it was updated. Ensure that // anything that ReplacedValues mapped to OldVal will now be mapped // all the way to NewVal. - ReplacedValues[OldVal] = NewVal; + auto OldValId = getTableId(OldVal); + auto NewValId = getTableId(NewVal); + DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal); + ReplacedValues[OldValId] = NewValId; } // The original node continues to exist in the DAG, marked NewNode. } @@ -780,9 +700,9 @@ "Invalid type for promoted integer"); AnalyzeNewValue(Result); - SDValue &OpEntry = PromotedIntegers[Op]; - assert(!OpEntry.getNode() && "Node is already promoted!"); - OpEntry = Result; + auto &OpIdEntry = PromotedIntegers[getTableId(Op)]; + assert((OpIdEntry == 0) && "Node is already promoted!"); + OpIdEntry = getTableId(Result); DAG.transferDbgValues(Op, Result); } @@ -797,15 +717,15 @@ "Invalid type for softened float"); AnalyzeNewValue(Result); - SDValue &OpEntry = SoftenedFloats[Op]; + auto &OpIdEntry = SoftenedFloats[getTableId(Op)]; // Allow repeated calls to save f128 type nodes // or any node with type that transforms to itself. // Many operations on these types are not softened. - assert((!OpEntry.getNode()|| + assert(((OpIdEntry == 0) || Op.getValueType() == - TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType())) && + TLI.getTypeToTransformTo(*DAG.getContext(), Op.getValueType())) && "Node is already converted to integer!"); - OpEntry = Result; + OpIdEntry = getTableId(Result); } void DAGTypeLegalizer::SetPromotedFloat(SDValue Op, SDValue Result) { @@ -814,9 +734,9 @@ "Invalid type for promoted float"); AnalyzeNewValue(Result); - SDValue &OpEntry = PromotedFloats[Op]; - assert(!OpEntry.getNode() && "Node is already promoted!"); - OpEntry = Result; + auto &OpIdEntry = PromotedFloats[getTableId(Op)]; + assert((OpIdEntry == 0) && "Node is already promoted!"); + OpIdEntry = getTableId(Result); } void DAGTypeLegalizer::SetScalarizedVector(SDValue Op, SDValue Result) { @@ -827,19 +747,17 @@ "Invalid type for scalarized vector"); AnalyzeNewValue(Result); - SDValue &OpEntry = ScalarizedVectors[Op]; - assert(!OpEntry.getNode() && "Node is already scalarized!"); - OpEntry = Result; + auto &OpIdEntry = ScalarizedVectors[getTableId(Op)]; + assert((OpIdEntry == 0) && "Node is already scalarized!"); + OpIdEntry = getTableId(Result); } void DAGTypeLegalizer::GetExpandedInteger(SDValue Op, SDValue &Lo, SDValue &Hi) { - std::pair &Entry = ExpandedIntegers[Op]; - RemapValue(Entry.first); - RemapValue(Entry.second); - assert(Entry.first.getNode() && "Operand isn't expanded"); - Lo = Entry.first; - Hi = Entry.second; + std::pair &Entry = ExpandedIntegers[getTableId(Op)]; + assert((Entry.first != 0) && "Operand isn't expanded"); + Lo = getSDValue(Entry.first); + Hi = getSDValue(Entry.second); } void DAGTypeLegalizer::SetExpandedInteger(SDValue Op, SDValue Lo, @@ -865,20 +783,18 @@ } // Remember that this is the result of the node. - std::pair &Entry = ExpandedIntegers[Op]; - assert(!Entry.first.getNode() && "Node already expanded"); - Entry.first = Lo; - Entry.second = Hi; + std::pair &Entry = ExpandedIntegers[getTableId(Op)]; + assert((Entry.first == 0) && "Node already expanded"); + Entry.first = getTableId(Lo); + Entry.second = getTableId(Hi); } void DAGTypeLegalizer::GetExpandedFloat(SDValue Op, SDValue &Lo, SDValue &Hi) { - std::pair &Entry = ExpandedFloats[Op]; - RemapValue(Entry.first); - RemapValue(Entry.second); - assert(Entry.first.getNode() && "Operand isn't expanded"); - Lo = Entry.first; - Hi = Entry.second; + std::pair &Entry = ExpandedFloats[getTableId(Op)]; + assert((Entry.first != 0) && "Operand isn't expanded"); + Lo = getSDValue(Entry.first); + Hi = getSDValue(Entry.second); } void DAGTypeLegalizer::SetExpandedFloat(SDValue Op, SDValue Lo, @@ -891,21 +807,19 @@ AnalyzeNewValue(Lo); AnalyzeNewValue(Hi); - // Remember that this is the result of the node. - std::pair &Entry = ExpandedFloats[Op]; - assert(!Entry.first.getNode() && "Node already expanded"); - Entry.first = Lo; - Entry.second = Hi; + std::pair &Entry = ExpandedFloats[getTableId(Op)]; + assert((Entry.first == 0) && "Node already expanded"); + Entry.first = getTableId(Lo); + Entry.second = getTableId(Hi); } void DAGTypeLegalizer::GetSplitVector(SDValue Op, SDValue &Lo, SDValue &Hi) { - std::pair &Entry = SplitVectors[Op]; - RemapValue(Entry.first); - RemapValue(Entry.second); - assert(Entry.first.getNode() && "Operand isn't split"); - Lo = Entry.first; - Hi = Entry.second; + std::pair &Entry = SplitVectors[getTableId(Op)]; + Lo = getSDValue(Entry.first); + Hi = getSDValue(Entry.second); + assert(Lo.getNode() && "Operand isn't split"); + ; } void DAGTypeLegalizer::SetSplitVector(SDValue Op, SDValue Lo, @@ -921,10 +835,10 @@ AnalyzeNewValue(Hi); // Remember that this is the result of the node. - std::pair &Entry = SplitVectors[Op]; - assert(!Entry.first.getNode() && "Node already split"); - Entry.first = Lo; - Entry.second = Hi; + std::pair &Entry = SplitVectors[getTableId(Op)]; + assert((Entry.first == 0) && "Node already split"); + Entry.first = getTableId(Lo); + Entry.second = getTableId(Hi); } void DAGTypeLegalizer::SetWidenedVector(SDValue Op, SDValue Result) { @@ -933,9 +847,9 @@ "Invalid type for widened vector"); AnalyzeNewValue(Result); - SDValue &OpEntry = WidenedVectors[Op]; - assert(!OpEntry.getNode() && "Node already widened!"); - OpEntry = Result; + auto &OpIdEntry = WidenedVectors[getTableId(Op)]; + assert((OpIdEntry == 0) && "Node already widened!"); + OpIdEntry = getTableId(Result); }