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,12 @@ +#!/usr/bin/env python + +import sys + +NamedNodePresent = False + +input = open(sys.argv[1], "r") +for line in input: + if "!interesting" in line: + sys.exit(0) + +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,23 @@ +; 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: !dbg +@global = global i32 0, !dbg !0 + +define void @main() !dbg !0 { + ret void, !dbg !0 +} + +; CHECK-NOT: !uninteresting +!uninteresting = !{!0} +; CHECK: !interesting +!interesting = !{!1} + +!0 = !{!"dropped"} +; CHECK: !"kept" +!1 = !{!"kept"} +; CHECK-NOT: ! 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"; +}