Sometimes (rarely) nodes held in LegalizeTypes

maps can be deleted.  This happens when RAUW
replaces a node N with another equivalent node
E, deleting the first node.  Solve this by
adding (N, E) to ReplacedNodes, which is already
used to remap nodes to replacements.  This means
that deleted nodes are being allowed in maps,
which can be delicate: the memory may be reused
for a new node which might get confused with the
old deleted node pointer hanging around in the
maps, so detect this and flush out maps if it
occurs (ExpungeNode).  The expunging operation
is expensive, however it never occurs during
a llvm-gcc bootstrap or anywhere in the nightly
testsuite.  It occurs three times in "make check":
Alpha/illegal-element-type.ll,
PowerPC/illegal-element-type.ll and
X86/mmx-shift.ll.  If expunging proves to be too
expensive then there are other more complicated
ways of solving the problem.
In the normal case this patch adds the overhead
of a few more map lookups, which is hopefully
negligable.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52214 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 86 insertions, 57 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
index 61d0e45162..16c86936a6 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
@@ -268,51 +268,6 @@ void DAGTypeLegalizer::AnalyzeNewNode(SDNode *&N) {
     Worklist.push_back(N);
 }
 
-void DAGTypeLegalizer::SanityCheck(SDNode *N) {
-  for (SmallVector<SDNode*, 128>::iterator I = Worklist.begin(),
-       E = Worklist.end(); I != E; ++I)
-    assert(*I != N);
-
-  for (DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.begin(),
-       E = ReplacedNodes.end(); I != E; ++I) {
-    assert(I->first.Val != N);
-    assert(I->second.Val != N);
-  }
-
-  for (DenseMap<SDOperand, SDOperand>::iterator I = PromotedNodes.begin(),
-       E = PromotedNodes.end(); I != E; ++I) {
-    assert(I->first.Val != N);
-    assert(I->second.Val != N);
-  }
-
-  for (DenseMap<SDOperand, SDOperand>::iterator
-       I = FloatToIntedNodes.begin(),
-       E = FloatToIntedNodes.end(); I != E; ++I) {
-    assert(I->first.Val != N);
-    assert(I->second.Val != N);
-  }
-
-  for (DenseMap<SDOperand, SDOperand>::iterator I = ScalarizedNodes.begin(),
-       E = ScalarizedNodes.end(); I != E; ++I) {
-    assert(I->first.Val != N);
-    assert(I->second.Val != N);
-  }
-
-  for (DenseMap<SDOperand, std::pair<SDOperand, SDOperand> >::iterator
-       I = ExpandedNodes.begin(), E = ExpandedNodes.end(); I != E; ++I) {
-    assert(I->first.Val != N);
-    assert(I->second.first.Val != N);
-    assert(I->second.second.Val != N);
-  }
-
-  for (DenseMap<SDOperand, std::pair<SDOperand, SDOperand> >::iterator
-       I = SplitNodes.begin(), E = SplitNodes.end(); I != E; ++I) {
-    assert(I->first.Val != N);
-    assert(I->second.first.Val != N);
-    assert(I->second.second.Val != N);
-  }
-}
-
 namespace {
   /// NodeUpdateListener - This class is a DAGUpdateListener that listens for
   /// updates to nodes and recomputes their ready state.
@@ -322,14 +277,15 @@ namespace {
   public:
     NodeUpdateListener(DAGTypeLegalizer &dtl) : DTL(dtl) {}
 
-    virtual void NodeDeleted(SDNode *N) {
-      // Ignore deletes.
+    virtual void NodeDeleted(SDNode *N, SDNode *E) {
       assert(N->getNodeId() != DAGTypeLegalizer::Processed &&
              N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
              "RAUW deleted processed node!");
-#ifndef NDEBUG
-      DTL.SanityCheck(N);
-#endif
+      // 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.
+      assert(E && "Node not replaced?");
+      for (unsigned i = 0, e = E->getNumValues(); i != e; ++i)
+        DTL.NoteReplacement(SDOperand(N, i), SDOperand(E, i));
     }
 
     virtual void NodeUpdated(SDNode *N) {
@@ -359,9 +315,9 @@ void DAGTypeLegalizer::ReplaceValueWith(SDOperand From, SDOperand To) {
   NodeUpdateListener NUL(*this);
   DAG.ReplaceAllUsesOfValueWith(From, To, &NUL);
 
-  // The old node may still be present in ExpandedNodes or PromotedNodes.
-  // Inform them about the replacement.
-  ReplacedNodes[From] = To;
+  // The old node may still be present in a map like ExpandedNodes or
+  // PromotedNodes.  Inform maps about the replacement.
+  NoteReplacement(From, To);
 }
 
 /// ReplaceNodeWith - Replace uses of the 'from' node's results with the 'to'
@@ -379,13 +335,13 @@ void DAGTypeLegalizer::ReplaceNodeWith(SDNode *From, SDNode *To) {
   // can potentially cause recursive merging.
   NodeUpdateListener NUL(*this);
   DAG.ReplaceAllUsesWith(From, To, &NUL);
-  
-  // The old node may still be present in ExpandedNodes or PromotedNodes.
-  // Inform them about the replacement.
+
+  // The old node may still be present in a map like ExpandedNodes or
+  // PromotedNodes.  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[SDOperand(From, i)] = SDOperand(To, i);
+    NoteReplacement(SDOperand(From, i), SDOperand(To, i));
   }
 }
 
@@ -402,7 +358,72 @@ void DAGTypeLegalizer::RemapNode(SDOperand &N) {
   }
 }
 
+/// ExpungeNode - If this is a deleted value that was kept around to speed up
+/// remapping, remove it globally now.  The only map that can have a deleted
+/// node as a source is ReplacedNodes.  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 always performs correct mappings.  The mapping
+/// will always be correct as long as ExpungeNode is called on the source when
+/// adding a new node to ReplacedNodes, and called on the target when adding
+/// a new node to any map.
+void DAGTypeLegalizer::ExpungeNode(SDOperand N) {
+  SDOperand Replacement = N;
+  RemapNode(Replacement);
+  if (Replacement != N) {
+    // Remove N from all maps - this is expensive but extremely rare.
+    ReplacedNodes.erase(N);
+
+    for (DenseMap<SDOperand, SDOperand>::iterator I = ReplacedNodes.begin(),
+         E = ReplacedNodes.end(); I != E; ++I) {
+      if (I->second == N)
+        I->second = Replacement;
+    }
+
+    for (DenseMap<SDOperand, SDOperand>::iterator I = PromotedNodes.begin(),
+         E = PromotedNodes.end(); I != E; ++I) {
+      assert(I->first != N);
+      if (I->second == N)
+        I->second = Replacement;
+    }
+
+    for (DenseMap<SDOperand, SDOperand>::iterator I = FloatToIntedNodes.begin(),
+         E = FloatToIntedNodes.end(); I != E; ++I) {
+      assert(I->first != N);
+      if (I->second == N)
+        I->second = Replacement;
+    }
+
+    for (DenseMap<SDOperand, SDOperand>::iterator I = ScalarizedNodes.begin(),
+         E = ScalarizedNodes.end(); I != E; ++I) {
+      assert(I->first != N);
+      if (I->second == N)
+        I->second = Replacement;
+    }
+
+    for (DenseMap<SDOperand, std::pair<SDOperand, SDOperand> >::iterator
+         I = ExpandedNodes.begin(), E = ExpandedNodes.end(); I != E; ++I) {
+      assert(I->first != N);
+      if (I->second.first == N)
+        I->second.first = Replacement;
+      if (I->second.second == N)
+        I->second.second = Replacement;
+    }
+
+    for (DenseMap<SDOperand, std::pair<SDOperand, SDOperand> >::iterator
+         I = SplitNodes.begin(), E = SplitNodes.end(); I != E; ++I) {
+      assert(I->first != N);
+      if (I->second.first == N)
+        I->second.first = Replacement;
+      if (I->second.second == N)
+        I->second.second = Replacement;
+    }
+  }
+}
+
+
 void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) {
+  ExpungeNode(Result);
   AnalyzeNewNode(Result.Val);
 
   SDOperand &OpEntry = PromotedNodes[Op];
@@ -411,6 +432,7 @@ void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) {
 }
 
 void DAGTypeLegalizer::SetIntegerOp(SDOperand Op, SDOperand Result) {
+  ExpungeNode(Result);
   AnalyzeNewNode(Result.Val);
 
   SDOperand &OpEntry = FloatToIntedNodes[Op];
@@ -419,6 +441,7 @@ void DAGTypeLegalizer::SetIntegerOp(SDOperand Op, SDOperand Result) {
 }
 
 void DAGTypeLegalizer::SetScalarizedOp(SDOperand Op, SDOperand Result) {
+  ExpungeNode(Result);
   AnalyzeNewNode(Result.Val);
 
   SDOperand &OpEntry = ScalarizedNodes[Op];
@@ -437,6 +460,9 @@ void DAGTypeLegalizer::GetExpandedOp(SDOperand Op, SDOperand &Lo,
 }
 
 void DAGTypeLegalizer::SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi) {
+  ExpungeNode(Lo);
+  ExpungeNode(Hi);
+
   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
   AnalyzeNewNode(Lo.Val);
   AnalyzeNewNode(Hi.Val);
@@ -458,6 +484,9 @@ void DAGTypeLegalizer::GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi) {
 }
 
 void DAGTypeLegalizer::SetSplitOp(SDOperand Op, SDOperand Lo, SDOperand Hi) {
+  ExpungeNode(Lo);
+  ExpungeNode(Hi);
+
   // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
   AnalyzeNewNode(Lo.Val);
   AnalyzeNewNode(Hi.Val);