From 8c5f47ac406c817a3bbf1f17281b1a6bbfe7be89 Mon Sep 17 00:00:00 2001 From: Nirav Dave Date: Thu, 22 Mar 2018 19:32:07 +0000 Subject: [PATCH] [DAG, X86] Fix ISel-time node insertion ids As in SystemZ backend, correctly propagate node ids when inserting new unselected nodes into the DAG during instruction Seleciton for X86 target. Fixes PR36865. Reviewers: jyknight, craig.topper Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D44797 llvm-svn: 328233 --- llvm/include/llvm/CodeGen/SelectionDAGISel.h | 3 ++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 19 ++++++- llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp | 10 ++-- llvm/lib/Target/X86/X86ISelDAGToDAG.cpp | 14 +++-- llvm/test/CodeGen/X86/pr36865.ll | 63 ++++++++++++++++++++++ 5 files changed, 98 insertions(+), 11 deletions(-) create mode 100644 llvm/test/CodeGen/X86/pr36865.ll diff --git a/llvm/include/llvm/CodeGen/SelectionDAGISel.h b/llvm/include/llvm/CodeGen/SelectionDAGISel.h index ed6fc76..e56eafc 100644 --- a/llvm/include/llvm/CodeGen/SelectionDAGISel.h +++ b/llvm/include/llvm/CodeGen/SelectionDAGISel.h @@ -110,6 +110,9 @@ public: 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: diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 406e253..fcc1d8f 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -989,14 +989,29 @@ void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) { 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) << " '" diff --git a/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp b/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp index 6e21308..59dd46c 100644 --- a/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp +++ b/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp @@ -593,16 +593,16 @@ bool SystemZDAGToDAGISel::selectAddress(SDValue Addr, // 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()); } } diff --git a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp index 375f965..1edeb85 100644 --- a/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp +++ b/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp @@ -1070,10 +1070,16 @@ bool X86DAGToDAGISel::matchAdd(SDValue N, X86ISelAddressMode &AM, // 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()); } } diff --git a/llvm/test/CodeGen/X86/pr36865.ll b/llvm/test/CodeGen/X86/pr36865.ll new file mode 100644 index 0000000..397b09f --- /dev/null +++ b/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 } -- 2.7.4