[Bugpoint redesign] Added Pass to Remove Global Variables

[diegotf]

Summary

This pass tries to remove Global Variables as well as their direct uses, for example if a given GV @x is deemed uninteresting and it's used by %call and %call2. Both the GV as well as its calls would be deleted (any uses of the calls would be replaced with undef)

Depends on D63672

[fhahn]

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

1 ↗

(On Diff #207934)

file name needs updating I think

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

1 ↗

(On Diff #207934)

file name needs updating I think

[diegotf]

Fixed top-level comments to fit actual filename & description.

Reworded doxygen comment on eraseDerivedUsers

[diegotf]

Changed commit so it only has changes made to parent diff (D63672)

[dblaikie]

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

9–15

Might be stronger to:

CHECK-NOT: "global" on either side of the "CHECK: @interesting = global"

That way it'd be resilient to any reordering, for instance (where you could silently pass the test if LLVM IR happened to print 2, 3, unnumbered, 1)

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

53 ↗

(On Diff #208570)

Is the indentation off here? (clang-format can be handy to clean up stuff like this)

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

23–31 ↗

(On Diff #208570)

Classes to group static functions are somewhat to be avoided, I think - should this be a helper namespace, or maybe leaving the functions in the 'llvm' namespace while making the names more specific?

[diegotf]

Fixed out-of-range bug on specialized passes when getting Targets

Refactored removal of uninteresting chunks in Delta.h, since erasing them whilst iterating crashed when last Chunk was erased

Re-ran clang-format

[diegotf]

Refactored Delta Debugging Algorithm from a template class to an inline function in LLVM namespace; the specialized behaviour called by the generic Delta pass is given as parameters to the function instead of being given as a class template and then called statically in order to reduce confusion.

Note: Specialized Delta passes are also now inline functions instead of classes that groupped static functions.

[diegotf]

Re-worded header comments to fit new implementation

[diegotf]

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

9–15

Good catch! I hadn't thought of that.

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

23–31 ↗

(On Diff #208570)

I've refactored the Generic Delta pass in order to avoid this problem. I believe it's also simpler and easier to read.

[dblaikie]

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

23–24 ↗

(On Diff #209649)

(non-member) Static functions aren't appropriate in header files (they lead to code size increases and ODR violations).

You could move these into some sort of implementation namespace (llvm::impl or something like that) or I guess they could be stateless lambdas - or moved out-of-line into a .cpp file instead. (moving the removeGlobalsDeltaPass definition out of line so it can refer to the implementation functions in the .cpp file (where those functions can/should be 'static' in that case))

[diegotf]

Moved Delta pass function definitions from header to cpp files in order to avoid ODR violations.

[dblaikie]

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

67 ↗

(On Diff #209957)

This 'inline' keyword probably needs to be removed. I'm surprised if this code links as-is (or compiles - some sort of warning/error like this:

inl.cpp:1:13: warning: inline function 'f' is not defined [-Wundefined-inline]
inline void f();

^

inl.cpp:3:3: note: used here

f();
^

[diegotf]

Removed inline keyword from function declarations (since it's defined out-of-line)

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

67 ↗

(On Diff #209957)

Yeah, I goofed up and uploaded a wrong commit

[diegotf]

Added license & file header to cpp files

[diegotf]

Changed Pass behavior so it doesnt delete derived uses anymore.

[diegotf]

Re-added behavior to delete direct uses opf GVs (accidentally deleted)

[diegotf]

Remove Metadata pass from DeltaManager.h and CMakeLists.txt

[diegotf]

Update diff so it only show changes made to D63672

[diegotf]

Changed GV unit test to fit to a more targeted interesting-ness test

[diegotf]

Changed it to show only changes to D63672

[dblaikie]

hmm, hard to review - the baseline review (D63672) seems inconsistent with the API usage here - so I'm not sure what's authoritative, which design changes have been discussed/finalized, etc..

[diegotf]

In D64176#1619418, @dblaikie wrote:

hmm, hard to review - the baseline review (D63672) seems inconsistent with the API usage here - so I'm not sure what's authoritative, which design changes have been discussed/finalized, etc..

I'll update this (and the child diffs) to fit the changes in baseline

[diegotf]

Formatting changes & added llvm-reduce as dependency to tests

[diegotf]

Update diff to reflect changes on baseline & moved interesting-ness test to python

[diegotf]

General Formatting

[dblaikie]

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

9–15

seems good to have it on both sides (CHECK-NOT before and after the CHECK @interesting).

19–33

Should these CHECK-NOTs also have some CHECKs that demonstrate what these have been transformed into? (showing the undefs appear)

Also - are there differences between uninteresting1/2/3 that's interesting/important to testing here, or could there be similar test coverage with 1 uninteresting/removed global?

[dblaikie]

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

122–125

This change appears independent of the rest of this patch - if that's the case, please commit it separately. (no need to send it for review if it's nothing too interesting - if it's just reducing the scope of variables as is generally good)

[diegotf]

Simplified test & added check to verify that direct uses are replaced with undef

[diegotf]

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

19–33

Agreed, i'll add the checks. And yeah, uninteresting 2&3 might be overkill. I'll update the test accordingly

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

122–125

I'll move it to another then :)

[dblaikie]

Looks good - thanks (:

[diegotf]

Re-ran clang-format

[xbolva00]

Surprisingly test remove-global-vars.ll fails on buildbot

http://lab.llvm.org:8011/builders/lld-x86_64-ubuntu-fast/builds/4649

Previous build was OK and this test case worked.

Either this testcase is unstable or something was miscompiled after
[X86] Add custom type legalization for bitcasting mmx to v2i32/v4i16/v8i8 to use movq2dq instead of going through memory.

cc @craig.topper

[xbolva00]

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

6

This looks weird

[diegotf]

Patch here: D66314

[diegotf]

Changed test so reduced version is printed to STDOUT

[xbolva00]

Hi,

Bots warn;
srv/llvm-buildbot-srcatch/llvm-build-dir/clang-x86_64-debian-fast/llvm.src/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp:17:6: warning: '@returns' command used in a comment that is attached to a function returning void [-Wdocumentation]
1 warning generated.

Can you fix this small issue? Thanks

[dblaikie]

In D64176#1634377, @xbolva00 wrote:

Hi,

Bots warn;
srv/llvm-buildbot-srcatch/llvm-build-dir/clang-x86_64-debian-fast/llvm.src/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp:17:6: warning: '@returns' command used in a comment that is attached to a function returning void [-Wdocumentation]
1 warning generated.

Can you fix this small issue? Thanks

@bkramer fixed this in r369848 - thanks Ben!

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

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

llvm/test/Reduce/remove-funcs.ll

 ; Test that llvm-reduce can remove uninteresting functions as well as
 ; their InstCalls.
 ;
 ; RUN: llvm-reduce --test %p/Inputs/remove-funcs.py %s
 ; RUN: cat reduced.ll | FileCheck %s
-; REQUIRES: plugins, shell
+; REQUIRES: plugins
 
 ; CHECK-NOT: uninteresting1()
 define i32 @uninteresting1() {
 entry:
   ret i32 0
 }
 
 ; CHECK: interesting()

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

+; Test that llvm-reduce can remove uninteresting Global Variables as well as
+; their direct uses.
+;
+; RUN: llvm-reduce --test %p/Inputs/remove-global-vars.py %s
+; RUN: cat reduced.ll | FileCheck %s
+; REQUIRES: plugins
+
+@uninteresting1 = global i32 0, align 4
+; CHECK: @interesting = global
+@interesting = global i32 5, align 4
+; CHECK-NOT: global
+@uninteresting2 = global i32 25, align 4
+@uninteresting3 = global i32 50, align 4
+
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  store i32 0, i32* %retval, align 4
+  ; CHECK-NOT: load i32, i32* @uninteresting2, align 4
+  %0 = load i32, i32* @uninteresting2, align 4
+  store i32 %0, i32* @interesting, align 4
+  ; CHECK-NOT: load i32, i32* @uninteresting3, align 4
+  %1 = load i32, i32* @uninteresting3, align 4
+  %dec = add nsw i32 %1, -1
+  ; CHECK-NOT: store i32 %dec, i32* @uninteresting3, align 4
+  store i32 %dec, i32* @uninteresting3, align 4
+  ; CHECK: load i32, i32* @interesting, align 4
+  %2 = load i32, i32* @interesting, align 4
+  ; CHECK-NOT: load i32, i32* @uninteresting2, align 4
+  %3 = load i32, i32* @uninteresting2, align 4
+  %add = add nsw i32 %2, %3
+  ; CHECK-NOT: store i32 %add, i32* @uninteresting1, align 4
+  store i32 %add, i32* @uninteresting1, align 4
+  store i32 10, i32* @interesting, align 4
+  ; CHECK: load i32, i32* @interesting, align 4
+  %4 = load i32, i32* @interesting, align 4
+  ret i32 0
+}

llvm/tools/llvm-reduce/CMakeLists.txt

 # Support plugins.
 set(LLVM_NO_DEAD_STRIP 1)
 
 add_llvm_tool(llvm-reduce
   llvm-reduce.cpp
   TestRunner.cpp
   deltas/Delta.cpp
   deltas/ReduceFunctions.cpp
+  deltas/ReduceGlobalVars.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/ReduceFunctions.h"
+#include "deltas/ReduceGlobalVars.h"
 
 namespace llvm {
 
+// TODO: Add function which can call specified delta passes (for unit tests)
 inline void runDeltaPasses(TestRunner &Tester) {
+  outs() << "Reducing functions...\n";
   reduceFunctionsDeltaPass(Tester);
+  outs() << "Reducing GVs...\n";
+  reduceGlobalsDeltaPass(Tester);
   // TODO: Implement the remaining Delta Passes
 }
 
 } // namespace llvm

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

 void llvm::runDeltaPass(
     TestRunner &Test, unsigned Targets,
     std::function<void(const std::vector<Chunk> &, Module *)>
         ExtractChunksFromModule) {
   if (!Targets) {
     outs() << "\nNothing to reduce\n";
     return;
   }
-
-  std::vector<Chunk> Chunks = {{1, Targets}};
-  std::set<Chunk> UninterestingChunks;
-  std::unique_ptr<Module> ReducedProgram;
-
   if (!Test.run(Test.getReducedFilepath())) {
     outs() << "\nInput isn't interesting! Verify interesting-ness test\n";
     return;
   }
 
+  std::vector<Chunk> Chunks = {{1, Targets}};
+  std::set<Chunk> UninterestingChunks;
+  std::unique_ptr<Module> ReducedProgram;
+
   if (!increaseGranularity(Chunks)) {
     outs() << "\nAlready at minimum size. Cannot reduce anymore.\n";
     return;
   }
 
   do {
     UninterestingChunks = {};
     for (int I = Chunks.size() - 1; I >= 0; --I) {
void llvm::runDeltaPass(
 
   } while (!UninterestingChunks.empty() || increaseGranularity(Chunks));
 
   // If we reduced the testcase replace it
   if (ReducedProgram)
     Test.setProgram(std::move(ReducedProgram));
   outs() << "Couldn't increase anymore.\n";
 }
 No newline at end of file

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

-//===- DeltaManager.h - Runs Delta Passes to reduce Input -----------------===//
+//===- RemoveGlobalVars.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 calls each specialized Delta pass in order to reduce the input IR
-// file.
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce initialized Global Variables in the provided Module.
 //
 //===----------------------------------------------------------------------===//
 
-#include "TestRunner.h"
-#include "deltas/Delta.h"
-#include "deltas/ReduceFunctions.h"
+#include "Delta.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Transforms/Utils/Cloning.h"
 
 namespace llvm {
-
-inline void runDeltaPasses(TestRunner &Tester) {
-  reduceFunctionsDeltaPass(Tester);
-  // TODO: Implement the remaining Delta Passes
-}
-
+void reduceGlobalsDeltaPass(TestRunner &Test);
 } // namespace llvm

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

+//===- RemoveGlobalVars.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 initialized Global Variables in the provided Module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceGlobalVars.h"
+
+/// Removes all the Initialized GVs that aren't inside the desired Chunks.
+/// @returns the Module stripped of out-of-chunk GVs
+static void extractGVsFromModule(std::vector<Chunk> ChunksToKeep,
+                                 Module *Program) {
+  // Get GVs inside desired chunks
+  std::set<GlobalVariable *> GVsToKeep;
+  unsigned I = 0, GVCount = 0;
+  for (auto &GV : Program->globals())
+    if (GV.hasInitializer() && I < ChunksToKeep.size()) {
+      if (ChunksToKeep[I].contains(++GVCount))
+        GVsToKeep.insert(&GV);
+      if (GVCount == ChunksToKeep[I].end)
+        ++I;
+    }
+
+  // Delete out-of-chunk GVs and their uses
+  std::vector<GlobalVariable *> ToRemove;
+  std::vector<Instruction *> InstToRemove;
+  for (auto &GV : Program->globals())
+    if (GV.hasInitializer() && !GVsToKeep.count(&GV)) {
+      for (auto U : GV.users())
+        if (auto *Inst = dyn_cast<Instruction>(U))
+          InstToRemove.push_back(Inst);
+
+      GV.replaceAllUsesWith(UndefValue::get(GV.getType()));
+      ToRemove.push_back(&GV);
+    }
+
+  // Delete Instruction uses of unwanted GVs
+  for (auto *Inst : InstToRemove) {
+    Inst->replaceAllUsesWith(UndefValue::get(Inst->getType()));
+    Inst->eraseFromParent();
+  }
+
+  for (auto *GV : ToRemove)
+    GV->eraseFromParent();
+}
+
+/// Counts the amount of initialized GVs and displays their
+/// respective name & index
+static int countGVs(Module *Program) {
+  // TODO: Silence index with --quiet flag
+  outs() << "----------------------------\n";
+  outs() << "GlobalVariable Index Reference:\n";
+  int GVCount = 0;
+  for (auto &GV : Program->globals())
+    if (GV.hasInitializer())
+      outs() << "\t" << ++GVCount << ": " << GV.getName() << "\n";
+  outs() << "----------------------------\n";
+  return GVCount;
+}
+
+void llvm::reduceGlobalsDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing GVs...\n";
+  unsigned GVCount = countGVs(Test.getProgram());
+  runDeltaPass(Test, GVCount, extractGVsFromModule);
+}