[DAG] Fix Node Replacement in PromoteIntBinOp

[niravd]

Summary

When one operand is a user of another in a promoted binary operation
we may replace and delete the returned value before returning
triggering an assertion. Reorder node replacements to prevent this.

Fixes PR34137.

[efriedma]

This is why I hate DAGCombine; you have to constantly worry about the CSE map invalidating pointers you care about, and I'm never confident I'm handling it correctly.

Could we simplify this code using makeEquivalentMemoryOrdering to insert the loads into the right spot in the DAG? Or does that introduce its own RAUW problems?

[niravd]

In D36581#838609, @efriedma wrote:

This is why I hate DAGCombine; you have to constantly worry about the CSE map invalidating pointers you care about, and I'm never confident I'm handling it correctly.

Could we simplify this code using makeEquivalentMemoryOrdering to insert the loads into the right spot in the DAG? Or does that introduce its own RAUW problems?

No, this is a close but unrelated problem. This has been latent for a long while. I'm a little surprised that it required rL297695 to expose this. FWIW I've found that the way to deal with CSE invalidation from multiple replacements is to calculate which nodes need to be replaced upfront (either trivially or checking if there's more than one use) and replacing user nodes before their operands. Clunkier than I'd like, but straightforward. I also have a patch that more aggressively causes invalidation-based assertions where latent bugs may lie; I think it'll catch the lion share of the latent bugs.

[efriedma]

Okay, that makes sense.

Is it possible for N0 to be an ancestor of N1? If it is, do we need to replace N1 before N0?

[niravd]

D'oh. It possible though hard. I'll add a cheap check and swap.

In D36581#839344, @efriedma wrote:

Okay, that makes sense.

Is it possible for N0 to be an ancestor of N1? If it is, do we need to replace N1 before N0?

[niravd]

Add swap when both operands are exapnded loads w/ a dependence.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1181

You need to swap NN0 and NN1, I think?

[dbabokin]

In D36581#838767, @niravd wrote:

I also have a patch that more aggressively causes invalidation-based assertions where latent bugs may lie; I think it'll catch the lion share of the latent bugs.

Let me know if you need to run assertion patch through random testing (which finds all this cases I'm filing as bugs).

[niravd]

Add missing swap

[RKSimon]

In D36581#839584, @dbabokin wrote:

In D36581#838767, @niravd wrote:

I also have a patch that more aggressively causes invalidation-based assertions where latent bugs may lie; I think it'll catch the lion share of the latent bugs.

Let me know if you need to run assertion patch through random testing (which finds all this cases I'm filing as bugs).

Similarly, is there anything that we could add to EXPENSIVE_CHECKS builds to help identify these?

[hans]

Any progress here? PR34137 is marked as a release blocker.

[hans]

In D36581#848166, @hans wrote:

Any progress here? PR34137 is marked as a release blocker.

Nirav: ping?

[niravd]

Missed line added. This should be okay. Can I get an LGTM?

[efriedma]

LGTM.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1180

Calling isPredecessorOf is a little risky; it's usually cheap, but the cost blows up for large DAGs. Hopefully this doesn't cause problems in practice.

[hans]

Nirav asked me to land this since it's a release blocker and he's afk.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
     bool Replace1 = false;
     SDValue N1 = Op.getOperand(1);
     SDValue NN1 = PromoteOperand(N1, PVT, Replace1);
     SDLoc DL(Op);
 
     SDValue RV =
         DAG.getNode(ISD::TRUNCATE, DL, VT, DAG.getNode(Opc, DL, PVT, NN0, NN1));
 
-    // New replace instances of N0 and N1
-    if (Replace0 && N0 && N0.getOpcode() != ISD::DELETED_NODE && NN0 &&
-        NN0.getOpcode() != ISD::DELETED_NODE) {
+    // We are always replacing N0/N1's use in N and only need
+    // additional replacements if there are additional uses.
+    Replace0 &= !N0->hasOneUse();
+    Replace1 &= (N0 != N1) && !N1->hasOneUse();
+
+    // Combine Op here so it is presreved past replacements.
+    CombineTo(Op.getNode(), RV);
+
+    // If operands have a use ordering, make sur we deal with
+    // predecessor first.
+    if (Replace0 && Replace1 && N0.getNode()->isPredecessorOf(N1.getNode())) {
+      std::swap(N0, N1);
+      std::swap(NN0, NN1);
+    }
+
+    if (Replace0) {
       AddToWorklist(NN0.getNode());
       ReplaceLoadWithPromotedLoad(N0.getNode(), NN0.getNode());
     }
-
-    if (Replace1 && N1 && N1.getOpcode() != ISD::DELETED_NODE && NN1 &&
-        NN1.getOpcode() != ISD::DELETED_NODE) {
+    if (Replace1) {
       AddToWorklist(NN1.getNode());
       ReplaceLoadWithPromotedLoad(N1.getNode(), NN1.getNode());
     }
-
-    // Deal with Op being deleted.
-    if (Op && Op.getOpcode() != ISD::DELETED_NODE)
-      return RV;
+    return Op;
   }
   return SDValue();
 }
 
 /// Promote the specified integer shift operation if the target indicates it is
 /// beneficial. e.g. On x86, it's usually better to promote i16 operations to
 /// i32 since i16 instructions are longer.
 SDValue DAGCombiner::PromoteIntShiftOp(SDValue Op) {
while (StoreNodes.size() > 1) {
 
     // Transfer chain users from old loads to the new load.
     for (unsigned i = 0; i < NumElem; ++i) {
       LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[i].MemNode);
       DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1),
                                     SDValue(NewLoad.getNode(), 1));
     }
 
-    // Replace the all stores with the new store.
-    for (unsigned i = 0; i < NumElem; ++i)
+    // Replace the all stores with the new store. Recursively remove
+    // corresponding value if its no longer used.
+    for (unsigned i = 0; i < NumElem; ++i) {
+      SDValue Val = StoreNodes[i].MemNode->getOperand(1);
       CombineTo(StoreNodes[i].MemNode, NewStore);
+      if (Val.getNode()->use_empty())
+        recursivelyDeleteUnusedNodes(Val.getNode());
+    }
+
     RV = true;
     StoreNodes.erase(StoreNodes.begin(), StoreNodes.begin() + NumElem);
     continue;
   }
   return RV;
 }
 
 SDValue DAGCombiner::replaceStoreChain(StoreSDNode *ST, SDValue BetterChain) {

test/CodeGen/X86/pr34137.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+
+@var_3 = external global i16, align 2
+@var_13 = external global i16, align 2
+@var_212 = external global i64, align 8
+
+define void @pr34127() {
+; CHECK-LABEL: pr34127:
+; CHECK:       # BB#0: # %entry
+; CHECK-NEXT:    movzwl {{.*}}(%rip), %eax
+; CHECK-NEXT:    movw {{.*}}(%rip), %cx
+; CHECK-NEXT:    andw %ax, %cx
+; CHECK-NEXT:    andl %eax, %ecx
+; CHECK-NEXT:    movl %ecx, -{{[0-9]+}}(%rsp)
+; CHECK-NEXT:    xorl %edx, %edx
+; CHECK-NEXT:    testw %cx, %cx
+; CHECK-NEXT:    sete %dl
+; CHECK-NEXT:    andl %eax, %edx
+; CHECK-NEXT:    movq %rdx, {{.*}}(%rip)
+; CHECK-NEXT:    movw $0, (%rax)
+; CHECK-NEXT:    retq
+entry:
+  %a = alloca i32, align 4
+  %0 = load i16, i16* @var_3, align 2
+  %conv = zext i16 %0 to i32
+  %1 = load i16, i16* @var_3, align 2
+  %conv1 = zext i16 %1 to i32
+  %2 = load i16, i16* @var_13, align 2
+  %conv2 = zext i16 %2 to i32
+  %and = and i32 %conv1, %conv2
+  %and3 = and i32 %conv, %and
+  store i32 %and3, i32* %a, align 4
+  %3 = load i16, i16* @var_3, align 2
+  %conv4 = zext i16 %3 to i32
+  %4 = load i16, i16* @var_3, align 2
+  %conv5 = zext i16 %4 to i32
+  %5 = load i16, i16* @var_13, align 2
+  %conv6 = zext i16 %5 to i32
+  %and7 = and i32 %conv5, %conv6
+  %and8 = and i32 %conv4, %and7
+  %tobool = icmp ne i32 %and8, 0
+  %lnot = xor i1 %tobool, true
+  %conv9 = zext i1 %lnot to i32
+  %6 = load i16, i16* @var_3, align 2
+  %conv10 = zext i16 %6 to i32
+  %and11 = and i32 %conv9, %conv10
+  %conv12 = sext i32 %and11 to i64
+  store i64 %conv12, i64* @var_212, align 8
+  %conv14 = zext i1 undef to i16
+  store i16 %conv14, i16* undef, align 2
+  ret void
+}