Index: llvm/trunk/include/llvm/CodeGen/SelectionDAGISel.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/SelectionDAGISel.h +++ llvm/trunk/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, @@ -199,23 +201,28 @@ /// of the new node T. void ReplaceUses(SDValue F, SDValue T) { CurDAG->ReplaceAllUsesOfValueWith(F, T); + EnforceNodeIdInvariant(T.getNode()); } /// ReplaceUses - replace all uses of the old nodes F with the use /// of the new nodes T. void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) { CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num); + for (unsigned i = 0; i < Num; ++i) + EnforceNodeIdInvariant(T[i].getNode()); } /// ReplaceUses - replace all uses of the old node F with the use /// of the new node T. void ReplaceUses(SDNode *F, SDNode *T) { CurDAG->ReplaceAllUsesWith(F, T); + EnforceNodeIdInvariant(T); } /// Replace all uses of \c F with \c T, then remove \c F from the DAG. void ReplaceNode(SDNode *F, SDNode *T) { CurDAG->ReplaceAllUsesWith(F, T); + EnforceNodeIdInvariant(T); CurDAG->RemoveDeadNode(F); } Index: llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp =================================================================== --- llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -960,6 +960,59 @@ } // end anonymous namespace +// This function is used to enforce the topological node id property +// property leveraged during Instruction selection. Before selection all +// nodes are given a non-negative id such that all nodes have a larger id than +// their operands. As this holds transitively we can prune checks that a node N +// is a predecessor of M another by not recursively checking through M's +// operands if N's ID is larger than M's ID. This is significantly improves +// performance of for various legality checks (e.g. IsLegalToFold / +// UpdateChains). + +// However, when we fuse multiple nodes into a single node +// during selection we may induce a predecessor relationship between inputs and +// outputs of distinct nodes being merged violating the topological property. +// Should a fused node have a successor which has yet to be selected, our +// legality checks would be incorrect. To avoid this we mark all unselected +// sucessor nodes, i.e. id != -1 as invalid for pruning by bit-negating (x => +// (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M. +// We use bit-negation to more clearly enforce that node id -1 can only be +// achieved by selected nodes). As the conversion is reversable the original Id, +// topological pruning can still be leveraged when looking for unselected nodes. +// This method is call internally in all ISel replacement calls. +void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) { + SmallVector OpNodes; + SmallVector Nodes; + SmallPtrSet Visited; + OpNodes.push_back(Node); + + while (!OpNodes.empty()) { + SDNode *N = OpNodes.pop_back_val(); + for (const SDValue &Op : N->op_values()) { + if (Op->getNodeId() == -1 && Visited.insert(Op.getNode()).second) + OpNodes.push_back(Op.getNode()); + } + Nodes.push_back(N); + } + + Visited.clear(); + while (!Nodes.empty()) { + SDNode *N = Nodes.pop_back_val(); + + // Don't repeat work. + if (!Visited.insert(N).second) + continue; + for (auto *U : N->uses()) { + auto UId = U->getNodeId(); + if (UId > 0) { + int InvalidatedUId = -UId + 1; + U->setNodeId(InvalidatedUId); + Nodes.push_back(U); + } + } + } +} + void SelectionDAGISel::DoInstructionSelection() { DEBUG(dbgs() << "===== Instruction selection begins: " << printMBBReference(*FuncInfo->MBB) << " '" @@ -995,6 +1048,33 @@ if (Node->use_empty()) continue; +#ifndef NDEBUG + SmallVector Nodes; + Nodes.push_back(Node); + + while (!Nodes.empty()) { + auto N = Nodes.pop_back_val(); + if (Node->getOpcode() == ISD::TokenFactor || Node->getNodeId() < 0) + continue; + for (const SDValue &Op : N->op_values()) { + if (Op->getOpcode() == ISD::TokenFactor) + Nodes.push_back(Op.getNode()); + else { + // We rely on topological ordering of node ids for checking for + // cycles when fusing nodes during selection. All unselected nodes + // successors of an already selected node should have a negative id. + // This assertion will catch such cases. If this assertion triggers + // it is likely you using DAG-level Value/Node replacement functions + // (versus equivalent ISEL replacement) in backend-specific + // selections. See comment in EnforceNodeIdInvariant for more + // details. + 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 @@ -2184,7 +2264,7 @@ WorkList.pop_back(); // NodeId topological order of TokenFactors is not guaranteed. Do not skip. if (Use->getOpcode() != ISD::TokenFactor && - Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1) + Use->getNodeId() < Def->getNodeId() && Use->getNodeId() > 0) continue; // Don't revisit nodes if we already scanned it and didn't fail, we know we @@ -2391,7 +2471,7 @@ static_cast(nullptr)); }); if (ChainNode->getOpcode() != ISD::TokenFactor) - CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain); + ReplaceUses(ChainVal, InputChain); // If the node became dead and we haven't already seen it, delete it. if (ChainNode != NodeToMatch && ChainNode->use_empty() && @@ -2637,8 +2717,8 @@ // Move the glue if needed. if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 && (unsigned)OldGlueResultNo != ResNumResults-1) - CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo), - SDValue(Res, ResNumResults-1)); + ReplaceUses(SDValue(Node, OldGlueResultNo), + SDValue(Res, ResNumResults - 1)); if ((EmitNodeInfo & OPFL_GlueOutput) != 0) --ResNumResults; @@ -2646,14 +2726,15 @@ // Move the chain reference if needed. if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 && (unsigned)OldChainResultNo != ResNumResults-1) - CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo), - SDValue(Res, ResNumResults-1)); + ReplaceUses(SDValue(Node, OldChainResultNo), + SDValue(Res, ResNumResults - 1)); // Otherwise, no replacement happened because the node already exists. Replace // Uses of the old node with the new one. if (Res != Node) { - CurDAG->ReplaceAllUsesWith(Node, Res); - CurDAG->RemoveDeadNode(Node); + ReplaceNode(Node, Res); + } else { + EnforceNodeIdInvariant(Res); } return Res; @@ -2970,8 +3051,7 @@ return; case ISD::AssertSext: case ISD::AssertZext: - CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0), - NodeToMatch->getOperand(0)); + ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0)); CurDAG->RemoveDeadNode(NodeToMatch); return; case ISD::INLINEASM: @@ -3729,7 +3809,7 @@ NodeToMatch->getValueType(i).getSizeInBits() == Res.getValueSizeInBits()) && "invalid replacement"); - CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res); + ReplaceUses(SDValue(NodeToMatch, i), Res); } // Update chain uses. @@ -3742,8 +3822,8 @@ if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) == MVT::Glue && InputGlue.getNode()) - CurDAG->ReplaceAllUsesOfValueWith( - SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1), InputGlue); + ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1), + InputGlue); assert(NodeToMatch->use_empty() && "Didn't replace all uses of the node?"); Index: llvm/trunk/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp =================================================================== --- llvm/trunk/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp +++ llvm/trunk/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp @@ -766,12 +766,11 @@ if (ProduceCarry) { // Replace the carry-use - CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 1), SDValue(AddHi, 1)); + ReplaceUses(SDValue(N, 1), SDValue(AddHi, 1)); } // Replace the remaining uses. - CurDAG->ReplaceAllUsesWith(N, RegSequence); - CurDAG->RemoveDeadNode(N); + ReplaceNode(N, RegSequence); } void AMDGPUDAGToDAGISel::SelectUADDO_USUBO(SDNode *N) { Index: llvm/trunk/lib/Target/ARM/ARMISelDAGToDAG.cpp =================================================================== --- llvm/trunk/lib/Target/ARM/ARMISelDAGToDAG.cpp +++ llvm/trunk/lib/Target/ARM/ARMISelDAGToDAG.cpp @@ -500,7 +500,7 @@ void ARMDAGToDAGISel::replaceDAGValue(const SDValue &N, SDValue M) { CurDAG->RepositionNode(N.getNode()->getIterator(), M.getNode()); - CurDAG->ReplaceAllUsesWith(N, M); + ReplaceUses(N, M); } bool ARMDAGToDAGISel::SelectImmShifterOperand(SDValue N, Index: llvm/trunk/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp =================================================================== --- llvm/trunk/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp +++ llvm/trunk/lib/Target/Hexagon/HexagonISelDAGToDAG.cpp @@ -662,7 +662,7 @@ return; } - CurDAG->ReplaceAllUsesOfValueWith(SDValue(N,0), N->getOperand(0)); + ReplaceUses(SDValue(N, 0), N->getOperand(0)); CurDAG->RemoveDeadNode(N); } @@ -726,7 +726,6 @@ SDNode *T = CurDAG->MorphNodeTo(N, N->getOpcode(), CurDAG->getVTList(OpTy), {Op}); ReplaceNode(T, Op.getNode()); - CurDAG->RemoveDeadNode(T); } void HexagonDAGToDAGISel::SelectP2D(SDNode *N) { @@ -2185,4 +2184,3 @@ RootHeights.clear(); RootWeights.clear(); } - Index: llvm/trunk/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp =================================================================== --- llvm/trunk/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp +++ llvm/trunk/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp @@ -1953,7 +1953,6 @@ // If the mask is all -1's, generate "undef". if (!UseLeft && !UseRight) { ISel.ReplaceNode(N, ISel.selectUndef(SDLoc(SN), ResTy).getNode()); - DAG.RemoveDeadNode(N); return; } @@ -2009,7 +2008,6 @@ NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV}); ISel.ReplaceNode(N, NewN); - DAG.RemoveDeadNode(N); } void HvxSelector::selectVAlign(SDNode *N) { @@ -2070,8 +2068,7 @@ MemOp[0] = cast(N)->getMemOperand(); cast(Result)->setMemRefs(MemOp, MemOp + 1); - ReplaceUses(N, Result); - CurDAG->RemoveDeadNode(N); + ReplaceNode(N, Result); } void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) { @@ -2109,8 +2106,7 @@ MemOp[0] = cast(N)->getMemOperand(); cast(Result)->setMemRefs(MemOp, MemOp + 1); - ReplaceUses(N, Result); - CurDAG->RemoveDeadNode(N); + ReplaceNode(N, Result); } void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) { @@ -2153,5 +2149,3 @@ ReplaceUses(SDValue(N, 1), SDValue(Result, 1)); CurDAG->RemoveDeadNode(N); } - - Index: llvm/trunk/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp =================================================================== --- llvm/trunk/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp +++ llvm/trunk/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp @@ -596,7 +596,13 @@ if (N.getNode()->getNodeId() == -1 || N.getNode()->getNodeId() > Pos->getNodeId()) { DAG->RepositionNode(Pos->getIterator(), N.getNode()); - N.getNode()->setNodeId(Pos->getNodeId()); + // 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); } } @@ -1027,8 +1033,7 @@ }; SDValue New = convertTo( DL, VT, SDValue(CurDAG->getMachineNode(Opcode, DL, OpcodeVT, Ops), 0)); - ReplaceUses(N, New.getNode()); - CurDAG->RemoveDeadNode(N); + ReplaceNode(N, New.getNode()); return true; } @@ -1119,8 +1124,7 @@ SDValue Lower = CurDAG->getConstant(LowerVal, DL, VT); SDValue Or = CurDAG->getNode(Opcode, DL, VT, Upper, Lower); - ReplaceUses(Node, Or.getNode()); - CurDAG->RemoveDeadNode(Node); + ReplaceNode(Node, Or.getNode()); SelectCode(Or.getNode()); } @@ -1618,4 +1622,3 @@ if (MadeChange) CurDAG->RemoveDeadNodes(); } - Index: llvm/trunk/lib/Target/X86/X86ISelDAGToDAG.cpp =================================================================== --- llvm/trunk/lib/Target/X86/X86ISelDAGToDAG.cpp +++ llvm/trunk/lib/Target/X86/X86ISelDAGToDAG.cpp @@ -3094,8 +3094,7 @@ // Emit a testl or testw. SDNode *NewNode = CurDAG->getMachineNode(Op, dl, MVT::i32, Reg, Imm); // Replace CMP with TEST. - CurDAG->ReplaceAllUsesWith(Node, NewNode); - CurDAG->RemoveDeadNode(Node); + ReplaceNode(Node, NewNode); return; } break; Index: llvm/trunk/test/CodeGen/X86/pr36312.ll =================================================================== --- llvm/trunk/test/CodeGen/X86/pr36312.ll +++ llvm/trunk/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 +}