[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-bbs.py

 import sys
-import re
 
 InterestingBBs = 0
 input = open(sys.argv[1], "r")
 for line in input:
   i = line.find(';')
   if i >= 0:
     line = line[:i]
   if line.startswith("interesting") or "%interesting" in line:
     InterestingBBs += 1
 
 if InterestingBBs == 6:
   sys.exit(0) # interesting!
 
 sys.exit(1) # IR isn't interesting

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

 #!/usr/bin/env python
 
 import sys
 
+InterestingVar = 0
+
 input = open(sys.argv[1], "r")
 for line in input:
-  if "@interesting = global" in line:
-    sys.exit(0)
+  i = line.find(';')
+  if i >= 0:
+    line = line[:i]
+  if line.startswith("@interesting = global") or "@interesting" in line:
+    InterestingVar += 1
+
+if InterestingVar == 4:
+  sys.exit(0) # interesting!
 
-sys.exit(1) # IR isn't interesting
+sys.exit(1)

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

+import sys
+
+InterestingInstructions = 0
+
+input = open(sys.argv[1], "r")
+for line in input:
+  i = line.find(';')
+  if i >= 0:
+    line = line[:i]
+  if "%interesting" in line:
+    InterestingInstructions += 1
+  print InterestingInstructions
+
+if InterestingInstructions == 5:
+  sys.exit(0) # interesting!
+
+sys.exit(1)

llvm/test/Reduce/remove-global-vars.ll

entry:
   %0 = load i32, i32* @uninteresting, align 4
   ; CHECK: store i32 undef, i32* @interesting, align 4
   store i32 %0, i32* @interesting, align 4
 
   ; CHECK: load i32, i32* @interesting, align 4
   %1 = load i32, i32* @interesting, align 4
   store i32 %1, i32* @uninteresting, align 4
 
-  ; CHECK: %inc = add nsw i32 undef, 1
-  %inc = add nsw i32 %0, 1
-  ; CHECK: store i32 %inc, i32* @interesting, align 4
-  store i32 %inc, i32* @interesting, align 4
+  ; CHECK: store i32 5, i32* @interesting, align 4
+  store i32 5, i32* @interesting, align 4
   ret i32 0
 }

llvm/test/Reduce/remove-instructions.ll

+; Test that llvm-reduce can remove uninteresting instructions.
+;
+; RUN: llvm-reduce --test %python --test-arg %p/Inputs/remove-instructions.py %s -o %t
+; RUN: cat %t | FileCheck -implicit-check-not=uninteresting %s
+; REQUIRES: plugins
+
+; We're testing all direct uses of %interesting are conserved
+; CHECK-COUNT-5: %interesting
+define i32 @main() #0 {
+entry:
+  %uninteresting1 = alloca i32, align 4
+  %interesting = alloca i32, align 4
+  %uninteresting2 = alloca i32, align 4
+  store i32 0, i32* %uninteresting1, align 4
+  store i32 0, i32* %interesting, align 4
+  %0 = load i32, i32* %interesting, align 4
+  %uninteresting3 = add nsw i32 %0, 1
+  store i32 %uninteresting3, i32* %interesting, align 4
+  %1 = load i32, i32* %interesting, align 4
+  store i32 %1, i32* %uninteresting2, align 4
+  ; CHECK-NOT: ret
+  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/ReduceBasicBlocks.cpp
+  deltas/ReduceInstructions.cpp
 
   DEPENDS
   intrinsics_gen
   )

llvm/tools/llvm-reduce/DeltaManager.h

 
 #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"
 
 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/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"
+
+using namespace llvm;
+
+/// 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) {
+  int I = 0, InstCount = 0;
+  std::set<Instruction *> InstToKeep;
+
+  for (auto &F : *Program)
+    for (auto &BB : F)
+      for (auto &Inst : BB)
+        if (I < (int)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);
+}