[Bugpoint redesign] Added pass to reduce Instructions

[diegotf]

Summary

Pass reduces uninteresting instructions from input.

This diff also modified the remove-global-vars.ll test, since this Pass broke it

[diegotf]

Updated test so it pipes the reduction to FileCheck directly from STDOUT

llvm/test/Reduce/Inputs/remove-global-vars.py

 #!/usr/bin/env python
 
 import sys
 
+InterestingGlobalPresent = False
+InterestingUses = 0
+
 input = open(sys.argv[1], "r")
 for line in input:
-  if "@interesting = global" in line:
-    sys.exit(0)
+  if ';' in line:
+    continue
+  elif "@interesting = global" in line:
+    InterestingVarIsGlobal = True
+  elif "@interesting" in line or "%inc" in line:
+    InterestingUses += 1
 
-sys.exit(1) # IR isn't interesting
+if InterestingVarIsGlobal and InterestingUses == 4:
+  sys.exit(0) # interesting!
+else:
+  sys.exit(1)

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

+#!/usr/bin/env python
+
+import sys
+
+InterestingVarUses = 0
+
+input = open(sys.argv[1], "r")
+for line in input:
+  if "%x" in line and ';' not in line:
+    InterestingVarUses += 1
+
+if InterestingVarUses == 5:
+  sys.exit(0) # interesting!
+else:
+  sys.exit(1)

llvm/test/Reduce/remove-instructions.ll

+; Test that llvm-reduce can remove uninteresting instructions.
+;
+; RUN: llvm-reduce --test %p/Inputs/remove-instructions.py %s
+; RUN: cat reduced.ll | FileCheck %s
+; REQUIRES: plugins
+
+; We're testing all direct uses of %x are conserved
+; CHECK-COUNT-5: %x
+define i32 @main() #0 {
+entry:
+  ; CHECK-NOT: %retval = alloca i32, align 4
+  %retval = alloca i32, align 4
+  %x = alloca i32, align 4
+  ; CHECK-NOT: %y = alloca i32, align 4
+  %y = alloca i32, align 4
+  ; CHECK-NOT: store i32 0, i32* %retval, align 4
+  store i32 0, i32* %retval, align 4
+  store i32 0, i32* %x, align 4
+  %0 = load i32, i32* %x, align 4
+  ; CHECK-NOT: %inc = add nsw i32 %0, 1
+  %inc = add nsw i32 %0, 1
+  store i32 %inc, i32* %x, align 4
+  %1 = load i32, i32* %x, align 4
+  ; CHECK-NOT: store i32 %1, i32* %y, align 4
+  store i32 %1, i32* %y, align 4
+  ; CHECK-NOT: ret i32 0
+  ret i32 0
+}

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
 
   DEPENDS
   intrinsics_gen
   )
 export_executable_symbols(llvm-reduce)

llvm/tools/llvm-reduce/DeltaManager.h

 //===----------------------------------------------------------------------===//
 
 #include "TestRunner.h"
 #include "deltas/Delta.h"
 #include "deltas/ReduceArguments.h"
 #include "deltas/ReduceFunctions.h"
 #include "deltas/ReduceGlobalVars.h"
 #include "deltas/ReduceMetadata.h"
+#include "deltas/ReduceInstructions.h"
 
 namespace llvm {
 
 // TODO: Add CLI option to run only specified Passes (for unit tests)
 inline void runDeltaPasses(TestRunner &Tester) {
   reduceFunctionsDeltaPass(Tester);
   reduceGlobalsDeltaPass(Tester);
   reduceMetadataDeltaPass(Tester);
   reduceArgumentsDeltaPass(Tester);
+  reduceInstructionsDeltaPass(Tester);
   // TODO: Implement the remaining Delta Passes
 }
 
 } // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceInstructions.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 reduceInstructionsDeltaPass(TestRunner &Test);
+} // namespace llvm

llvm/tools/llvm-reduce/deltas/ReduceInstructions.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 "ReduceInstructions.h"
+
+/// 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 extractInstrFromModule(std::vector<Chunk> ChunksToKeep,
+                                   Module *Program) {
+  unsigned I = 0, InstCount = 0;
+  std::set<Instruction *> InstToKeep;
+
+  for (auto &F : *Program)
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        if (I < ChunksToKeep.size()) {
+          if (ChunksToKeep[I].contains(++InstCount))
+            InstToKeep.insert(&Inst);
+          if (ChunksToKeep[I].end == InstCount)
+            ++I;
+        }
+
+  std::vector<Instruction *> InstToDelete;
+  for (auto &F : *Program)
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        if (!InstToKeep.count(&Inst)) {
+          Inst.replaceAllUsesWith(UndefValue::get(Inst.getType()));
+          InstToDelete.push_back(&Inst);
+        }
+
+  for (auto &I : InstToDelete)
+    I->eraseFromParent();
+}
+
+/// Counts the amount of basic blocks and prints their name & respective index
+static unsigned countInstructions(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  int InstCount = 0;
+  for (auto &F : *Program)
+    for (auto &BB : F)
+        InstCount += BB.getInstList().size();
+  outs() << "Number of instructions: " << InstCount << "\n";
+
+  return InstCount;
+}
+
+void llvm::reduceInstructionsDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Insructions...\n";
+  unsigned InstCount = countInstructions(Test.getProgram());
+  runDeltaPass(Test, InstCount, extractInstrFromModule);
+}