[DAG] Enforce stricter NodeId invariant during Instruction selection

Instruction Selection makes use of the topological ordering of nodes
by node id (a node's operands have smaller node id than it) when doing
cycle detection.  During selection we may violate this property as a
selection of multiple nodes may induce a use dependence (and thus a
node id restriction) between two unrelated nodes. If a selected node
has an unselected successor this may allow us to miss a cycle in
detection an invalid selection.

This patch fixes this by marking all unselected successors of a
selected node have negated node id.  We avoid pruning on such negative
ids but still can reconstruct the original id for pruning.

In-tree targets have been updated to replace DAG-level replacements
with ISel-level ones which enforce this property.

This preemptively fixes PR36312 before triggering commit r324359 relands

Reviewers: craig.topper, bogner, jyknight

Subscribers: arsenm, nhaehnle, javed.absar, llvm-commits, hiraditya

Differential Revision: https://reviews.llvm.org/D43198

llvm-svn: 327170

1 files changed, 36 insertions, 0 deletions

diff --git a/llvm/test/CodeGen/X86/pr36312.ll b/llvm/test/CodeGen/X86/pr36312.ll
new file mode 100644
index 00000000000..ea892ee292f
--- /dev/null
+++ b/llvm/test/CodeGen/X86/pr36312.ll
@@ -0,0 +1,36 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+
+%struct.anon = type { i32, i32 }
+
+@c = common  global %struct.anon zeroinitializer, align 4
+@d =  local_unnamed_addr global %struct.anon* @c, align 8
+@a = common  local_unnamed_addr global i32 0, align 4
+@b = common  local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: norecurse nounwind uwtable
+define  void @g() local_unnamed_addr #0 {
+; CHECK-LABEL: g:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    movq {{.*}}(%rip), %rax
+; CHECK-NEXT:    movl {{.*}}(%rip), %ecx
+; CHECK-NEXT:    xorl %edx, %edx
+; CHECK-NEXT:    incl %ecx
+; CHECK-NEXT:    setne %dl
+; CHECK-NEXT:    addl 4(%rax), %edx
+; CHECK-NEXT:    movl %ecx, {{.*}}(%rip)
+; CHECK-NEXT:    movl %edx, {{.*}}(%rip)
+; CHECK-NEXT:    retq
+entry:
+  %0 = load %struct.anon*, %struct.anon** @d, align 8
+  %y = getelementptr inbounds %struct.anon, %struct.anon* %0, i64 0, i32 1
+  %1 = load i32, i32* %y, align 4
+  %2 = load i32, i32* @b, align 4
+  %inc = add nsw i32 %2, 1
+  store i32 %inc, i32* @b, align 4
+  %tobool = icmp ne i32 %inc, 0
+  %land.ext = zext i1 %tobool to i32
+  %add = add nsw i32 %1, %land.ext
+  store i32 %add, i32* @a, align 4
+  ret void
+}