Fix a nasty bug in LegalizeTypes (spotted in

CodeGen/PowerPC/illegal-element-type.ll): suppose
a node X is processed, and processing maps it to
a node Y.  Then X continues to exist in the DAG,
but with no users.  While processing some other
node, a new node may be created that happens to
be equal to X, and thus X will be reused rather
than a truly new node.  This can cause X to
"magically reappear", and since it is in the
Processed state in will not be reprocessed, so
at the end of type legalization the illegal node
X can still be present.  The solution is to replace
X with Y whenever X gets resurrected like this.


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

6 files changed, 70 insertions, 60 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
index 7497ba2c8d..cfaf0a9c93 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp
@@ -207,9 +207,10 @@ NodeDone:
 #endif
 }
 
-/// MarkNewNodes - The specified node is the root of a subtree of potentially
-/// new nodes.  Add the correct NodeId to mark it.
-void DAGTypeLegalizer::MarkNewNodes(SDNode *N) {
+/// 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(SDNode *&N) {
   // If this was an existing node that is already done, we're done.
   if (N->getNodeId() != NewNode)
     return;
@@ -221,15 +222,39 @@ void DAGTypeLegalizer::MarkNewNodes(SDNode *N) {
   //
   // As we walk the operands, keep track of the number of nodes that are
   // processed.  If non-zero, this will become the new nodeid of this node.
+  // Already processed operands may need to be remapped to the node that
+  // replaced them, which can result in our node changing.  Since remapping
+  // is rare, the code tries to minimize overhead in the non-remapping case.
+
+  SmallVector<SDOperand, 8> NewOps;
   unsigned NumProcessed = 0;
   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
-    int OpId = N->getOperand(i).Val->getNodeId();
-    if (OpId == NewNode)
-      MarkNewNodes(N->getOperand(i).Val);
-    else if (OpId == Processed)
+    SDOperand OrigOp = N->getOperand(i);
+    SDOperand Op = OrigOp;
+
+    if (Op.Val->getNodeId() == Processed)
+      RemapNode(Op);
+
+    if (Op.Val->getNodeId() == NewNode)
+      AnalyzeNewNode(Op.Val);
+    else if (Op.Val->getNodeId() == Processed)
       ++NumProcessed;
+
+    if (!NewOps.empty()) {
+      // Some previous operand changed.  Add this one to the list.
+      NewOps.push_back(Op);
+    } else if (Op != OrigOp) {
+      // This is the first operand to change - add all operands so far.
+      for (unsigned j = 0; j < i; ++j)
+        NewOps.push_back(N->getOperand(j));
+      NewOps.push_back(Op);
+    }
   }
-  
+
+  // Some operands changed - update the node.
+  if (!NewOps.empty())
+    N = DAG.UpdateNodeOperands(SDOperand(N, 0), &NewOps[0], NewOps.size()).Val;
+
   N->setNodeId(N->getNumOperands()-NumProcessed);
   if (N->getNodeId() == ReadyToProcess)
     Worklist.push_back(N);
@@ -258,7 +283,7 @@ namespace {
       assert(N->getNodeId() != DAGTypeLegalizer::Processed &&
              N->getNodeId() != DAGTypeLegalizer::ReadyToProcess &&
              "RAUW updated processed node!");
-      DTL.ReanalyzeNodeFlags(N);
+      DTL.ReanalyzeNode(N);
     }
   };
 }
@@ -269,11 +294,10 @@ namespace {
 /// of From to use To instead.
 void DAGTypeLegalizer::ReplaceValueWith(SDOperand From, SDOperand To) {
   if (From == To) return;
-  
+
   // If expansion produced new nodes, make sure they are properly marked.
-  if (To.Val->getNodeId() == NewNode)
-    MarkNewNodes(To.Val);
-  
+  AnalyzeNewNode(To.Val);
+
   // Anything that used the old node should now use the new one.  Note that this
   // can potentially cause recursive merging.
   NodeUpdateListener NUL(*this);
@@ -288,13 +312,13 @@ void DAGTypeLegalizer::ReplaceValueWith(SDOperand From, SDOperand To) {
 /// node's results.  The from and to node must define identical result types.
 void DAGTypeLegalizer::ReplaceNodeWith(SDNode *From, SDNode *To) {
   if (From == To) return;
+
+  // If expansion produced new nodes, make sure they are properly marked.
+  AnalyzeNewNode(To);
+
   assert(From->getNumValues() == To->getNumValues() &&
          "Node results don't match");
-  
-  // If expansion produced new nodes, make sure they are properly marked.
-  if (To->getNodeId() == NewNode)
-    MarkNewNodes(To);
-  
+
   // Anything that used the old node should now use the new one.  Note that this
   // can potentially cause recursive merging.
   NodeUpdateListener NUL(*this);
@@ -323,8 +347,7 @@ void DAGTypeLegalizer::RemapNode(SDOperand &N) {
 }
 
 void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) {
-  if (Result.Val->getNodeId() == NewNode) 
-    MarkNewNodes(Result.Val);
+  AnalyzeNewNode(Result.Val);
 
   SDOperand &OpEntry = PromotedNodes[Op];
   assert(OpEntry.Val == 0 && "Node is already promoted!");
@@ -332,9 +355,8 @@ void DAGTypeLegalizer::SetPromotedOp(SDOperand Op, SDOperand Result) {
 }
 
 void DAGTypeLegalizer::SetScalarizedOp(SDOperand Op, SDOperand Result) {
-  if (Result.Val->getNodeId() == NewNode) 
-    MarkNewNodes(Result.Val);
-  
+  AnalyzeNewNode(Result.Val);
+
   SDOperand &OpEntry = ScalarizedNodes[Op];
   assert(OpEntry.Val == 0 && "Node is already scalarized!");
   OpEntry = Result;
@@ -352,17 +374,15 @@ void DAGTypeLegalizer::GetExpandedOp(SDOperand Op, SDOperand &Lo,
 }
 
 void DAGTypeLegalizer::SetExpandedOp(SDOperand Op, SDOperand Lo, SDOperand Hi) {
+  // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
+  AnalyzeNewNode(Lo.Val);
+  AnalyzeNewNode(Hi.Val);
+
   // Remember that this is the result of the node.
   std::pair<SDOperand, SDOperand> &Entry = ExpandedNodes[Op];
   assert(Entry.first.Val == 0 && "Node already expanded");
   Entry.first = Lo;
   Entry.second = Hi;
-  
-  // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
-  if (Lo.Val->getNodeId() == NewNode) 
-    MarkNewNodes(Lo.Val);
-  if (Hi.Val->getNodeId() == NewNode) 
-    MarkNewNodes(Hi.Val);
 }
 
 void DAGTypeLegalizer::GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi) {
@@ -375,17 +395,15 @@ void DAGTypeLegalizer::GetSplitOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi) {
 }
 
 void DAGTypeLegalizer::SetSplitOp(SDOperand Op, SDOperand Lo, SDOperand Hi) {
+  // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
+  AnalyzeNewNode(Lo.Val);
+  AnalyzeNewNode(Hi.Val);
+
   // Remember that this is the result of the node.
   std::pair<SDOperand, SDOperand> &Entry = SplitNodes[Op];
   assert(Entry.first.Val == 0 && "Node already split");
   Entry.first = Lo;
   Entry.second = Hi;
-  
-  // Lo/Hi may have been newly allocated, if so, add nodeid's as relevant.
-  if (Lo.Val->getNodeId() == NewNode) 
-    MarkNewNodes(Lo.Val);
-  if (Hi.Val->getNodeId() == NewNode) 
-    MarkNewNodes(Hi.Val);
 }
 
 
diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypes.h b/lib/CodeGen/SelectionDAG/LegalizeTypes.h
index 047c0582d4..7e8ea6640d 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypes.h
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypes.h
@@ -117,16 +117,16 @@ public:
   
   void run();
   
-  /// ReanalyzeNodeFlags - Recompute the NodeID flags for the specified node,
-  /// adding it to the worklist if ready.
-  void ReanalyzeNodeFlags(SDNode *N) {
+  /// ReanalyzeNode - Recompute the NodeID and correct processed operands
+  /// for the specified node, adding it to the worklist if ready.
+  void ReanalyzeNode(SDNode *N) {
     N->setNodeId(NewNode);
-    MarkNewNodes(N);
+    AnalyzeNewNode(N);
   }
-  
+
 private:
-  void MarkNewNodes(SDNode *N);
-  
+  void AnalyzeNewNode(SDNode *&N);
+
   void ReplaceValueWith(SDOperand From, SDOperand To);
   void ReplaceNodeWith(SDNode *From, SDNode *To);
 
diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp
index f9468828f4..0852d7623f 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypesExpand.cpp
@@ -879,8 +879,7 @@ bool DAGTypeLegalizer::ExpandOperand(SDNode *N, unsigned OpNo) {
     // Mark N as new and remark N and its operands.  This allows us to correctly
     // revisit N if it needs another step of promotion and allows us to visit
     // any new operands to N.
-    N->setNodeId(NewNode);
-    MarkNewNodes(N);
+    ReanalyzeNode(N);
     return true;
   }
 
diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypesPromote.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypesPromote.cpp
index 3d4ba7b500..2ff1693e89 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypesPromote.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypesPromote.cpp
@@ -368,11 +368,10 @@ bool DAGTypeLegalizer::PromoteOperand(SDNode *N, unsigned OpNo) {
     // Mark N as new and remark N and its operands.  This allows us to correctly
     // revisit N if it needs another step of promotion and allows us to visit
     // any new operands to N.
-    N->setNodeId(NewNode);
-    MarkNewNodes(N);
+    ReanalyzeNode(N);
     return true;
   }
-  
+
   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
          "Invalid operand expansion");
   
@@ -448,10 +447,8 @@ SDOperand DAGTypeLegalizer::PromoteOperand_SELECT(SDNode *N, unsigned OpNo) {
   // that the value is properly zero extended.
   unsigned BitWidth = Cond.getValueSizeInBits();
   if (!DAG.MaskedValueIsZero(Cond, 
-                             APInt::getHighBitsSet(BitWidth, BitWidth-1))) {
+                             APInt::getHighBitsSet(BitWidth, BitWidth-1)))
     Cond = DAG.getZeroExtendInReg(Cond, MVT::i1);
-    MarkNewNodes(Cond.Val); 
-  }
 
   // The chain (Op#0) and basic block destination (Op#2) are always legal types.
   return DAG.UpdateNodeOperands(SDOperand(N, 0), Cond, N->getOperand(1),
@@ -466,11 +463,9 @@ SDOperand DAGTypeLegalizer::PromoteOperand_BRCOND(SDNode *N, unsigned OpNo) {
   // that the value is properly zero extended.
   unsigned BitWidth = Cond.getValueSizeInBits();
   if (!DAG.MaskedValueIsZero(Cond, 
-                             APInt::getHighBitsSet(BitWidth, BitWidth-1))) {
+                             APInt::getHighBitsSet(BitWidth, BitWidth-1)))
     Cond = DAG.getZeroExtendInReg(Cond, MVT::i1);
-    MarkNewNodes(Cond.Val); 
-  }
-  
+
   // The chain (Op#0) and basic block destination (Op#2) are always legal types.
   return DAG.UpdateNodeOperands(SDOperand(N, 0), N->getOperand(0), Cond,
                                 N->getOperand(2));
diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypesScalarize.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypesScalarize.cpp
index da8fd807a4..d386feb260 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypesScalarize.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypesScalarize.cpp
@@ -182,11 +182,10 @@ bool DAGTypeLegalizer::ScalarizeOperand(SDNode *N, unsigned OpNo) {
     // Mark N as new and remark N and its operands.  This allows us to correctly
     // revisit N if it needs another step of promotion and allows us to visit
     // any new operands to N.
-    N->setNodeId(NewNode);
-    MarkNewNodes(N);
+    ReanalyzeNode(N);
     return true;
   }
-  
+
   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
          "Invalid operand expansion");
   
diff --git a/lib/CodeGen/SelectionDAG/LegalizeTypesSplit.cpp b/lib/CodeGen/SelectionDAG/LegalizeTypesSplit.cpp
index 489aea4c64..bfc497b55a 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeTypesSplit.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeTypesSplit.cpp
@@ -353,11 +353,10 @@ bool DAGTypeLegalizer::SplitOperand(SDNode *N, unsigned OpNo) {
     // Mark N as new and remark N and its operands.  This allows us to correctly
     // revisit N if it needs another step of promotion and allows us to visit
     // any new operands to N.
-    N->setNodeId(NewNode);
-    MarkNewNodes(N);
+    ReanalyzeNode(N);
     return true;
   }
-  
+
   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
          "Invalid operand expansion");