Index: llvm/include/llvm/CodeGen/SelectionDAGISel.h =================================================================== --- llvm/include/llvm/CodeGen/SelectionDAGISel.h +++ llvm/include/llvm/CodeGen/SelectionDAGISel.h @@ -110,6 +110,8 @@ CodeGenOpt::Level OptLevel, bool IgnoreChains = false); + static void EnforceNodeIdInvariant(SDNode *N); + // Opcodes used by the DAG state machine: enum BuiltinOpcodes { OPC_Scope, Index: llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp =================================================================== --- llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -972,6 +972,37 @@ if (Node->use_empty()) continue; + // We rely on topological ordering of node ids for checking for + // cycles when fusing nodes during selection. For correctness we + // expect that any successor nodes have a node id of -1. Ignore + // TokenFactor node ids for this. Also assume Constants and + // RegisterCopies may be ignored. + +#ifndef NDEBUG + SmallVector Nodes; + Nodes.push_back(Node); + + while (!Nodes.empty()) { + auto N = Nodes.pop_back_val(); + if (Node->getOpcode() == ISD::TokenFactor || Node->getNodeId() == -1) + continue; + for (const SDValue &Op : N->op_values()) { + if (Op->getOpcode() == ISD::TokenFactor) + Nodes.push_back(Op.getNode()); + else if (Op->getOpcode() != ISD::Constant && + Op->getOpcode() != ISD::TargetConstant && + Op->getOpcode() != ISD::CopyToReg && + Op->getOpcode() != ISD::CopyFromReg) + // If you are seeing this assertion trigger instruction selection + // the topological ordering of node ids may be violated breaking our + // cycle detection. It is likely that can be fixed by calling + // EnforceNodeIdInvariant(Op) whereever Op is selected. + assert(Op->getNodeId() != -1 && + "Node has already selected predecessor node"); + } + } +#endif + // When we are using non-default rounding modes or FP exception behavior // FP operations are represented by StrictFP pseudo-operations. They // need to be simplified here so that the target-specific instruction @@ -2265,6 +2296,31 @@ return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains); } +// This function is used to enforce the ISEL proproperty that all +// unselected successor nodes to selected nodes must have node id +// -1. This preserves the topological node id invariant used in +// cycle searches (most likely IsLegalToFold). +// +// This should be called on all selected nodes if they result from a +// fusion including an output from a non-root (a node that is not +// explicitly being called by Select). +void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) { + SmallVector Nodes; + SmallPtrSet Visited; + Nodes.push_back(Node); + + while (!Nodes.empty()) { + SDNode *N = Nodes.pop_back_val(); + // Don't repeat work. + if (!Visited.insert(N).second) + continue; + N->setNodeId(-1); + for (auto *U : N->uses()) + if (U->getNodeId() != -1) + Nodes.push_back(U); + } +} + void SelectionDAGISel::Select_INLINEASM(SDNode *N) { SDLoc DL(N); @@ -2373,6 +2429,7 @@ !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode)) NowDeadNodes.push_back(ChainNode); } + EnforceNodeIdInvariant(InputChain.getNode()); } if (!NowDeadNodes.empty()) Index: llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp =================================================================== --- llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp +++ llvm/lib/Target/ARM/ARMISelDAGToDAG.cpp @@ -2485,15 +2485,18 @@ // 1. Mask includes the LSB -> Simply shift the top N bits off NewN = EmitShift(ARM::tLSLri, X, 31 - Range->first); ReplaceNode(And.getNode(), NewN); + EnforceNodeIdInvariant(NewN); } else if (Range->first == 31) { // 2. Mask includes the MSB -> Simply shift the bottom N bits off NewN = EmitShift(ARM::tLSRri, X, Range->second); ReplaceNode(And.getNode(), NewN); + EnforceNodeIdInvariant(NewN); } else if (Range->first == Range->second) { // 3. Only one bit is set. We can shift this into the sign bit and use a // PL/MI comparison. NewN = EmitShift(ARM::tLSLri, X, 31 - Range->first); ReplaceNode(And.getNode(), NewN); + EnforceNodeIdInvariant(NewN); SwitchEQNEToPLMI = true; } else if (!Subtarget->hasV6T2Ops()) { @@ -2503,6 +2506,7 @@ NewN = EmitShift(ARM::tLSRri, SDValue(NewN, 0), Range->second + (31 - Range->first)); ReplaceNode(And.getNode(), NewN); + EnforceNodeIdInvariant(NewN); } } @@ -2892,6 +2896,7 @@ ReplaceUses(SDValue(N, 0), SDValue(Chain.getNode(), Chain.getResNo())); CurDAG->RemoveDeadNode(N); + EnforceNodeIdInvariant(ResNode); return; } @@ -2939,6 +2944,7 @@ if (InFlag.getOpcode() == ARMISD::CMPZ) { bool SwitchEQNEToPLMI; SelectCMPZ(InFlag.getNode(), SwitchEQNEToPLMI); + EnforceNodeIdInvariant(InFlag.getNode()); if (SwitchEQNEToPLMI) { SDValue ARMcc = N->getOperand(2); @@ -2958,6 +2964,7 @@ SDValue Ops[] = {N->getOperand(0), N->getOperand(1), NewARMcc, N->getOperand(3), N->getOperand(4)}; CurDAG->MorphNodeTo(N, ARMISD::CMOV, N->getVTList(), Ops); + EnforceNodeIdInvariant(N); } } Index: llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp =================================================================== --- llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp +++ llvm/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp @@ -327,6 +327,8 @@ SDValue F[] = { SDValue(N,0), SDValue(N,1), SDValue(C,0), SDValue(C,1) }; SDValue T[] = { SDValue(L,0), SDValue(S,0), SDValue(L,1), SDValue(S,0) }; ReplaceUses(F, T, array_lengthof(T)); + EnforceNodeIdInvariant(L); + EnforceNodeIdInvariant(S); // This transformation will leave the intrinsic dead. If it remains in // the DAG, the selection code will see it again, but without the load, // and it will generate a store that is normally required for it. Index: llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp =================================================================== --- llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp +++ llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp @@ -952,9 +952,10 @@ WorkQ.insert(W->getOperand(j).getNode()); } - for (SDNode *L : Nodes) + for (SDNode *L : Nodes) { ISel.Select(L); - + ISel.EnforceNodeIdInvariant(L); + } return !Nodes.empty(); } @@ -1016,6 +1017,7 @@ }); ISel.ReplaceNode(InpN, OutN); + ISel.EnforceNodeIdInvariant(OutN); selectVectorConstants(OutN); DAG.RemoveDeadNodes(); } @@ -1344,6 +1346,7 @@ assert(!N->use_empty()); ISel.ReplaceNode(N, LV.getNode()); + ISel.EnforceNodeIdInvariant(LV.getNode()); DAG.RemoveDeadNodes(); std::deque SubNodes; @@ -1927,7 +1930,9 @@ }); // If the mask is all -1's, generate "undef". if (!UseLeft && !UseRight) { - ISel.ReplaceNode(N, ISel.selectUndef(SDLoc(SN), ResTy).getNode()); + auto *N2 = ISel.selectUndef(SDLoc(SN), ResTy).getNode(); + ISel.ReplaceNode(N, N2); + ISel.EnforceNodeIdInvariant(N2); DAG.RemoveDeadNode(N); return; } @@ -1984,6 +1989,7 @@ NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV}); ISel.ReplaceNode(N, NewN); + ISel.EnforceNodeIdInvariant(NewN); DAG.RemoveDeadNode(N); } @@ -2032,6 +2038,7 @@ cast(Result)->setMemRefs(MemOp, MemOp + 1); ReplaceUses(N, Result); + EnforceNodeIdInvariant(Result); CurDAG->RemoveDeadNode(N); } @@ -2071,6 +2078,7 @@ cast(Result)->setMemRefs(MemOp, MemOp + 1); ReplaceUses(N, Result); + EnforceNodeIdInvariant(Result); CurDAG->RemoveDeadNode(N); } @@ -2112,7 +2120,6 @@ ReplaceUses(N, Result); ReplaceUses(SDValue(N, 0), SDValue(Result, 0)); ReplaceUses(SDValue(N, 1), SDValue(Result, 1)); + EnforceNodeIdInvariant(Result); CurDAG->RemoveDeadNode(N); } - - Index: llvm/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp =================================================================== --- llvm/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp +++ llvm/lib/Target/MSP430/MSP430ISelDAGToDAG.cpp @@ -371,6 +371,8 @@ ReplaceUses(SDValue(N1.getNode(), 2), SDValue(ResNode, 2)); // Transfer writeback. ReplaceUses(SDValue(N1.getNode(), 1), SDValue(ResNode, 1)); + // Enforce Node Id invariant on ResNode. + EnforceNodeIdInvariant(ResNode); return true; } Index: llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp =================================================================== --- llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp +++ llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp @@ -991,6 +991,7 @@ insertDAGNode(CurDAG, N, New); ReplaceNode(N, New.getNode()); N = New.getNode(); + EnforceNodeIdInvariant(N); } // Now, select the machine opcode to implement this operation. if (!N->isMachineOpcode()) Index: llvm/lib/Target/X86/X86ISelDAGToDAG.cpp =================================================================== --- llvm/lib/Target/X86/X86ISelDAGToDAG.cpp +++ llvm/lib/Target/X86/X86ISelDAGToDAG.cpp @@ -2382,6 +2382,9 @@ ReplaceUses(SDValue(StoreNode, 0), SDValue(Result, 1)); ReplaceUses(SDValue(StoredVal.getNode(), 1), SDValue(Result, 0)); CurDAG->RemoveDeadNode(Node); + // Result has outputs originally from other nodes than StoreNode so we need to + // fixup successor nodeids + EnforceNodeIdInvariant(Result); return true; } @@ -2971,6 +2974,7 @@ InFlag = SDValue(CNode, 1); // Update the chain. ReplaceUses(N1.getValue(1), SDValue(CNode, 0)); + EnforceNodeIdInvariant(CNode); // Record the mem-refs MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1); MemOp[0] = cast(N1)->getMemOperand(); Index: llvm/test/CodeGen/X86/pr36312.ll =================================================================== --- /dev/null +++ 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 +}