[DAG] Don't map a TableId to itself in the ReplacedValues map

[bjope]

Summary

Found some regressions (infinite loop in DAGTypeLegalizer::RemapId)
after r334880. This patch makes sure that we do map a TableId to
itself.

[bjope]

lib/CodeGen/SelectionDAG/LegalizeTypes.cpp

578

Maybe an alternative solution could be to allow mapping of a value to itself in ReplacedValues, and then we could simply return Id here when Id==I->second.

658

I think we still need to do this replacement even if FromId == ToId, since From.getNode() != To.getNode(), right?

[niravd]

LGTM. Thanks!

lib/CodeGen/SelectionDAG/LegalizeTypes.cpp

658

Yes.

lib/CodeGen/SelectionDAG/LegalizeTypes.h

public:
   /// "true" if it made any changes.
   bool run();
 
   void NoteDeletion(SDNode *Old, SDNode *New) {
     for (unsigned i = 0, e = Old->getNumValues(); i != e; ++i) {
       TableId NewId = getTableId(SDValue(New, i));
       TableId OldId = getTableId(SDValue(Old, i));
 
+      if (OldId != NewId)
         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);

lib/CodeGen/SelectionDAG/LegalizeTypes.cpp

 void DAGTypeLegalizer::RemapValue(SDValue &V) {
   auto Id = getTableId(V);
   V = getSDValue(Id);
 }
 
 void DAGTypeLegalizer::RemapId(TableId &Id) {
   auto I = ReplacedValues.find(Id);
   if (I != ReplacedValues.end()) {
+    assert(Id != I->second && "Id is mapped to itself.");
     // Use path compression to speed up future lookups if values get multiply
     // replaced with other values.
     RemapId(I->second);
     Id = I->second;
 
     // 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.
void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) {
   NodeUpdateListener NUL(*this, NodesToAnalyze);
   do {
 
     // 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);
 
+    if (FromId != ToId)
       ReplacedValues[FromId] = ToId;
     DAG.ReplaceAllUsesOfValueWith(From, To);
 
     // Process the list of nodes that need to be reanalyzed.
     while (!NodesToAnalyze.empty()) {
       SDNode *N = NodesToAnalyze.back();
       NodesToAnalyze.pop_back();
       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
while (!NodesToAnalyze.empty()) {
             RemapValue(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.
           auto OldValId = getTableId(OldVal);
           auto NewValId = getTableId(NewVal);
           DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal);
+          if (OldValId != NewValId)
             ReplacedValues[OldValId] = NewValId;
         }
         // The original node continues to exist in the DAG, marked NewNode.
       }
     }
     // When recursively update nodes with new nodes, it is possible to have
     // new uses of From due to CSE. If this happens, replace the new uses of
     // From with To.
   } while (!From.use_empty());

test/CodeGen/X86/legalize-types-remapid.ll

+; RUN: llc -mtriple=i386 -mcpu=generic -O0 -o /dev/null %s
+
+@c = global i32 0
+@d = global <2 x i64> zeroinitializer
+
+define void @test() {
+bb1:
+  %t0 = load <2 x i64>, <2 x i64>* @d
+  %t0.i0 = extractelement <2 x i64> %t0, i32 0
+  %t0.i0.cast = bitcast i64 %t0.i0 to <2 x i32>
+  %t0.i0.cast.i0 = extractelement <2 x i32> %t0.i0.cast, i32 0
+  store volatile i32 %t0.i0.cast.i0, i32* @c
+  %t0.i0.cast.i1 = extractelement <2 x i32> %t0.i0.cast, i32 1
+  store volatile i32 %t0.i0.cast.i1, i32* @c
+  ret void
+}