Index: llvm/trunk/test/Reduce/Inputs/remove-metadata.py =================================================================== --- llvm/trunk/test/Reduce/Inputs/remove-metadata.py +++ llvm/trunk/test/Reduce/Inputs/remove-metadata.py @@ -0,0 +1,8 @@ +import sys + +input = open(sys.argv[1], "r") +for line in input: + if "!interesting" in line: + sys.exit(0) + +sys.exit(1) Index: llvm/trunk/test/Reduce/remove-metadata.ll =================================================================== --- llvm/trunk/test/Reduce/remove-metadata.ll +++ llvm/trunk/test/Reduce/remove-metadata.ll @@ -0,0 +1,29 @@ +; Test that llvm-reduce can remove uninteresting metadata from an IR file. +; The Metadata pass erases named & unnamed metadata nodes. +; +; RUN: rm -rf %t +; RUN: mkdir %t +; copy the test file to preserve executable bit +; RUN: cp %p/Inputs/remove-metadata.py %t/test.py +; get the python path from lit +; RUN: echo "#!" %python > %t/test.py +; then include the rest of the test script +; RUN: cat %p/Inputs/remove-metadata.py >> %t/test.py + +; RUN: llvm-reduce --test %t/test.py %s -o %t/out.ll +; RUN: cat %t/out.ll | FileCheck -implicit-check-not=! %s +; REQUIRES: plugins + +@global = global i32 0, !dbg !0 + +define void @main() !dbg !0 { + ret void, !dbg !0 +} + +!uninteresting = !{!0} +; CHECK: !interesting = !{!0} +!interesting = !{!1} + +!0 = !{!"uninteresting"} +; CHECK: !0 = !{!"interesting"} +!1 = !{!"interesting"} Index: llvm/trunk/tools/llvm-reduce/CMakeLists.txt =================================================================== --- llvm/trunk/tools/llvm-reduce/CMakeLists.txt +++ llvm/trunk/tools/llvm-reduce/CMakeLists.txt @@ -19,6 +19,7 @@ deltas/Delta.cpp deltas/ReduceFunctions.cpp deltas/ReduceGlobalVars.cpp + deltas/ReduceMetadata.cpp DEPENDS intrinsics_gen Index: llvm/trunk/tools/llvm-reduce/DeltaManager.h =================================================================== --- llvm/trunk/tools/llvm-reduce/DeltaManager.h +++ llvm/trunk/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 } Index: llvm/trunk/tools/llvm-reduce/deltas/ReduceMetadata.h =================================================================== --- llvm/trunk/tools/llvm-reduce/deltas/ReduceMetadata.h +++ llvm/trunk/tools/llvm-reduce/deltas/ReduceMetadata.h @@ -0,0 +1,18 @@ +//===- 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 "TestRunner.h" + +namespace llvm { +void reduceMetadataDeltaPass(TestRunner &Test); +} // namespace llvm Index: llvm/trunk/tools/llvm-reduce/deltas/ReduceMetadata.cpp =================================================================== --- llvm/trunk/tools/llvm-reduce/deltas/ReduceMetadata.cpp +++ llvm/trunk/tools/llvm-reduce/deltas/ReduceMetadata.cpp @@ -0,0 +1,139 @@ +//===- 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" +#include "Delta.h" +#include "llvm/ADT/SmallVector.h" +#include +#include + +using namespace llvm; + +/// 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"; +}