From 267185ec922b29ddc25684b89ac8fec2d7d027e2 Mon Sep 17 00:00:00 2001 From: "Duncan P. N. Exon Smith" Date: Fri, 8 Apr 2016 00:33:44 +0000 Subject: [PATCH] ValueMapper: Treat LocalAsMetadata more like function-local Values This is a partial re-commit -- maybe more of a re-implementation -- of r265631 (reverted in r265637). This makes RF_IgnoreMissingLocals behave (almost) consistently between the Value and the Metadata hierarchy. In particular: - MapValue returns nullptr or "metadata !{}" for missing locals in MetadataAsValue/LocalAsMetadata bridging paris, depending on the RF_IgnoreMissingLocals flag. - MapValue doesn't memoize LocalAsMetadata-related results. - MapMetadata no longer deals with LocalAsMetadata or RF_IgnoreMissingLocals at all. (This wasn't in r265631 at all, but I realized during testing it would make the patch simpler with no loss of generality.) r265631 went too far, making both functions universally ignore RF_IgnoreMissingLocals. This broke building (e.g.) compiler-rt. Reassociate (and possibly other passes) don't currently maintain dominates-use invariants for metadata operands, resulting in IR like this: define void @foo(i32 %arg) { call void @llvm.some.intrinsic(metadata i32 %x) %x = add i32 1, i32 %arg } If the inliner chooses to inline @foo into another function, then RemapInstruction will call `MapValue(metadata i32 %x)` and assert that the return is not nullptr. I've filed PR27273 to add a Verifier check and fix the underlying problem in the optimization passes. As a workaround, return `!{}` instead of nullptr for unmapped LocalAsMetadata when RF_IgnoreMissingLocals is unset. Otherwise, match the behaviour of r265631. Original commit message: ValueMapper: Make LocalAsMetadata match function-local Values Start treating LocalAsMetadata similarly to function-local members of the Value hierarchy in MapValue and MapMetadata. - Don't memoize them. - Return nullptr if they are missing. This also cleans up ConstantAsMetadata to stop listening to the RF_IgnoreMissingLocals flag. llvm-svn: 265759 --- llvm/include/llvm/Transforms/Utils/ValueMapper.h | 42 ++++++++-- llvm/lib/IR/Verifier.cpp | 4 + llvm/lib/Transforms/Utils/ValueMapper.cpp | 72 ++++++++++++---- .../Inline/local-as-metadata-undominated-use.ll | 49 +++++++++++ .../unittests/Transforms/Utils/ValueMapperTest.cpp | 95 ++++++++++++++++++++++ 5 files changed, 239 insertions(+), 23 deletions(-) create mode 100644 llvm/test/Transforms/Inline/local-as-metadata-undominated-use.ll diff --git a/llvm/include/llvm/Transforms/Utils/ValueMapper.h b/llvm/include/llvm/Transforms/Utils/ValueMapper.h index e8023bd..e4dedfe 100644 --- a/llvm/include/llvm/Transforms/Utils/ValueMapper.h +++ b/llvm/include/llvm/Transforms/Utils/ValueMapper.h @@ -68,13 +68,21 @@ enum RemapFlags { RF_NoModuleLevelChanges = 1, /// If this flag is set, the remapper ignores missing function-local entries - /// (Argument, Instruction, BasicBlock) that are not in the - /// value map. If it is unset, it aborts if an operand is asked to be - /// remapped which doesn't exist in the mapping. + /// (Argument, Instruction, BasicBlock) that are not in the value map. If it + /// is unset, it aborts if an operand is asked to be remapped which doesn't + /// exist in the mapping. /// - /// There are no such assertions in MapValue(), whose result should be - /// essentially unchanged by this flag. This only changes the assertion - /// behaviour in RemapInstruction(). + /// There are no such assertions in MapValue(), whose results are almost + /// unchanged by this flag. This flag mainly changes the assertion behaviour + /// in RemapInstruction(). + /// + /// Since an Instruction's metadata operands (even that point to SSA values) + /// aren't guaranteed to be dominated by their definitions, MapMetadata will + /// return "!{}" instead of "null" for \a LocalAsMetadata instances whose SSA + /// values are unmapped when this flag is set. Otherwise, \a MapValue() + /// completely ignores this flag. + /// + /// \a MapMetadata() always ignores this flag. RF_IgnoreMissingLocals = 2, /// Instruct the remapper to move distinct metadata instead of duplicating it @@ -101,12 +109,32 @@ static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) { /// 3. Else if \c V is a function-local value, return nullptr. /// 4. Else if \c V is a \a GlobalValue, return \c nullptr or \c V depending /// on \a RF_NullMapMissingGlobalValues. -/// 5. Else, Compute the equivalent constant, and return it. +/// 5. Else if \c V is a \a MetadataAsValue wrapping a LocalAsMetadata, +/// recurse on the local SSA value, and return nullptr or "metadata !{}" on +/// missing depending on RF_IgnoreMissingValues. +/// 6. Else if \c V is a \a MetadataAsValue, rewrap the return of \a +/// MapMetadata(). +/// 7. Else, compute the equivalent constant, and return it. Value *MapValue(const Value *V, ValueToValueMapTy &VM, RemapFlags Flags = RF_None, ValueMapTypeRemapper *TypeMapper = nullptr, ValueMaterializer *Materializer = nullptr); +/// Lookup or compute a mapping for a piece of metadata. +/// +/// Compute and memoize a mapping for \c MD. +/// +/// 1. If \c MD is mapped, return it. +/// 2. Else if \a RF_NoModuleLevelChanges or \c MD is an \a MDString, return +/// \c MD. +/// 3. Else if \c MD is a \a ConstantAsMetadata, call \a MapValue() and +/// re-wrap its return (returning nullptr on nullptr). +/// 4. Else, \c MD is an \a MDNode. These are remapped, along with their +/// transitive operands. Distinct nodes are duplicated or moved depending +/// on \a RF_MoveDistinctNodes. Uniqued nodes are remapped like constants. +/// +/// \note \a LocalAsMetadata is completely unsupported by \a MapMetadata. +/// Instead, use \a MapValue() with its wrapping \a MetadataAsValue instance. Metadata *MapMetadata(const Metadata *MD, ValueToValueMapTy &VM, RemapFlags Flags = RF_None, ValueMapTypeRemapper *TypeMapper = nullptr, diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp index abb0e9b..b0c77a0 100644 --- a/llvm/lib/IR/Verifier.cpp +++ b/llvm/lib/IR/Verifier.cpp @@ -3502,6 +3502,10 @@ void Verifier::verifyDominatesUse(Instruction &I, unsigned i) { // Quick check whether the def has already been encountered in the same block. // PHI nodes are not checked to prevent accepting preceeding PHIs, because PHI // uses are defined to happen on the incoming edge, not at the instruction. + // + // FIXME: If this operand is a MetadataAsValue (wrapping a LocalAsMetadata) + // wrapping an SSA value, assert that we've already encountered it. See + // related FIXME in Mapper::mapLocalAsMetadata in ValueMapper.cpp. if (!isa(I) && InstsInThisBlock.count(Op)) return; diff --git a/llvm/lib/Transforms/Utils/ValueMapper.cpp b/llvm/lib/Transforms/Utils/ValueMapper.cpp index 59870f8..ca48290 100644 --- a/llvm/lib/Transforms/Utils/ValueMapper.cpp +++ b/llvm/lib/Transforms/Utils/ValueMapper.cpp @@ -86,6 +86,20 @@ public: /// (not an MDNode, or MDNode::isResolved() returns true). Metadata *mapMetadata(const Metadata *MD); + // Map LocalAsMetadata, which never gets memoized. + // + // If the referenced local is not mapped, the principled return is nullptr. + // However, optimization passes sometimes move metadata operands *before* the + // SSA values they reference. To prevent crashes in \a RemapInstruction(), + // return "!{}" when RF_IgnoreMissingLocals is not set. + // + // \note Adding a mapping for LocalAsMetadata is unsupported. Add a mapping + // to the value map for the SSA value in question instead. + // + // FIXME: Once we have a verifier check for forward references to SSA values + // through metadata operands, always return nullptr on unmapped locals. + Metadata *mapLocalAsMetadata(const LocalAsMetadata &LAM); + private: Value *mapBlockAddress(const BlockAddress &BA); @@ -294,18 +308,32 @@ Value *Mapper::mapValue(const Value *V) { if (const auto *MDV = dyn_cast(V)) { const Metadata *MD = MDV->getMetadata(); + + if (auto *LAM = dyn_cast(MD)) { + // Look through to grab the local value. + if (Value *LV = mapValue(LAM->getValue())) { + if (V == LAM->getValue()) + return const_cast(V); + return MetadataAsValue::get(V->getContext(), LocalAsMetadata::get(LV)); + } + + // FIXME: always return nullptr once Verifier::verifyDominatesUse() + // ensures metadata operands only reference defined SSA values. + return (Flags & RF_IgnoreMissingLocals) + ? nullptr + : MetadataAsValue::get(V->getContext(), + MDTuple::get(V->getContext(), None)); + } + // If this is a module-level metadata and we know that nothing at the module // level is changing, then use an identity mapping. - if (!isa(MD) && (Flags & RF_NoModuleLevelChanges)) + if (Flags & RF_NoModuleLevelChanges) return VM[V] = const_cast(V); - // FIXME: be consistent with function-local values for LocalAsMetadata by - // returning nullptr when LocalAsMetadata is missing. Adding a mapping is - // expensive. + // Map the metadata and turn it into a value. auto *MappedMD = mapMetadata(MD); - if (MD == MappedMD || (!MappedMD && (Flags & RF_IgnoreMissingLocals))) + if (MD == MappedMD) return VM[V] = const_cast(V); - return VM[V] = MetadataAsValue::get(V->getContext(), MappedMD); } @@ -623,21 +651,16 @@ Optional Mapper::mapSimpleMetadata(const Metadata *MD) { if (isa(MD)) return mapToSelf(MD); - if (isa(MD)) + if (auto *CMD = dyn_cast(MD)) { if ((Flags & RF_NoModuleLevelChanges)) return mapToSelf(MD); - // FIXME: Assert that this is not LocalAsMetadata. It should be handled - // elsewhere. - if (const auto *VMD = dyn_cast(MD)) { // Disallow recursion into metadata mapping through mapValue. VM.disableMapMetadata(); - Value *MappedV = mapValue(VMD->getValue()); + Value *MappedV = mapValue(CMD->getValue()); VM.enableMapMetadata(); - // FIXME: Always use "ignore" behaviour. There should only be globals here. - if (VMD->getValue() == MappedV || - (!MappedV && (Flags & RF_IgnoreMissingLocals))) + if (CMD->getValue() == MappedV) return mapToSelf(MD); return mapToMetadata(MD, MappedV ? ValueAsMetadata::get(MappedV) : nullptr); @@ -659,9 +682,26 @@ Metadata *llvm::MapMetadata(const Metadata *MD, ValueToValueMapTy &VM, return Mapper(VM, Flags, TypeMapper, Materializer).mapMetadata(MD); } +Metadata *Mapper::mapLocalAsMetadata(const LocalAsMetadata &LAM) { + // Lookup the mapping for the value itself, and return the appropriate + // metadata. + if (Value *V = mapValue(LAM.getValue())) { + if (V == LAM.getValue()) + return const_cast(&LAM); + return ValueAsMetadata::get(V); + } + + // FIXME: always return nullptr once Verifier::verifyDominatesUse() ensures + // metadata operands only reference defined SSA values. + return (Flags & RF_IgnoreMissingLocals) + ? nullptr + : MDTuple::get(LAM.getContext(), None); +} + Metadata *Mapper::mapMetadata(const Metadata *MD) { - // FIXME: First check for and deal with LocalAsMetadata, so that - // mapSimpleMetadata() doesn't need to deal with it. + assert(MD && "Expected valid metadata"); + assert(!isa(MD) && "Unexpected local metadata"); + if (Optional NewMD = mapSimpleMetadata(MD)) return *NewMD; diff --git a/llvm/test/Transforms/Inline/local-as-metadata-undominated-use.ll b/llvm/test/Transforms/Inline/local-as-metadata-undominated-use.ll new file mode 100644 index 0000000..5182e21 --- /dev/null +++ b/llvm/test/Transforms/Inline/local-as-metadata-undominated-use.ll @@ -0,0 +1,49 @@ +; RUN: opt -inline -S < %s | FileCheck %s + +; Make sure the inliner doesn't crash when a metadata-bridged SSA operand is an +; undominated use. +; +; If we ever add a verifier check to prevent the scenario in this file, it's +; fine to delete this testcase. However, we would need a bitcode upgrade since +; such historical IR exists in practice. + +define i32 @foo(i32 %i) !dbg !4 { +entry: + tail call void @llvm.dbg.value(metadata i32 %add, i64 0, metadata !8, metadata !10), !dbg !11 + %add = add nsw i32 1, %i, !dbg !12 + ret i32 %add, !dbg !13 +} + +; CHECK-LABEL: define i32 @caller( +define i32 @caller(i32 %i) { +; CHECK-NEXT: entry: +entry: +; Although the inliner shouldn't crash, it can't be expected to get the +; "correct" SSA value since its assumptions have been violated. +; CHECK-NEXT: tail call void @llvm.dbg.value(metadata ![[EMPTY:[0-9]+]], +; CHECK-NEXT: %{{.*}} = add nsw + %call = tail call i32 @foo(i32 %i) + ret i32 %call +} + +declare void @llvm.dbg.value(metadata, i64, metadata, metadata) + +!llvm.dbg.cu = !{!0} +!llvm.module.flags = !{!9} + +!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.9.0 (trunk 265634) (llvm/trunk 265637)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, subprograms: !3) +!1 = !DIFile(filename: "t.c", directory: "/path/to/tests") + +; CHECK: ![[EMPTY]] = !{} +!2 = !{} +!3 = !{!4} +!4 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 2, type: !5, isLocal: false, isDefinition: true, scopeLine: 2, flags: DIFlagPrototyped, isOptimized: true) +!5 = !DISubroutineType(types: !6) +!6 = !{!7, !7} +!7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed) +!8 = !DILocalVariable(name: "add", arg: 1, scope: !4, file: !1, line: 2, type: !7) +!9 = !{i32 2, !"Debug Info Version", i32 3} +!10 = !DIExpression() +!11 = !DILocation(line: 2, column: 13, scope: !4) +!12 = !DILocation(line: 2, column: 27, scope: !4) +!13 = !DILocation(line: 2, column: 18, scope: !4) diff --git a/llvm/unittests/Transforms/Utils/ValueMapperTest.cpp b/llvm/unittests/Transforms/Utils/ValueMapperTest.cpp index 222f2a2..151f76d 100644 --- a/llvm/unittests/Transforms/Utils/ValueMapperTest.cpp +++ b/llvm/unittests/Transforms/Utils/ValueMapperTest.cpp @@ -139,4 +139,99 @@ TEST(ValueMapperTest, MapMetadataNullMapGlobalWithIgnoreMissingLocals) { EXPECT_EQ(nullptr, MapValue(F.get(), VM, Flags)); } +TEST(ValueMapperTest, MapMetadataConstantAsMetadata) { + LLVMContext C; + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(C), Type::getInt8Ty(C), false); + std::unique_ptr F( + Function::Create(FTy, GlobalValue::ExternalLinkage, "F")); + + auto *CAM = ConstantAsMetadata::get(F.get()); + { + ValueToValueMapTy VM; + EXPECT_EQ(CAM, MapMetadata(CAM, VM)); + EXPECT_TRUE(VM.MD().count(CAM)); + VM.MD().erase(CAM); + EXPECT_EQ(CAM, MapMetadata(CAM, VM, RF_IgnoreMissingLocals)); + EXPECT_TRUE(VM.MD().count(CAM)); + + auto *N = MDTuple::get(C, None); + VM.MD()[CAM].reset(N); + EXPECT_EQ(N, MapMetadata(CAM, VM)); + EXPECT_EQ(N, MapMetadata(CAM, VM, RF_IgnoreMissingLocals)); + } + + std::unique_ptr F2( + Function::Create(FTy, GlobalValue::ExternalLinkage, "F2")); + ValueToValueMapTy VM; + VM[F.get()] = F2.get(); + auto *F2MD = MapMetadata(CAM, VM); + EXPECT_TRUE(VM.MD().count(CAM)); + EXPECT_TRUE(F2MD); + EXPECT_EQ(F2.get(), cast(F2MD)->getValue()); +} + +#ifdef GTEST_HAS_DEATH_TEST +#ifndef NDEBUG +TEST(ValueMapperTest, MapMetadataLocalAsMetadata) { + LLVMContext C; + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(C), Type::getInt8Ty(C), false); + std::unique_ptr F( + Function::Create(FTy, GlobalValue::ExternalLinkage, "F")); + Argument &A = *F->arg_begin(); + + // MapMetadata doesn't support LocalAsMetadata. The only valid container for + // LocalAsMetadata is a MetadataAsValue instance, so use it directly. + auto *LAM = LocalAsMetadata::get(&A); + ValueToValueMapTy VM; + EXPECT_DEATH(MapMetadata(LAM, VM), "Unexpected local metadata"); + EXPECT_DEATH(MapMetadata(LAM, VM, RF_IgnoreMissingLocals), + "Unexpected local metadata"); +} +#endif +#endif + +TEST(ValueMapperTest, MapValueLocalAsMetadata) { + LLVMContext C; + FunctionType *FTy = + FunctionType::get(Type::getVoidTy(C), Type::getInt8Ty(C), false); + std::unique_ptr F( + Function::Create(FTy, GlobalValue::ExternalLinkage, "F")); + Argument &A = *F->arg_begin(); + + auto *LAM = LocalAsMetadata::get(&A); + auto *MAV = MetadataAsValue::get(C, LAM); + + // The principled answer to a LocalAsMetadata of an unmapped SSA value would + // be to return nullptr (regardless of RF_IgnoreMissingLocals). + // + // However, algorithms that use RemapInstruction assume that each instruction + // only references SSA values from previous instructions. Arguments of + // such as "metadata i32 %x" don't currently successfully maintain that + // property. To keep RemapInstruction from crashing we need a non-null + // return here, but we also shouldn't reference the unmapped local. Use + // "metadata !{}". + auto *N0 = MDTuple::get(C, None); + auto *N0AV = MetadataAsValue::get(C, N0); + ValueToValueMapTy VM; + EXPECT_EQ(N0AV, MapValue(MAV, VM)); + EXPECT_EQ(nullptr, MapValue(MAV, VM, RF_IgnoreMissingLocals)); + EXPECT_FALSE(VM.count(MAV)); + EXPECT_FALSE(VM.count(&A)); + EXPECT_EQ(None, VM.getMappedMD(LAM)); + + VM[MAV] = MAV; + EXPECT_EQ(MAV, MapValue(MAV, VM)); + EXPECT_EQ(MAV, MapValue(MAV, VM, RF_IgnoreMissingLocals)); + EXPECT_TRUE(VM.count(MAV)); + EXPECT_FALSE(VM.count(&A)); + + VM[MAV] = &A; + EXPECT_EQ(&A, MapValue(MAV, VM)); + EXPECT_EQ(&A, MapValue(MAV, VM, RF_IgnoreMissingLocals)); + EXPECT_TRUE(VM.count(MAV)); + EXPECT_FALSE(VM.count(&A)); +} + } // end namespace -- 2.7.4