From a22e8f85e2d434e3c2de1913e5675d049e80ec8a Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Wed, 5 Aug 2015 23:52:42 +0000 Subject: [PATCH] ValueMapper: Rotate distinct node remapping algorithm Rotate the algorithm for remapping distinct nodes in order to simplify how uniquing cycles get resolved. This removes some of the recursion, and, most importantly, exposes all uniquing cycles at the top-level. Besides being a little more efficient -- temporary MDNodes won't live as long -- the clearer logic should help protect against bugs like those fixed in r243961 and r243976. What are uniquing cycles? Why do they present challenges when remapping metadata? !0 = !{!1} !1 = !{!0} !0 and !1 form a simple uniquing cycle. When remapping from one metadata graph to another, every uniquing cycle gets "duplicated" through a dance: !0-temp = !{!1?} ; map(!0): clone !0, VM[!0] = !0-temp !1-temp = !{!0?} ; ..map(!1): clone !1, VM[!1] = !1-temp !1-temp = !{!0-temp} ; ..map(!1): remap !1's operands !2 = !{!0-temp} ; ..map(!1): uniquify: !1-temp => !2 !0-temp = !{!2} ; map(!0): remap !0's operands !3 = !{!2} ; map(!0): uniquify: !0-temp => !3 ; Result !2 = !{!3} !3 = !{!2} (In the two "uniquify" steps above, the operands of !X-temp are compared to the operands of !X. If they're the same, then !X-temp gets RAUW'ed to !X; if they're different, then !X-temp is promoted to a new unique node. The latter case always hits in for uniquing cycles, so we duplicate all the nodes involved.) Why is this a problem? Uniquable Metadata nodes that have temporary node as transitive operands keep RAUW support until the temporary nodes get finalized. With non-cycles, this happens automatically: when a uniquable node's count of unresolved operands drops to zero, it immediately sheds its own RAUW support (possibly triggering the same in any node that references it). However, uniquing cycles create a reference cycle, and uniqued nodes that transitively reference a uniquing cycle are "stuck" in an unresolved state until someone calls `MDNode::resolveCycles()` on a node in the unresolved subgraph. Distinct nodes should help here (and mostly do): since they aren't uniqued anywhere, they are guaranteed not to be RAUW'ed. They effectively form a barrier between uniqued nodes, breaking some uniquing cycles, and shielding uniqued nodes from uniquing cycles. Unfortunately, with this barrier in place, the unresolved subgraph(s) can be disjoint from the top-level node. The mapping algorithm needs to find at least one representative from each disjoint subgraph. But which nodes are *stuck*, and which will get resolved automatically? And which nodes are in the unresolved subgraph? The old logic was conservative. This commit rotates the logic for distinct nodes, so that we have access to unresolved nodes at the top-level call to `llvm::MapMetadata()`. Each time we return to the top-level, we know that all temporaries have been RAUW'ed away. Here, it's safe (and necessary) to call `resolveCycles()` immediately on unresolved operands. This should also perform better than the old algorithm. The recursion stack is shorter, temporary nodes don't live as long, and there are fewer tracking references to unresolved nodes. As the debug info graph introduces more 'distinct' nodes, remapping should incrementally get cheaper and cheaper. Aside from possible performance improvements (and reduced cruft in the `LLVMContext`), there should be no functionality change here. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@244181 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/ValueMapper.cpp | 74 +++++++++++++++------------- 1 file changed, 40 insertions(+), 34 deletions(-) diff --git a/lib/Transforms/Utils/ValueMapper.cpp b/lib/Transforms/Utils/ValueMapper.cpp index 3446462599b..5fdd890e5d8 100644 --- a/lib/Transforms/Utils/ValueMapper.cpp +++ b/lib/Transforms/Utils/ValueMapper.cpp @@ -156,20 +156,20 @@ static Metadata *mapToSelf(ValueToValueMapTy &VM, const Metadata *MD) { } static Metadata *MapMetadataImpl(const Metadata *MD, - SmallVectorImpl &Cycles, + SmallVectorImpl &DistinctWorklist, ValueToValueMapTy &VM, RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer); static Metadata *mapMetadataOp(Metadata *Op, - SmallVectorImpl &Cycles, + SmallVectorImpl &DistinctWorklist, ValueToValueMapTy &VM, RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer) { if (!Op) return nullptr; - if (Metadata *MappedOp = - MapMetadataImpl(Op, Cycles, VM, Flags, TypeMapper, Materializer)) + if (Metadata *MappedOp = MapMetadataImpl(Op, DistinctWorklist, VM, Flags, + TypeMapper, Materializer)) return MappedOp; // Use identity map if MappedOp is null and we can ignore missing entries. if (Flags & RF_IgnoreMissingEntries) @@ -185,7 +185,7 @@ static Metadata *mapMetadataOp(Metadata *Op, /// Remap the operands of an MDNode. static bool remapOperands(MDNode &Node, - SmallVectorImpl &Cycles, + SmallVectorImpl &DistinctWorklist, ValueToValueMapTy &VM, RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer) { @@ -194,8 +194,8 @@ static bool remapOperands(MDNode &Node, bool AnyChanged = false; for (unsigned I = 0, E = Node.getNumOperands(); I != E; ++I) { Metadata *Old = Node.getOperand(I); - Metadata *New = - mapMetadataOp(Old, Cycles, VM, Flags, TypeMapper, Materializer); + Metadata *New = mapMetadataOp(Old, DistinctWorklist, VM, Flags, TypeMapper, + Materializer); if (Old != New) { AnyChanged = true; Node.replaceOperandWith(I, New); @@ -212,7 +212,7 @@ static bool remapOperands(MDNode &Node, /// place; effectively, they're moved from one graph to another. Otherwise, /// they're cloned/duplicated, and the new copy's operands are remapped. static Metadata *mapDistinctNode(const MDNode *Node, - SmallVectorImpl &Cycles, + SmallVectorImpl &DistinctWorklist, ValueToValueMapTy &VM, RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer) { @@ -224,23 +224,16 @@ static Metadata *mapDistinctNode(const MDNode *Node, else NewMD = MDNode::replaceWithDistinct(Node->clone()); - // Remap the operands. If any change, track those that could be involved in - // uniquing cycles. - mapToMetadata(VM, Node, NewMD); - if (remapOperands(*NewMD, Cycles, VM, Flags, TypeMapper, Materializer)) - for (Metadata *Op : NewMD->operands()) - if (auto *Node = dyn_cast_or_null(Op)) - if (!Node->isResolved()) - Cycles.emplace_back(Node); - - return NewMD; + // Remap operands later. + DistinctWorklist.push_back(NewMD); + return mapToMetadata(VM, Node, NewMD); } /// \brief Map a uniqued MDNode. /// /// Uniqued nodes may not need to be recreated (they may map to themselves). static Metadata *mapUniquedNode(const MDNode *Node, - SmallVectorImpl &Cycles, + SmallVectorImpl &DistinctWorklist, ValueToValueMapTy &VM, RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer) { @@ -251,7 +244,8 @@ static Metadata *mapUniquedNode(const MDNode *Node, // returning. auto ClonedMD = Node->clone(); mapToMetadata(VM, Node, ClonedMD.get()); - if (!remapOperands(*ClonedMD, Cycles, VM, Flags, TypeMapper, Materializer)) { + if (!remapOperands(*ClonedMD, DistinctWorklist, VM, Flags, TypeMapper, + Materializer)) { // No operands changed, so use the original. ClonedMD->replaceAllUsesWith(const_cast(Node)); return const_cast(Node); @@ -262,7 +256,7 @@ static Metadata *mapUniquedNode(const MDNode *Node, } static Metadata *MapMetadataImpl(const Metadata *MD, - SmallVectorImpl &Cycles, + SmallVectorImpl &DistinctWorklist, ValueToValueMapTy &VM, RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer) { @@ -307,32 +301,44 @@ static Metadata *MapMetadataImpl(const Metadata *MD, assert(Node->isResolved() && "Unexpected unresolved node"); if (Node->isDistinct()) - return mapDistinctNode(Node, Cycles, VM, Flags, TypeMapper, Materializer); + return mapDistinctNode(Node, DistinctWorklist, VM, Flags, TypeMapper, + Materializer); - return mapUniquedNode(Node, Cycles, VM, Flags, TypeMapper, Materializer); + return mapUniquedNode(Node, DistinctWorklist, VM, Flags, TypeMapper, + Materializer); } Metadata *llvm::MapMetadata(const Metadata *MD, ValueToValueMapTy &VM, RemapFlags Flags, ValueMapTypeRemapper *TypeMapper, ValueMaterializer *Materializer) { - SmallVector Cycles; - Metadata *NewMD = - MapMetadataImpl(MD, Cycles, VM, Flags, TypeMapper, Materializer); + SmallVector DistinctWorklist; + Metadata *NewMD = MapMetadataImpl(MD, DistinctWorklist, VM, Flags, TypeMapper, + Materializer); - if ((Flags & RF_NoModuleLevelChanges) || - (MD == NewMD && !(Flags & RF_MoveDistinctMDs))) { - assert(Cycles.empty() && "Unresolved cycles without remapping anything?"); + // When there are no module-level changes, it's possible that the metadata + // graph has temporaries. Skip the logic to resolve cycles, since it's + // unnecessary (and invalid) in that case. + if (Flags & RF_NoModuleLevelChanges) return NewMD; - } + // If the top-level metadata was a uniqued MDNode, it could be involved in a + // uniquing cycle. if (auto *N = dyn_cast(NewMD)) if (!N->isResolved()) N->resolveCycles(); - // Resolve cycles underneath MD. - for (MDNode *N : Cycles) - if (!N->isResolved()) - N->resolveCycles(); + // Remap the operands of distinct MDNodes. + while (!DistinctWorklist.empty()) { + auto *N = DistinctWorklist.pop_back_val(); + + // If an operand changes, then it may be involved in a uniquing cycle. + if (remapOperands(*N, DistinctWorklist, VM, Flags, TypeMapper, + Materializer)) + for (Metadata *MD : N->operands()) + if (auto *Op = dyn_cast_or_null(MD)) + if (!Op->isResolved()) + Op->resolveCycles(); + } return NewMD; } -- 2.34.1