diff --git a/llvm/test/Reduce/Inputs/remove-bbs.py b/llvm/test/Reduce/Inputs/remove-bbs.py new file mode 100755 --- /dev/null +++ b/llvm/test/Reduce/Inputs/remove-bbs.py @@ -0,0 +1,17 @@ +#!/usr/bin/env python + +import sys +import re + +InterestingBBs = 0 +input = open(sys.argv[1], "r") +for line in input: + if '; CHECK' in line: + continue + elif re.search(r"^interesting:*", line) or "%interesting" in line: + InterestingBBs += 1 + +if InterestingBBs == 6: + 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,29 @@ +; Test that llvm-reduce can remove uninteresting Basic Blocks, and remove them from instructions (i.e. SwitchInst, BranchInst and IndirectBrInst) +; Note: if an uninteresting BB is the default case for a switch, the instruction is removed altogether (since the default case cannot be replaced) +; +; RUN: llvm-reduce --test %p/Inputs/remove-bbs.py %s -o - | FileCheck %s +; REQUIRES: plugins + +define void @main() { +interesting: + ; CHECK-NOT: switch i32 0, label %uninteresting + switch i32 0, label %uninteresting [ + i32 0, label %uninteresting + ] + +uninteresting: + ret void + +interesting2: + ; CHECK: switch i32 1, label %interesting3 + switch i32 1, label %interesting3 [ + ; CHECK-NOT: i32 0, label %uninteresting + i32 0, label %uninteresting + ; CHECK: i32 1, label %interesting3 + i32 1, label %interesting3 + ] + +interesting3: + ; CHECK: br label %interesting2 + br i1 true, label %interesting2, label %uninteresting +} 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,140 @@ +//===- 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/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/LLVMContext.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 replaceBranchTerminator(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); + + // BB only references Chunk BBs + if (ChunkSucessors.size() == Term->getNumSuccessors()) + return; + + Term->eraseFromParent(); + + if (ChunkSucessors.empty()) { + ReturnInst::Create(BB->getContext(), nullptr, BB); + 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 uninteresting BBs from switch, if the default case ends up being +/// uninteresting, the switch is replaced with a void return (since it has to be +/// replace with something) +static void removeUninterestingBBsFromSwitch(SwitchInst *SwInst, + std::set BBsToKeep) { + if (!BBsToKeep.count(SwInst->getDefaultDest())) { + ReturnInst::Create(SwInst->getContext(), nullptr, SwInst->getParent()); + SwInst->eraseFromParent(); + } 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; + } + } +} + +/// 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) { + if (auto SwInst = dyn_cast(BB.getTerminator())) + removeUninterestingBBsFromSwitch(SwInst, BBsToKeep); + else + replaceBranchTerminator(&BB, BBsToKeep); + } + + // Replace out-of-chunk switch uses + for (auto &BB : BBsToDelete) { + // 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); +}