Index: llvm/include/llvm/CodeGen/SelectionDAGISel.h
===================================================================
--- llvm/include/llvm/CodeGen/SelectionDAGISel.h
+++ llvm/include/llvm/CodeGen/SelectionDAGISel.h
@@ -110,6 +110,9 @@
                             CodeGenOpt::Level OptLevel,
                             bool IgnoreChains = false);
 
+  static void InvalidateNodeId(SDNode *N);
+  static int getUninvalidatedNodeId(SDNode *N);
+
   static void EnforceNodeIdInvariant(SDNode *N);
 
   // Opcodes used by the DAG state machine:
Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
===================================================================
--- llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -989,14 +989,25 @@
     for (auto *U : N->uses()) {
       auto UId = U->getNodeId();
       if (UId > 0) {
-        int InvalidatedUId = -UId + 1;
-        U->setNodeId(InvalidatedUId);
+        InvalidateNodeId(U);
         Nodes.push_back(U);
       }
     }
   }
 }
 
+void SelectionDAGISel::InvalidateNodeId(SDNode *N) {
+  int InvalidId = -N->getNodeId() + 1;
+  N->setNodeId(InvalidId);
+}
+
+int SelectionDAGISel::getUninvalidatedNodeId(SDNode *N) {
+  int Id = N->getNodeId();
+  if (Id < 0)
+    return -Id + 1;
+  return Id;
+}
+
 void SelectionDAGISel::DoInstructionSelection() {
   DEBUG(dbgs() << "===== Instruction selection begins: "
                << printMBBReference(*FuncInfo->MBB) << " '"
Index: llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
===================================================================
--- llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
+++ llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp
@@ -593,16 +593,16 @@
 // The selection DAG must no longer depend on their uniqueness when this
 // function is used.
 static void insertDAGNode(SelectionDAG *DAG, SDNode *Pos, SDValue N) {
-  if (N.getNode()->getNodeId() == -1 ||
-      N.getNode()->getNodeId() > Pos->getNodeId()) {
+  if (N->getNodeId() == -1 ||
+      (SelectionDAGISel::getUninvalidatedNodeId(N.getNode()) >
+       SelectionDAGISel::getUninvalidatedNodeId(Pos))) {
     DAG->RepositionNode(Pos->getIterator(), N.getNode());
     // Mark Node as invalid for pruning as after this it may be a successor to a
     // selected node but otherwise be in the same position of Pos.
     // Conservatively mark it with the same -abs(Id) to assure node id
     // invariant is preserved.
-    int PId = Pos->getNodeId();
-    int InvalidatedPId = -(PId + 1);
-    N->setNodeId((PId > 0) ? InvalidatedPId : PId);
+    N->setNodeId(Pos->getNodeId());
+    SelectionDAGISel::InvalidateNodeId(N.getNode());
   }
 }
 
Index: llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
===================================================================
--- llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ llvm/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -1070,10 +1070,16 @@
 // IDs! The selection DAG must no longer depend on their uniqueness when this
 // is used.
 static void insertDAGNode(SelectionDAG &DAG, SDValue Pos, SDValue N) {
-  if (N.getNode()->getNodeId() == -1 ||
-      N.getNode()->getNodeId() > Pos.getNode()->getNodeId()) {
-    DAG.RepositionNode(Pos.getNode()->getIterator(), N.getNode());
-    N.getNode()->setNodeId(Pos.getNode()->getNodeId());
+  if (N->getNodeId() == -1 ||
+      (SelectionDAGISel::getUninvalidatedNodeId(N.getNode()) >
+       SelectionDAGISel::getUninvalidatedNodeId(Pos.getNode()))) {
+    DAG.RepositionNode(Pos->getIterator(), N.getNode());
+    // Mark Node as invalid for pruning as after this it may be a successor to a
+    // selected node but otherwise be in the same position of Pos.
+    // Conservatively mark it with the same -abs(Id) to assure node id
+    // invariant is preserved.
+    N->setNodeId(Pos->getNodeId());
+    SelectionDAGISel::InvalidateNodeId(N.getNode());
   }
 }
 
Index: llvm/test/CodeGen/X86/pr36865.ll
===================================================================
--- /dev/null
+++ llvm/test/CodeGen/X86/pr36865.ll
@@ -0,0 +1,63 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple x86_64-unknown-linux-gnu < %s | FileCheck %s
+
+define void @main() {
+; CHECK-LABEL: main:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    subq $424, %rsp # imm = 0x1A8
+; CHECK-NEXT:    .cfi_def_cfa_offset 432
+; CHECK-NEXT:    leaq {{[0-9]+}}(%rsp), %rdi
+; CHECK-NEXT:    xorl %esi, %esi
+; CHECK-NEXT:    movl $400, %edx # imm = 0x190
+; CHECK-NEXT:    callq memset
+; CHECK-NEXT:    movl {{[0-9]+}}(%rsp), %eax
+; CHECK-NEXT:    movl (%rax), %ecx
+; CHECK-NEXT:    addl 0, %eax
+; CHECK-NEXT:    addl %ecx, %eax
+; CHECK-NEXT:    addl %ecx, %eax
+; CHECK-NEXT:    addl {{[0-9]+}}(%rsp), %eax
+; CHECK-NEXT:    movl %eax, {{[0-9]+}}(%rsp)
+; CHECK-NEXT:    movl {{[0-9]+}}(%rsp), %eax
+; CHECK-NEXT:    movl %eax, %ecx
+; CHECK-NEXT:    imull %eax, %ecx
+; CHECK-NEXT:    subl %ecx, %eax
+; CHECK-NEXT:    movl %eax, (%rax)
+entry:
+  %k = alloca i32, align 4
+  %m = alloca i32, align 4
+  %a = alloca [100 x i32], align 16
+  %0 = bitcast [100 x i32]* %a to i8*
+  call void @llvm.memset.p0i8.i64(i8* nonnull align 16 %0, i8 0, i64 400, i1 false)
+  %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* %a, i64 0, i64 34
+  %add = load i32, i32* %k
+  %1 = load i32, i32* null
+  %2 = load i32, i32* undef
+  %3 = load i32, i32* undef
+  %4 = load i32, i32* %arrayidx
+  %5 = load i32, i32* undef
+  %6 = load i32, i32* undef
+  %7 = load i32, i32* undef
+  %8 = load i32, i32* undef
+  %9 = load i32, i32* undef
+  %10 = load i32, i32* undef
+  %11 = load i32, i32* undef
+  %12 = load i32, i32* undef
+  %13 = load i32, i32* undef
+  %14 = load i32, i32* undef
+  %15 = load i32, i32* undef
+  %16 = load i32, i32* undef
+  %add.1 = add i32 %add, %1
+  %add.2 = add i32 %add.1, %2
+  %add.3 = add i32 %add.2, %3
+  %add.4 = add i32 %add.3, %4
+  store i32 %add.4, i32* %k
+  %17 = load i32, i32* %m
+  %mul = mul i32 %17, %17
+  %sub = sub i32 %17, %mul
+  store i32 %sub, i32* undef
+  unreachable
+}
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1) #0
+
+attributes #0 = { argmemonly nounwind }