[SelectionDAG] Fix for PR30775: Assertion `NodeToMatch->getOpcode() != ISD::DELETED_NODE && "NodeToMatch was removed partway through selection"' failed.

[ABataev]

Summary

NodeToMatch can be modified during matching, but the code does not handle this situation.
Also fixes PR31536

[RKSimon]

Can the test case be reduced any further?

test/CodeGen/X86/dag-update-nodetomatch.ll

13

Add a comment explaining what the test is testing.

[ABataev]

In D29292#661039, @RKSimon wrote:

Can the test case be reduced any further?

It is already reduced. I tried to reduce the reproducer, this is the best I could do.

test/CodeGen/X86/dag-update-nodetomatch.ll

13

Ok, will do

[RKSimon]

Please can you check if this fixes PR31536 as well?

[ABataev]

In D29292#661549, @RKSimon wrote:

Please can you check if this fixes PR31536 as well?

Yes, fixes

[RKSimon]

In D29292#661687, @ABataev wrote:

In D29292#661549, @RKSimon wrote:

Please can you check if this fixes PR31536 as well?

Yes, fixes

Is it worth adding that test case as well?

[ABataev]

In D29292#661693, @RKSimon wrote:

In D29292#661687, @ABataev wrote:

In D29292#661549, @RKSimon wrote:

Please can you check if this fixes PR31536 as well?

Yes, fixes

Is it worth adding that test case as well?

Ok, will add

[ABataev]

Added test from PR31536 + simplified checks + some small changes.

[RKSimon]

Pity the test cases don't reduce any further...

test/CodeGen/X86/dag-update-nodetomatch.ll

13

Please can you add the bugzilla PR number to the comments for each test?

[ABataev]

test/CodeGen/X86/dag-update-nodetomatch.ll

13

Ok, will do

[ABataev]

Added comments with PR numbers to the test

[ABataev]

Other comments?

[RKSimon]

If the test cases won't reduce any further then I guess this is acceptable.

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

 };
 
 /// \\brief A DAG update listener to keep the matching state
 /// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
 /// change the DAG while matching.  X86 addressing mode matcher is an example
 /// for this.
 class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
 {
-      SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes;
-      SmallVectorImpl<MatchScope> &MatchScopes;
+  SDNode *&NodeToMatch;
+  SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes;
 public:
-  MatchStateUpdater(SelectionDAG &DAG,
-                    SmallVectorImpl<std::pair<SDValue, SDNode*> > &RN,
-                    SmallVectorImpl<MatchScope> &MS) :
-    SelectionDAG::DAGUpdateListener(DAG),
-    RecordedNodes(RN), MatchScopes(MS) { }
+  MatchStateUpdater(SelectionDAG &DAG, SDNode *&NodeToMatch,
+                    SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
+                    SmallVectorImpl<MatchScope> &MS)
+      : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
+        RecordedNodes(RN), MatchScopes(MS) {}
 
   void NodeDeleted(SDNode *N, SDNode *E) override {
     // Some early-returns here to avoid the search if we deleted the node or
     // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
     // do, so it's unnecessary to update matching state at that point).
     // Neither of these can occur currently because we only install this
     // update listener during matching a complex patterns.
     if (!E || E->isMachineOpcode())
       return;
+    // Check if NodeToMatch was updated.
+    if (N == NodeToMatch)
+      NodeToMatch = E;
     // Performing linear search here does not matter because we almost never
     // run this code.  You'd have to have a CSE during complex pattern
     // matching.
     for (auto &I : RecordedNodes)
       if (I.first.getNode() == N)
         I.first.setNode(E);
 
     for (auto &I : MatchScopes)
case OPC_CheckComplexPat: {
       unsigned CPNum = MatcherTable[MatcherIndex++];
       unsigned RecNo = MatcherTable[MatcherIndex++];
       assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
 
       // If target can modify DAG during matching, keep the matching state
       // consistent.
       std::unique_ptr<MatchStateUpdater> MSU;
       if (ComplexPatternFuncMutatesDAG())
-        MSU.reset(new MatchStateUpdater(*CurDAG, RecordedNodes,
+        MSU.reset(new MatchStateUpdater(*CurDAG, NodeToMatch, RecordedNodes,
                                         MatchScopes));
 
       if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
                                RecordedNodes[RecNo].first, CPNum,
                                RecordedNodes))
         break;
       continue;
     }

test/CodeGen/X86/dag-update-nodetomatch.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+
+%struct.i = type { i32, i24 }
+%struct.m = type { %struct.i }
+
+@a = local_unnamed_addr global i32 0, align 4
+@b = local_unnamed_addr global i16 0, align 2
+@c = local_unnamed_addr global i16 0, align 2
+@e = local_unnamed_addr global i16 0, align 2
+@l = local_unnamed_addr global %struct.i zeroinitializer, align 4
+@k = local_unnamed_addr global %struct.m zeroinitializer, align 4
+
+; Function Attrs: norecurse nounwind uwtable
+define void @_Z1nv() local_unnamed_addr {
+; CHECK-LABEL: _Z1nv:
+; CHECK:       # BB#0: # %entry
+; CHECK-NEXT:    movl k+{{.*}}(%rip), %ecx
+; CHECK-NEXT:    movswl {{.*}}(%rip), %r9d
+; CHECK-NEXT:    movswl {{.*}}(%rip), %r8d
+; CHECK-NEXT:    movl {{.*}}(%rip), %eax
+; CHECK-NEXT:    movl {{.*}}(%rip), %esi
+; CHECK-NEXT:    movl %esi, %edi
+; CHECK-NEXT:    shll $7, %edi
+; CHECK-NEXT:    sarl $7, %edi
+; CHECK-NEXT:    negl %edi
+; CHECK-NEXT:    testl %eax, %eax
+; CHECK-NEXT:    cmovel %eax, %edi
+; CHECK-NEXT:    movzwl %cx, %r10d
+; CHECK-NEXT:    leal (%r9,%r10,2), %ecx
+; CHECK-NEXT:    addl %r8d, %ecx
+; CHECK-NEXT:    cmpl %edi, %ecx
+; CHECK-NEXT:    sete %dil
+; CHECK-NEXT:    testl $33554431, %esi # imm = 0x1FFFFFF
+; CHECK-NEXT:    sete %dl
+; CHECK-NEXT:    orb %dil, %dl
+; CHECK-NEXT:    movzbl %dl, %edx
+; CHECK-NEXT:    movw %dx, {{.*}}(%rip)
+; CHECK-NEXT:    shrl $31, %ecx
+; CHECK-NEXT:    xorl $1, %ecx
+; CHECK-NEXT:    addl %r10d, %ecx
+; CHECK-NEXT:    # kill: %CL<def> %CL<kill> %ECX<kill>
+; CHECK-NEXT:    sarl %cl, %eax
+; CHECK-NEXT:    movw %ax, {{.*}}(%rip)
+; CHECK-NEXT:    retq
+entry:
+  %bf.load = load i32, i32* bitcast (i24* getelementptr inbounds (%struct.m, %struct.m* @k, i64 0, i32 0, i32 1) to i32*), align 4
+  %0 = load i16, i16* @c, align 2
+  %conv = sext i16 %0 to i32
+  %1 = load i16, i16* @b, align 2
+  %conv1 = sext i16 %1 to i32
+  %2 = load i32, i32* @a, align 4
+  %tobool = icmp ne i32 %2, 0
+  %bf.load3 = load i32, i32* getelementptr inbounds (%struct.i, %struct.i* @l, i64 0, i32 0), align 4
+  %bf.shl = shl i32 %bf.load3, 7
+  %bf.ashr = ashr exact i32 %bf.shl, 7
+  %bf.clear = shl i32 %bf.load, 1
+  %factor = and i32 %bf.clear, 131070
+  %add13 = add nsw i32 %factor, %conv
+  %add15 = add nsw i32 %add13, %conv1
+  %bf.ashr.op = sub nsw i32 0, %bf.ashr
+  %add28 = select i1 %tobool, i32 %bf.ashr.op, i32 0
+  %tobool29 = icmp eq i32 %add15, %add28
+  %phitmp = icmp eq i32 %bf.ashr, 0
+  %.phitmp = or i1 %phitmp, %tobool29
+  %conv37 = zext i1 %.phitmp to i16
+  store i16 %conv37, i16* @e, align 2
+  %bf.clear39 = and i32 %bf.load, 65535
+  %factor53 = shl nuw nsw i32 %bf.clear39, 1
+  %add46 = add nsw i32 %factor53, %conv
+  %add48 = add nsw i32 %add46, %conv1
+  %add48.lobit = lshr i32 %add48, 31
+  %add48.lobit.not = xor i32 %add48.lobit, 1
+  %add51 = add nuw nsw i32 %add48.lobit.not, %bf.clear39
+  %shr = ashr i32 %2, %add51
+  %conv52 = trunc i32 %shr to i16
+  store i16 %conv52, i16* @b, align 2
+  ret void
+}
+