Recommit r360171: [DAGCombiner] Avoid creating large tokenfactors in visitTokenFactor.

[fhahn]

Summary

If we hit the limit, we do expand the outstanding tokenfactors.
Otherwise, we might drop nodes with users in the unexpanded
tokenfactors. This fixes the crashes reported by Jordan Rupprecht.

[niravd]

Can you get away with just adding all remaining TFs (not their operands) to Ops? That way we keep the TF smaller and the pruning search still happens. That seems sufficient to fix the dropped operator issue.

If my intuition is wrong and we do need to CompletelyExpanded you should disable the pruning search itself when it's not being used.

[fhahn]

In D62633#1522239, @niravd wrote:

Can you get away with just adding all remaining TFs (not their operands) to Ops? That way we keep the TF smaller and the pruning search still happens. That seems sufficient to fix the dropped operator issue.

Yes we can, kind of. If we just add all remaining TFs, we might get stuck in a loop, because in some cases the simplified TokenFactor == N and N gets added to the worklist, because it is the single user of another tokenfactor. I changed it to expand the first outstanding tokenfactor and add the remaining ones unexpanded. THat way, we should not get stuck in a loop, while keeping the size small.

What do you think?

[niravd]

In D62633#1522420, @fhahn wrote:

In D62633#1522239, @niravd wrote:

Can you get away with just adding all remaining TFs (not their operands) to Ops? That way we keep the TF smaller and the pruning search still happens. That seems sufficient to fix the dropped operator issue.

Yes we can, kind of. If we just add all remaining TFs, we might get stuck in a loop, because in some cases the simplified TokenFactor == N and N gets added to the worklist, because it is the single user of another tokenfactor. I changed it to expand the first outstanding tokenfactor and add the remaining ones unexpanded. That way, we should not get stuck in a loop, while keeping the size small.

What do you think?

The problem with doing an small change is that we will definitely revisit the node again because it's changed and will then are likely to do another minor change inlining the next possible token factor. I suspect we're better off deferring updating the Changed predicate for TF operands until we've actually inlined its operands.

[fhahn]

In D62633#1522935, @niravd wrote:

In D62633#1522420, @fhahn wrote:

In D62633#1522239, @niravd wrote:

Can you get away with just adding all remaining TFs (not their operands) to Ops? That way we keep the TF smaller and the pruning search still happens. That seems sufficient to fix the dropped operator issue.

Yes we can, kind of. If we just add all remaining TFs, we might get stuck in a loop, because in some cases the simplified TokenFactor == N and N gets added to the worklist, because it is the single user of another tokenfactor. I changed it to expand the first outstanding tokenfactor and add the remaining ones unexpanded. That way, we should not get stuck in a loop, while keeping the size small.

What do you think?

The problem with doing an small change is that we will definitely revisit the node again because it's changed and will then are likely to do another minor change inlining the next possible token factor. I suspect we're better off deferring updating the Changed predicate for TF operands until we've actually inlined its operands.

Agreed. I went for the current version to avoid a combine cycle which seemed to be caused by the manual AddToWorklist call earlier on. I'll dig some more.

[fhahn]

Only add tokenfactors instead of inlining the first TF. Adjust logic for adding
TFs to the worklist accordingly.

[fhahn]

Bump cutoff to 2048 again, instead of 5 used for testing.

[fhahn]

Add option to adjust inline limit, for testing and added test that crashes with
the original patch.

[niravd]

LGTM modulo typo nit. Thanks!

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1847

nit: s/tokenfacto/Token Factor/g

[fhahn]

Thanks!

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitTokenFactor(SDNode *N) {
   bool Changed = false;             // If we should replace this token factor.
 
   // Start out with this token factor.
   TFs.push_back(N);
 
   // Iterate through token factors.  The TFs grows when new token factors are
   // encountered.
   for (unsigned i = 0; i < TFs.size(); ++i) {
-    SDNode *TF = TFs[i];
+    // Limit number of nodes to inline, to avoid quadratic compile times.
+    // We have to add the outstanding tokenfactors to Ops, otherwise we might
+    // drop Ops from the resulting tokenfactor.
+    if (Ops.size() > 2048) {
+      for (unsigned j = i; j < TFs.size(); j++)
+        Ops.emplace_back(TFs[j], 0);
+      // Drop unprocessed tokenfactors from TFs, so we do not add them to the
+      // combiner worklist later.
+      TFs.resize(i);
+      break;
+    }
 
+    SDNode *TF = TFs[i];
     // Check each of the operands.
     for (const SDValue &Op : TF->op_values()) {
       switch (Op.getOpcode()) {
       case ISD::EntryToken:
         // Entry tokens don't need to be added to the list. They are
         // redundant.
         Changed = true;
         break;
 
       case ISD::TokenFactor:
         if (Op.hasOneUse() && !is_contained(TFs, Op.getNode())) {
           // Queue up for processing.
           TFs.push_back(Op.getNode());
-          // Clean up in case the token factor is removed.
-          AddToWorklist(Op.getNode());
           Changed = true;
           break;
         }
         LLVM_FALLTHROUGH;
 
       default:
         // Only add if it isn't already in the list.
         if (SeenOps.insert(Op.getNode()).second)
           Ops.push_back(Op);
         else
           Changed = true;
         break;
       }
     }
   }
 
+  // Re-visit inlined tokenfactors, to clean them up in case they have been
+  // removed. Skip the first tokenfacto, as this is the current node.
+  for (unsigned i = 1, e = TFs.size(); i < e ; i++)
+    AddToWorklist(TFs[i]);
+
   // Remove Nodes that are chained to another node in the list. Do so
   // by walking up chains breath-first stopping when we've seen
   // another operand. In general we must climb to the EntryNode, but we can exit
   // early if we find all remaining work is associated with just one operand as
   // no further pruning is possible.
 
   // List of nodes to search through and original Ops from which they originate.
   SmallVector<std::pair<SDNode *, unsigned>, 8> Worklist;