ignore duplicate divisor uses when transforming into reciprocal multiplies (PR24141)

[spatel]

Summary

PR24141: https://llvm.org/bugs/show_bug.cgi?id=24141
contains a test case where we have duplicate entries in a node's uses() list.

After r241826, we use CombineTo() to delete dead nodes when combining the uses into reciprocal multiplies, but this fails if we encounter the just-deleted node again in the list.

The solution in this patch is to not add duplicate entries to the list of users that we will subsequently iterate over. For the test case, this avoids triggering the combineRepeatedFPDivisors() check entirely because there really is only one user of the divisor.

[echristo]

One inline comment/question. Otherwise it looks OK to me, but I don't do much in here a lot.

-eric

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

8373–8374

Could probably merge it into the existing if statement?

That said, I guess using std::find on it is how we do it for most of these, I assume we don't expect a lot of users and so would want to use a different mechanism?

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

8373–8374

Sure, I can merge it into the compound 'if'.

I thought about changing this to a set (DenseSet?) rather than SmallVector, but I'm also assuming that we would not expect more than a few users, so left it as-is for now.

If you would prefer using a set here, let me know. Thanks!

[spatel]

Patch updated:
I just discovered 'SmallPtrSet'.
Looks like it was designed exactly for this case, so let's use it here instead of a vector. Then, we don't have to use std::find() for dup checking.

[chandlerc]

In D11345#208493, @spatel wrote:

Patch updated:
I just discovered 'SmallPtrSet'.
Looks like it was designed exactly for this case, so let's use it here instead of a vector. Then, we don't have to use std::find() for dup checking.

Egads no, that makes the iteration order unstable.

This whole thing seems wrongly formulated. Why are we walking the *entire* users list prior to finding out whether there are few enough users? I feel like the TLI interface should say how many can be handled rather than accepting a number we want to handle.

And then the code here should be to insert into a SetVector until we exceed that threshold.

[spatel]

In D11345#208610, @chandlerc wrote:

In D11345#208493, @spatel wrote:

Patch updated:
I just discovered 'SmallPtrSet'.
Looks like it was designed exactly for this case, so let's use it here instead of a vector. Then, we don't have to use std::find() for dup checking.

Egads no, that makes the iteration order unstable.

This whole thing seems wrongly formulated. Why are we walking the *entire* users list prior to finding out whether there are few enough users? I feel like the TLI interface should say how many can be handled rather than accepting a number we want to handle.

And then the code here should be to insert into a SetVector until we exceed that threshold.

I'm not following. We're asking the TLI if we have exceeded a minimum threshold, not a maximum. If we exceed the threshold, we want to transform all divisions that have this divisor...so we always have to walk all users?

[hfinkel]

In D11345#208773, @spatel wrote:

In D11345#208610, @chandlerc wrote:

In D11345#208493, @spatel wrote:

Patch updated:
I just discovered 'SmallPtrSet'.
Looks like it was designed exactly for this case, so let's use it here instead of a vector. Then, we don't have to use std::find() for dup checking.

Egads no, that makes the iteration order unstable.

This whole thing seems wrongly formulated. Why are we walking the *entire* users list prior to finding out whether there are few enough users? I feel like the TLI interface should say how many can be handled rather than accepting a number we want to handle.

And then the code here should be to insert into a SetVector until we exceed that threshold.

I'm not following. We're asking the TLI if we have exceeded a minimum threshold, not a maximum. If we exceed the threshold, we want to transform all divisions that have this divisor...so we always have to walk all users?

Part of the issue here is that we might walk all of the users even though TLI.combineRepeatedFPDivisors will return false for any size. This is wasteful. We should just have TLI.combineRepeatedFPDivisors return the size threshold so that we can avoid walking if there is no point (and return false if no combination is ever desired).

Once we know that we're looking for a certain number of users, we can then see if we have enough. As Chandler says, you should use a SetVector so that the iteration order is stable.

Chandler, to be clear, we're not finding out if there are few enough users, we're walking to find out if there are enough (and, if there are, we need to iterate over all of them anyway).

[spatel]

In D11345#212092, @hfinkel wrote:

Part of the issue here is that we might walk all of the users even though TLI.combineRepeatedFPDivisors will return false for any size.

Ah, understood. I forgot the default return is always 'false'.

Let me split this up then:

1. Move the DAGCombiner's combineRepeatedFPDivisors logic into a helper function because it's getting too big (NFC).
2. Fix the TLI hook to return the minimum uses threshold (NFC).
3. Fix the data structure to be a SetVector to fix PR24141.

[spatel]

1. Move the DAGCombiner's combineRepeatedFPDivisors logic into a helper function because it's getting too big (NFC).

Checked in:
http://reviews.llvm.org/rL243293

2. Fix the TLI hook to return the minimum uses threshold (NFC).

Submitted for review:
http://reviews.llvm.org/D11531

3. Fix the data structure to be a SetVector to fix PR24141.

This is a trivial change if the previous change is ok, so I'll abandon this as a patch for review unless someone would like to see the updated patch here prior to commit.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitFDIV(SDNode *N) {
   // may have different costs for FDIV and FMUL, so sometimes the cost of two
   // FDIVs may be lower than the cost of one FDIV and two FMULs. Another reason
   // is the critical path is increased from "one FDIV" to "one FDIV + one FMUL".
   if (Options.UnsafeFPMath) {
     // Skip if current node is a reciprocal.
     if (N0CFP && N0CFP->isExactlyValue(1.0))
       return SDValue();
 
-    SmallVector<SDNode *, 4> Users;
+    // Only count unique users; duplicates may be present in the user list.
+    SmallPtrSet<SDNode*, 4> Users;
     // Find all FDIV users of the same divisor.
-    for (auto *U : N1->uses()) {
+    for (auto *U : N1->uses())
       if (U->getOpcode() == ISD::FDIV && U->getOperand(1) == N1)
-        Users.push_back(U);
-    }
+        Users.insert(U);
 
     if (TLI.combineRepeatedFPDivisors(Users.size())) {
       SDValue FPOne = DAG.getConstantFP(1.0, DL, VT);
       // FIXME: This optimization requires some level of fast-math, so the
       // created reciprocal node should at least have the 'allowReciprocal'
       // fast-math-flag set.
       SDValue Reciprocal = DAG.getNode(ISD::FDIV, DL, VT, FPOne, N1);
 

test/CodeGen/X86/fdiv-combine.ll

 ; CHECK-NEXT:    addsd %xmm2, %xmm0
 ; CHECK-NEXT:    retq
   %div1 = fdiv fast double 1.0, %y
   %div2 = fdiv fast double %x, %y
   %ret = fadd fast double %div2, %div1
   ret double %ret
 }
 
+define void @PR24141() #0 {
+; CHECK-LABEL: PR24141:
+; CHECK:  callq
+; CHECK-NEXT: divsd
+; CHECK-NEXT: jmp
+entry:
+  br label %while.body
+
+while.body:
+  %x.0 = phi double [ undef, %entry ], [ %div, %while.body ]
+  %call = call { double, double } @g(double %x.0)
+  %xv0 = extractvalue { double, double } %call, 0
+  %xv1 = extractvalue { double, double } %call, 1
+  %div = fdiv double %xv0, %xv1
+  br label %while.body
+}
+
+declare { double, double } @g(double)
+
 ; FIXME: If the backend understands 'arcp', then this attribute is unnecessary.
 attributes #0 = { "unsafe-fp-math"="true" }