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,24 @@ +; Test that llvm-reduce can remove uninteresting metadata from an IR file. +; The Metadata pass erases named & unnamed metadata nodes. +; +; RUN: llvm-reduce --test %p/Inputs/remove-metadata.py %s +; RUN: cat reduced.ll | FileCheck %s +; REQUIRES: plugins + +; CHECK-NOT: !llvm.dbg.cu +!llvm.dbg.cu = !{!0} +; CHECK: !llvm.module.flags +!llvm.module.flags = !{!3, !4, !5} +; CHECK-NOT: !llvm.ident +!llvm.ident = !{!6} + +; 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 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 9.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, globals: !2, nameTableKind: None) +!1 = !DIFile(filename: "ints.cpp", directory: "") +!2 = !{} +!3 = !{i32 2, !"Dwarf Version", i32 4} +!4 = !{i32 2, !"Debug Info Version", i32 3} +!5 = !{i32 1, !"wchar_size", i32 4} +!6 = !{!"clang version 9.0.0"} 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 @@ -19,6 +19,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,23 @@ +//===- 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 nodes. +// +//===----------------------------------------------------------------------===// + +#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,133 @@ +//===- 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 nodes. +// +//===----------------------------------------------------------------------===// + +#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); +} + +/// 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); + + for (auto &F : *Program) { + eraseMetadataIfOutsideChunk(&F, NodesToKeep); + for (auto &BB : F) + for (auto &Inst : BB) + eraseMetadataIfOutsideChunk(&Inst, NodesToKeep); + } + + + // Get out-of-chunk Named metadata nodes + unsigned MetadataCount = SeenNodes.size(); + std::vector NamedNodesToDelete; + for (auto &MD : Program->named_metadata()) { + 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 +static unsigned countMetadataTargets(Module *Program) { + std::set UnnamedNodes; + int NamedMetadataNodes = Program->named_metadata_size(); + + // 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) { + addMetadataToSet(&F, UnnamedNodes); + for (auto &BB : F) + for (auto &I : BB) + addMetadataToSet(&I, UnnamedNodes); + } + + return UnnamedNodes.size() + NamedMetadataNodes; +} + +void llvm::reduceMetadataDeltaPass(TestRunner &Test) { + outs() << "*** Reducing Metadata...\n"; + unsigned MDCount = countMetadataTargets(Test.getProgram()); + runDeltaPass(Test, MDCount, extractMetadataFromModule); + outs() << "----------------------------\n"; +}