diff --git a/llvm/test/Reduce/Inputs/remove-bbs.py b/llvm/test/Reduce/Inputs/remove-bbs.py new file mode 100644 --- /dev/null +++ b/llvm/test/Reduce/Inputs/remove-bbs.py @@ -0,0 +1,14 @@ +#!/usr/bin/env python + +import sys + +InterestingBBs = 0 +input = open(sys.argv[1], "r") +for line in input: + if "interesting:" in line and ';' not in line: + InterestingBBs += 1 + +if InterestingBBs == 3: + sys.exit(0) # interesting! +else: + sys.exit(1) # IR isn't interesting diff --git a/llvm/test/Reduce/remove-bbs.ll b/llvm/test/Reduce/remove-bbs.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Reduce/remove-bbs.ll @@ -0,0 +1,11 @@ +; Test that llvm-reduce can remove uninteresting Basic Blocks, and remove them from any Instruction that calls them (i.e. SwitchInst and BB Terminators) +; +; RUN: llvm-reduce --test %p/Inputs/remove-bbs.py %s -o - | FileCheck %s +; REQUIRES: plugins + +define i32 @main() { +uninteresting: + %call2 = call i32 @interesting() + %call = call i32 @uninteresting1() + ret i32 5 +} 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 @@ -22,6 +22,7 @@ deltas/ReduceMetadata.cpp deltas/ReduceArguments.cpp deltas/ReduceInstructions.cpp + deltas/ReduceBasicBlocks.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 @@ -14,21 +14,22 @@ #include "TestRunner.h" #include "deltas/Delta.h" #include "deltas/ReduceArguments.h" +#include "deltas/ReduceBasicBlocks.h" #include "deltas/ReduceFunctions.h" #include "deltas/ReduceGlobalVars.h" -#include "deltas/ReduceMetadata.h" #include "deltas/ReduceInstructions.h" +#include "deltas/ReduceMetadata.h" namespace llvm { // TODO: Add CLI option to run only specified Passes (for unit tests) inline void runDeltaPasses(TestRunner &Tester) { reduceFunctionsDeltaPass(Tester); + reduceBasicBlocksDeltaPass(Tester); reduceGlobalsDeltaPass(Tester); reduceMetadataDeltaPass(Tester); reduceArgumentsDeltaPass(Tester); reduceInstructionsDeltaPass(Tester); - // TODO: Implement the remaining Delta Passes } } // namespace llvm diff --git a/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.h b/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.h new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.h @@ -0,0 +1,20 @@ +//===- ReduceArguments.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 a function which calls the Generic Delta pass in order +// to reduce uninteresting Arguments from defined functions. +// +//===----------------------------------------------------------------------===// + +#include "Delta.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Cloning.h" + +namespace llvm { +void reduceBasicBlocksDeltaPass(TestRunner &Test); +} // namespace llvm diff --git a/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp b/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp new file mode 100644 --- /dev/null +++ b/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp @@ -0,0 +1,130 @@ +//===- ReduceArguments.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 a function which calls the Generic Delta pass in order +// to reduce uninteresting Arguments from defined functions. +// +//===----------------------------------------------------------------------===// + +#include "ReduceBasicBlocks.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Value.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/raw_ostream.h" +#include + +/// Replaces BB Terminator with one that only contains Chunk BBs +static void replaceTerminator(BasicBlock *BB, + std::set BBsToKeep) { + auto Term = BB->getTerminator(); + std::vector ChunkSucessors; + for (auto Succ : successors(BB)) + if (BBsToKeep.count(Succ)) + ChunkSucessors.push_back(Succ); + + if (ChunkSucessors.size() == Term->getNumSuccessors()) + return; + + Term->eraseFromParent(); + + // No need to replace terminator + if (ChunkSucessors.empty()) + return; + + if (isa(Term)) + BranchInst::Create(ChunkSucessors[0], BB); + + if (auto IndBI = dyn_cast(Term)) { + auto NewIndBI = IndirectBrInst::Create(IndBI->getAddress(), + ChunkSucessors.size(), BB); + for (auto Dest : ChunkSucessors) + NewIndBI->addDestination(Dest); + } +} + +/// Removes out-of-chunk arguments from functions, and modifies their calls +/// accordingly. It also removes allocations of out-of-chunk arguments. +/// @returns the Module stripped of out-of-chunk functions +static void extractBasicBlocksFromModule(std::vector ChunksToKeep, + Module *Program) { + unsigned I = 0, BBCount = 0; + std::set BBsToKeep; + + for (auto &F : *Program) + for (auto &BB : F) + if (I < ChunksToKeep.size()) { + if (ChunksToKeep[I].contains(++BBCount)) + BBsToKeep.insert(&BB); + if (ChunksToKeep[I].end == BBCount) + ++I; + } + + std::vector BBsToDelete; + for (auto &F : *Program) + for (auto &BB : F) { + if (!BBsToKeep.count(&BB)) { + BBsToDelete.push_back(&BB); + // Remove out-of-chunk BB from successor phi nodes + for (auto Succ : successors(&BB)) + Succ->removePredecessor(&BB); + } + } + + // Replace terminators that reference out-of-chunk BBs + for (auto &F : *Program) + for (auto &BB : F) + replaceTerminator(&BB, BBsToKeep); + + // Replace out-of-chunk switch uses + for (auto &BB : BBsToDelete) { + for (auto U : BB->users()) + if (auto *SwInst = dyn_cast(U)) { + // Cant replace default case, so delete switch + if (!BBsToKeep.count(SwInst->getDefaultDest())) + SwInst->eraseFromParent(); + // Remove switch cases that refer out-of-chunk BBs + else { + for (int I = 0, E = SwInst->getNumCases(); I != E; ++I) { + auto Case = SwInst->case_begin() + I; + if (!BBsToKeep.count(Case->getCaseSuccessor())) { + SwInst->removeCase(Case); + --I; + --E; + } + } + } + } + // Instructions might be referenced in other BBs + for (auto &I : *BB) + I.replaceAllUsesWith(UndefValue::get(I.getType())); + BB->eraseFromParent(); + } +} + +/// Counts the amount of basic blocks and prints their name & respective index +static unsigned countBasicBlocks(Module *Program) { + // TODO: Silence index with --quiet flag + outs() << "----------------------------\n"; + int BBCount = 0; + for (auto &F : *Program) + for (auto &BB : F) { + if (BB.hasName()) + outs() << "\t" << ++BBCount << ": " << BB.getName() << "\n"; + else + outs() << "\t" << ++BBCount << ": Unnamed\n"; + } + + return BBCount; +} + +void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) { + outs() << "*** Reducing Basic Blocks...\n"; + unsigned BBCount = countBasicBlocks(Test.getProgram()); + runDeltaPass(Test, BBCount, extractBasicBlocksFromModule); +}