diff --git a/llvm/test/Reduce/Inputs/remove-metadata.py b/llvm/test/Reduce/Inputs/remove-metadata.py new file mode 100755 --- /dev/null +++ b/llvm/test/Reduce/Inputs/remove-metadata.py @@ -0,0 +1,18 @@ +#!/usr/bin/env python + +import sys + +NamedNodePresent = False +DebugFunctionPresent = False + +input = open(sys.argv[1], "r") +for line in input: + if "!llvm.module.flags" in line: + NamedNodePresent = True + if "@llvm.dbg.interesting" in line: + DebugFunctionPresent = True + +if NamedNodePresent and DebugFunctionPresent: + sys.exit(0) # interesting! +else: + sys.exit(1) diff --git a/llvm/test/Reduce/remove-metadata.ll b/llvm/test/Reduce/remove-metadata.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Reduce/remove-metadata.ll @@ -0,0 +1,55 @@ +; Test that llvm-reduce can remove uninteresting metadata from an IR file. +; The Metadata pass erases named & unnamed metadata nodes, as well as debug functions. +; +; RUN: llvm-reduce --test %p/Inputs/remove-metadata.py %s +; RUN: cat reduced.ll | FileCheck %s +; REQUIRES: plugins + +; CHECK: @llvm.dbg.interesting +declare void @llvm.dbg.interesting(metadata %0, metadata %1, metadata %2) +declare void @llvm.dbg.uninteresting(metadata %0, metadata %1, metadata %2) + +; CHECK-NOT: !dbg +@x = dso_local global i32 0, align 4, !dbg !0 + +define dso_local i32 @main() !dbg !13 { +entry: + %retval = alloca i32, align 4 + store i32 0, i32* %retval, align 4 + store i32 10, i32* @x, align 4, !dbg !16 + %0 = load i32, i32* @x, align 4, !dbg !17 + %sub = sub nsw i32 %0, 5, !dbg !18 + %1 = load i32, i32* @x, align 4, !dbg !19 + ret i32 0, !dbg !20 +} + +; CHECK: !llvm.module.flags +; CHECK-NOT: !llvm. +!llvm.dbg.cu = !{!2} +!llvm.module.flags = !{!9, !10, !11} +!llvm.ident = !{!12} + +; Since we're only keeping !llvm.module.flags, there should only be 3 unnamed +; nodes, and due to numbering !3 should not exist. +; CHECK-NOT: !3 +!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression()) +!1 = distinct !DIGlobalVariable(name: "x", scope: !2, file: !3, line: 3, type: !8, isLocal: false, isDefinition: true) +!2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !3, producer: "clang version 9.0.0 (https://github.com/llvm/llvm-project.git ff0a72129a3e97bf7fddca38688808cd4f4e8f7b)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5, nameTableKind: None) +!3 = !DIFile(filename: "ints.cpp", directory: "") +!4 = !{} +!5 = !{!0, !6} +!6 = !DIGlobalVariableExpression(var: !7, expr: !DIExpression()) +!7 = distinct !DIGlobalVariable(name: "y", scope: !2, file: !3, line: 4, type: !8, isLocal: false, isDefinition: true) +!8 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) +!9 = !{i32 2, !"Dwarf Version", i32 4} +!10 = !{i32 2, !"Debug Info Version", i32 3} +!11 = !{i32 1, !"wchar_size", i32 4} +!12 = !{!"clang version 9.0.0 (https://github.com/llvm/llvm-project.git ff0a72129a3e97bf7fddca38688808cd4f4e8f7b)"} +!13 = distinct !DISubprogram(name: "main", scope: !3, file: !3, line: 10, type: !14, scopeLine: 10, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !2, retainedNodes: !4) +!14 = !DISubroutineType(types: !15) +!15 = !{!8} +!16 = !DILocation(line: 11, column: 5, scope: !13) +!17 = !DILocation(line: 12, column: 7, scope: !13) +!18 = !DILocation(line: 12, column: 9, scope: !13) +!19 = !DILocation(line: 13, column: 18, scope: !13) +!20 = !DILocation(line: 14, column: 3, scope: !13) diff --git a/llvm/tools/llvm-reduce/CMakeLists.txt b/llvm/tools/llvm-reduce/CMakeLists.txt --- a/llvm/tools/llvm-reduce/CMakeLists.txt +++ b/llvm/tools/llvm-reduce/CMakeLists.txt @@ -18,6 +18,7 @@ deltas/Delta.cpp deltas/ReduceFunctions.cpp deltas/ReduceGlobalVars.cpp + deltas/ReduceMetadata.cpp DEPENDS intrinsics_gen diff --git a/llvm/tools/llvm-reduce/DeltaManager.h b/llvm/tools/llvm-reduce/DeltaManager.h --- a/llvm/tools/llvm-reduce/DeltaManager.h +++ b/llvm/tools/llvm-reduce/DeltaManager.h @@ -15,15 +15,15 @@ #include "deltas/Delta.h" #include "deltas/ReduceFunctions.h" #include "deltas/ReduceGlobalVars.h" +#include "deltas/ReduceMetadata.h" namespace llvm { // TODO: Add CLI option to run only specified Passes (for unit tests) inline void runDeltaPasses(TestRunner &Tester) { - outs() << "Reducing functions...\n"; reduceFunctionsDeltaPass(Tester); - outs() << "Reducing GVs...\n"; reduceGlobalsDeltaPass(Tester); + reduceMetadataDeltaPass(Tester); // TODO: Implement the remaining Delta Passes } diff --git a/llvm/tools/llvm-reduce/deltas/ReduceMetadata.h b/llvm/tools/llvm-reduce/deltas/ReduceMetadata.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceMetadata.h @@ -0,0 +1,24 @@ +//===- ReduceMetadata.h - Specialized Delta Pass ------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements two functions used by the Generic Delta Debugging +// Algorithm, which are used to reduce Metadata tags, as well as debug +// functions. +// +//===----------------------------------------------------------------------===// + +#include "Delta.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Value.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include +#include + +namespace llvm { +void reduceMetadataDeltaPass(TestRunner &Test); +} // namespace llvm diff --git a/llvm/tools/llvm-reduce/deltas/ReduceMetadata.cpp b/llvm/tools/llvm-reduce/deltas/ReduceMetadata.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceMetadata.cpp @@ -0,0 +1,166 @@ +//===- ReduceMetadata.cpp - Specialized Delta Pass ------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements two functions used by the Generic Delta Debugging +// Algorithm, which are used to reduce Metadata tags, as well as debug +// functions. +// +//===----------------------------------------------------------------------===// + +#include "ReduceMetadata.h" + +/// Adds all Unnamed Metadata Nodes that are inside desired Chunks to set +template +static void getChunkMetadataNodes(T *MDUser, unsigned &I, + const std::vector &ChunksToKeep, + std::set &SeenNodes, + std::set &NodesToKeep) { + SmallVector, 4> MDs; + MDUser->getAllMetadata(MDs); + for (auto &MD : MDs) { + SeenNodes.insert(MD.second); + if (I < ChunksToKeep.size()) { + if (ChunksToKeep[I].contains(SeenNodes.size())) + NodesToKeep.insert(MD.second); + if (ChunksToKeep[I].end == SeenNodes.size()) + ++I; + } + } +} + +/// Erases out-of-chunk unnamed metadata nodes from its user +template +static void eraseMetadataIfOutsideChunk(T *MDUser, + const std::set &NodesToKeep) { + SmallVector, 4> MDs; + MDUser->getAllMetadata(MDs); + for (int I = 0, E = MDs.size(); I != E; ++I) + if (!NodesToKeep.count(MDs[I].second)) + MDUser->setMetadata(I, NULL); +} + +/// Erases function and its instruction users. It also replaces the latter with +/// "undef" +static void deleteFunctionAndCallers(Function *F) { + for (auto U : F->users()) { + U->replaceAllUsesWith(UndefValue::get(U->getType())); + if (auto *Inst = dyn_cast(U)) + Inst->eraseFromParent(); + } + F->eraseFromParent(); +} + +/// Removes all the Named and Unnamed Metadata Nodes, as well as any debug +/// functions that aren't inside the desired Chunks. +/// @returns the Module stripped of out-of-chunk MDNodes +static void extractMetadataFromModule(const std::vector &ChunksToKeep, + Module *Program) { + std::set SeenNodes; + std::set NodesToKeep; + unsigned I = 0; + + // Add chunk MDNodes used by GVs, Functions, and Instructions to set + for (auto &GV : Program->globals()) + getChunkMetadataNodes(&GV, I, ChunksToKeep, SeenNodes, NodesToKeep); + + for (auto &F : *Program) { + getChunkMetadataNodes(&F, I, ChunksToKeep, SeenNodes, NodesToKeep); + for (auto &BB : F) + for (auto &Inst : BB) + getChunkMetadataNodes(&Inst, I, ChunksToKeep, SeenNodes, NodesToKeep); + } + + // Once more, go over metadata nodes, but deleting the ones outside chunks + for (auto &GV : Program->globals()) + eraseMetadataIfOutsideChunk(&GV, NodesToKeep); + + // And keeping a list of debug functions + std::vector DebugFuncs; + for (auto &F : *Program) { + if (F.getName().startswith("llvm.")) + DebugFuncs.push_back(&F); + else + eraseMetadataIfOutsideChunk(&F, NodesToKeep); + for (auto &BB : F) + for (auto &Inst : BB) + eraseMetadataIfOutsideChunk(&Inst, NodesToKeep); + } + + // Go over debug functions and erase the ones out-of-chunk + unsigned MetadataCount = SeenNodes.size(); + for (auto F : DebugFuncs) { + if (I < ChunksToKeep.size()) { + if (!ChunksToKeep[I].contains(++MetadataCount)) + deleteFunctionAndCallers(F); + if (ChunksToKeep[I].end == MetadataCount) + ++I; + } else + deleteFunctionAndCallers(F); + } + + std::vector NamedNodesToDelete; + + // Get out-of-chunk Named metadata nodes + for (auto &MD : Program->named_metadata()) { + ++MetadataCount; + if (I < ChunksToKeep.size()) { + if (!ChunksToKeep[I].contains(MetadataCount)) + NamedNodesToDelete.push_back(&MD); + if (ChunksToKeep[I].end == SeenNodes.size()) + ++I; + } else + NamedNodesToDelete.push_back(&MD); + } + + for (auto NN : NamedNodesToDelete) { + for (int I = 0, E = NN->getNumOperands(); I != E; ++I) + NN->setOperand(I, NULL); + NN->eraseFromParent(); + } +} + +// Gets unnamed metadata nodes used by a given instruction/GV/function and adds +// them to the set of seen nodes +template +static void addMetadataToSet(T *MDUser, std::set &UnnamedNodes) { + SmallVector, 4> MDs; + MDUser->getAllMetadata(MDs); + for (auto &MD : MDs) + UnnamedNodes.insert(MD.second); +} + +/// Returns the amount of Named and Unnamed Metadata Nodes, and Debug functions +/// used in the module +static unsigned countMetadataTargets(Module *Program) { + std::set UnnamedNodes; + int NamedMetadataNodes = Program->named_metadata_size(); + int DebugFunctionsCount = 0; + + // Get metadata nodes used by globals + for (auto &GV : Program->globals()) + addMetadataToSet(&GV, UnnamedNodes); + + // Do the same for nodes used by functions & instructions + for (auto &F : *Program) { + if (F.getName().startswith("llvm.")) + ++DebugFunctionsCount; + addMetadataToSet(&F, UnnamedNodes); + for (auto &BB : F) + for (auto &I : BB) + addMetadataToSet(&I, UnnamedNodes); + } + + return UnnamedNodes.size() + NamedMetadataNodes + DebugFunctionsCount; +} + +void llvm::reduceMetadataDeltaPass(TestRunner &Test) { + outs() << "*** Reducing Metadata...\n"; + unsigned MDCount = countMetadataTargets(Test.getProgram()); + runDeltaPass(Test, MDCount, extractMetadataFromModule); + outs() << "----------------------------\n"; +}