[DAG, X86] Fix ISel-time node insertion ids

[niravd]

Summary

As in SystemZ backend, correctly propagate node ids when inserting new
unselected nodes into the DAG during instruction Seleciton for X86
target.

Fixes PR36865.

[niravd]

Remove unrelated fixup.

[jyknight]

LG after resolving comment.

llvm/include/llvm/CodeGen/SelectionDAGISel.h

113 ↗

(On Diff #139486)

Some comments about what these are for would be good to have here.

llvm/trunk/include/llvm/CodeGen/SelectionDAGISel.h

public:
   /// IsLegalToFold - Returns true if the specific operand node N of
   /// U can be folded during instruction selection that starts at Root.
   /// FIXME: This is a static member function because the MSP430/X86
   /// targets, which uses it during isel.  This could become a proper member.
   static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
                             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:
   enum BuiltinOpcodes {
     OPC_Scope,
     OPC_RecordNode,
     OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3,
     OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7,

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) {
   SmallVector<SDNode *, 4> Nodes;
   Nodes.push_back(Node);
 
   while (!Nodes.empty()) {
     SDNode *N = Nodes.pop_back_val();
     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);
       }
     }
   }
 }
 
+// InvalidateNodeId - As discusses in EnforceNodeIdInvariant, mark a
+// NodeId with the equivalent node id which is invalid for topological
+// pruning.
+void SelectionDAGISel::InvalidateNodeId(SDNode *N) {
+  int InvalidId = -N->getNodeId() + 1;
+  N->setNodeId(InvalidId);
+}
+
+// getUninvalidatedNodeId - get original uninvalidated node id.
+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) << " '"
                << FuncInfo->MBB->getName() << "'\n");
 
   PreprocessISelDAG();
 
   // Select target instructions for the DAG.

llvm/trunk/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp

 }
 
 // Insert a node into the DAG at least before Pos.  This will reposition
 // the node as needed, and will assign it a node ID that is <= Pos's ID.
 // Note that this does *not* preserve the uniqueness of node IDs!
 // 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());
   }
 }
 
 void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM,
                                              EVT VT, SDValue &Base,
                                              SDValue &Disp) const {
   Base = AM.Base;
   if (!Base.getNode())

llvm/trunk/lib/Target/X86/X86ISelDAGToDAG.cpp

 }
 
 // Insert a node into the DAG at least before the Pos node's position. This
 // will reposition the node as needed, and will assign it a node ID that is <=
 // the Pos node's ID. Note that this does *not* preserve the uniqueness of node
 // 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());
   }
 }
 
 // Transform "(X >> (8-C1)) & (0xff << C1)" to "((X >> 8) & 0xff) << C1" if
 // safe. This allows us to convert the shift and and into an h-register
 // extract and a scaled index. Returns false if the simplification is
 // performed.
 static bool foldMaskAndShiftToExtract(SelectionDAG &DAG, SDValue N,

llvm/trunk/test/CodeGen/X86/pr36865.ll

+; 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 }