[Bugpoint redesign] Added pass to reduce Basic Blocks

[diegotf]

Summary

This pass tries to remove uninteresting Basic Blocks. Note: it also removes them from any SwInst, BranchInst and IndirectBrInst that references them.

[diegotf]

Added test & fixed a bug where SwitchInst were not being replaced

[hctim]

Looks like this broke the sanitizer buildbots - I'll confirm that a revert fixes and will follow up with it:

FAIL: LLVM :: Reduce/remove-bbs.ll (25951 of 33613)
******************** TEST 'LLVM :: Reduce/remove-bbs.ll' FAILED ********************
Script:
--
: 'RUN: at line 4';   llvm-reduce --test "/usr/bin/python" --test-arg /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/Reduce/Inputs/remove-bbs.py /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/Reduce/remove-bbs.ll -o /b/sanitizer-x86_64-linux-fast/build/llvm_build_msan/test/Reduce/Output/remove-bbs.ll.tmp
: 'RUN: at line 5';   cat /b/sanitizer-x86_64-linux-fast/build/llvm_build_msan/test/Reduce/Output/remove-bbs.ll.tmp | /b/sanitizer-x86_64-linux-fast/build/llvm_build_msan/bin/FileCheck -implicit-check-not=uninteresting /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/Reduce/remove-bbs.ll
--
Exit Code: 77

Command Output (stderr):
--
*** Reducing Functions...
----------------------------
Function Index Reference:
	1: main
----------------------------
Increasing granularity...
Already at minimum size. Cannot reduce anymore.
----------------------------
Increasing granularity...Success! New Chunks:
	[1,2]
	[3,4]
==2672==WARNING: MemorySanitizer: use-of-uninitialized-value
    #0 0x4d69bb in replaceBranchTerminator /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp:54:12
    #1 0x4d69bb in extractBasicBlocksFromModule(std::__1::vector<llvm::Chunk, std::__1::allocator<llvm::Chunk> >, llvm::Module*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp:114
    #2 0x4c61c9 in __invoke<void (*&)(std::__1::vector<llvm::Chunk, std::__1::allocator<llvm::Chunk> >, llvm::Module *), const std::__1::vector<llvm::Chunk, std::__1::allocator<llvm::Chunk> > &, llvm::Module *> /b/sanitizer-x86_64-linux-fast/build/libcxx_build_msan/include/c++/v1/type_traits:3501:1
    #3 0x4c61c9 in void std::__1::__invoke_void_return_wrapper<void>::__call<void (*&)(std::__1::vector<llvm::Chunk, std::__1::allocator<llvm::Chunk> >, llvm::Module*), std::__1::vector<llvm::Chunk, std::__1::allocator<llvm::Chunk> > const&, llvm::Module*>(void (*&)(std::__1::vector<llvm::Chunk, std::__1::allocator<llvm::Chunk> >, llvm::Module*), std::__1::vector<llvm::Chunk, std::__1::allocator<llvm::Chunk> > const&, llvm::Module*&&) /b/sanitizer-x86_64-linux-fast/build/libcxx_build_msan/include/c++/v1/__functional_base:348
    #4 0x4b7607 in operator() /b/sanitizer-x86_64-linux-fast/build/libcxx_build_msan/include/c++/v1/functional:1867:16
    #5 0x4b7607 in operator() /b/sanitizer-x86_64-linux-fast/build/libcxx_build_msan/include/c++/v1/functional:2473
    #6 0x4b7607 in llvm::runDeltaPass(llvm::TestRunner&, int, std::__1::function<void (std::__1::vector<llvm::Chunk, std::__1::allocator<llvm::Chunk> > const&, llvm::Module*)>) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llvm-reduce/deltas/Delta.cpp:132
    #7 0x4d4170 in llvm::reduceBasicBlocksDeltaPass(llvm::TestRunner&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp:145:3
    #8 0x4ad562 in runDeltaPasses /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llvm-reduce/DeltaManager.h:28:3
    #9 0x4ad562 in main /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llvm-reduce/llvm-reduce.cpp:88
    #10 0x7f9ec536f2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #11 0x436ef9 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_msan/bin/llvm-reduce+0x436ef9)

SUMMARY: MemorySanitizer: use-of-uninitialized-value /b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp:54:12 in replaceBranchTerminator

llvm/test/Reduce/Inputs/remove-bbs.py

+#!/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

llvm/test/Reduce/remove-bbs.ll

+; 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
+}

llvm/tools/llvm-reduce/CMakeLists.txt

add_llvm_tool(llvm-reduce
   llvm-reduce.cpp
   TestRunner.cpp
   deltas/Delta.cpp
   deltas/ReduceFunctions.cpp
   deltas/ReduceGlobalVars.cpp
   deltas/ReduceMetadata.cpp
   deltas/ReduceArguments.cpp
   deltas/ReduceInstructions.cpp
+  deltas/ReduceBasicBlocks.cpp
 
   DEPENDS
   intrinsics_gen
   )
 export_executable_symbols(llvm-reduce)

llvm/tools/llvm-reduce/DeltaManager.h

 //===- DeltaManager.h - Runs Delta Passes to reduce Input -----------------===//
 //
 // 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 calls each specialized Delta pass in order to reduce the input IR
 // file.
 //
 //===----------------------------------------------------------------------===//
 
 #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

llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.h

+//===- 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

llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp

+//===- 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 <vector>
+
+/// Replaces BB Terminator with one that only contains Chunk BBs
+static void replaceBranchTerminator(BasicBlock *BB,
+                                    std::set<BasicBlock *> BBsToKeep) {
+  auto Term = BB->getTerminator();
+  std::vector<BasicBlock *> 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<BranchInst>(Term))
+    BranchInst::Create(ChunkSucessors[0], BB);
+
+  if (auto IndBI = dyn_cast<IndirectBrInst>(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<BasicBlock *> 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<Chunk> ChunksToKeep,
+                                         Module *Program) {
+  unsigned I = 0, BBCount = 0;
+  std::set<BasicBlock *> 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<BasicBlock *> 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<SwitchInst>(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);
+}