llvm-reduce: Fix invalid reductions with llvm.used

[arsenm]

Summary

Fixes issue 59413.

[jdoerfert]

LG, with some nits though.

llvm/include/llvm/Transforms/Utils/ModuleUtils.h

88

Nit: I don't think we need it to be a std::function, llvm::function_ref should do.

llvm/lib/Transforms/Utils/ModuleUtils.cpp

147

Nits:
Early exit in the end.
Surprised we need .getArrayRef()
Here and elsewhere, we should keep GV around until we insert the new GlobalVariable before it to avoid reorderings in the IR.
Remove llvm::

[arsenm]

llvm/lib/Transforms/Utils/ModuleUtils.cpp

147

If you create the new one when the old one still exists, you get "@llvm.used0" which is wrong. Avoiding reordering would require finding the neighbor global

[arsenm]

aa9bdd50c25aa6a6dc58f2af397bdfcfad417244

llvm/lib/Transforms/Utils/ModuleUtils.cpp

147

I remembered takeName exists, so managed to fix this

llvm/include/llvm/Transforms/Utils/ModuleUtils.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_MODULEUTILS_H
 #define LLVM_TRANSFORMS_UTILS_MODULEUTILS_H
 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Alignment.h"
 #include "llvm/Support/MemoryBufferRef.h"
+#include <functional>
 #include <utility> // for std::pair
 
 namespace llvm {
 template <typename T> class SmallVectorImpl;
 
 template <typename T> class ArrayRef;
 class Module;
 class Function;

 bool nameUnamedGlobals(Module &M);
 
 /// Adds global values to the llvm.used list.
 void appendToUsed(Module &M, ArrayRef<GlobalValue *> Values);
 
 /// Adds global values to the llvm.compiler.used list.
 void appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values);
 
+/// Removes global values from the llvm.used and llvm.compiler.used arrays. \p
+/// ShouldRemove should return true for any initializer field that should not be
+/// included in the replacement global.
+void removeFromUsedLists(Module &M,
+                         std::function<bool(Constant *)> ShouldRemove);
+
 /// Filter out potentially dead comdat functions where other entries keep the
 /// entire comdat group alive.
 ///
 /// This is designed for cases where functions appear to become dead but remain
 /// alive due to other live entries in their comdat group.
 ///
 /// The \p DeadComdatFunctions container should only have pointers to
 /// `Function`s which are members of a comdat group and are believed to be

llvm/lib/Target/AMDGPU/AMDGPULowerModuleLDSPass.cpp

bool isKernelLDS(const Function *F) {
   // There's also a test that checks that the LDS lowering does not hit on
   // a graphics shader, denoted amdgpu_ps, so stay with the limited case.
   // Putting LDS in the name of the function to draw attention to this.
   return AMDGPU::isKernel(F->getCallingConv());
 }
 
 class AMDGPULowerModuleLDS : public ModulePass {
 
-  static void removeFromUsedList(Module &M, StringRef Name,
-                                 SmallPtrSetImpl<Constant *> &ToRemove) {
-    GlobalVariable *GV = M.getNamedGlobal(Name);
-    if (!GV || ToRemove.empty()) {
-      return;
-    }
-
-    SmallVector<Constant *, 16> Init;
-    auto *CA = cast<ConstantArray>(GV->getInitializer());
-    for (auto &Op : CA->operands()) {
-      // ModuleUtils::appendToUsed only inserts Constants
-      Constant *C = cast<Constant>(Op);
-      if (!ToRemove.contains(C->stripPointerCasts())) {
-        Init.push_back(C);
-      }
-    }
-
-    if (Init.size() == CA->getNumOperands()) {
-      return; // none to remove
-    }
-
-    GV->eraseFromParent();
-
-    for (Constant *C : ToRemove) {
-      C->removeDeadConstantUsers();
-    }
-
-    if (!Init.empty()) {
-      ArrayType *ATy =
-          ArrayType::get(Type::getInt8PtrTy(M.getContext()), Init.size());
-      GV =
-          new GlobalVariable(M, ATy, false, GlobalValue::AppendingLinkage,
-                                   ConstantArray::get(ATy, Init), Name);
-      GV->setSection("llvm.metadata");
-    }
-  }
-
-  static void removeFromUsedLists(Module &M,
-                                  const DenseSet<GlobalVariable *> &LocalVars) {
+  static void
+  removeLocalVarsFromUsedLists(Module &M,
     // The verifier rejects used lists containing an inttoptr of a constant
     // so remove the variables from these lists before replaceAllUsesWith
+    SmallPtrSet<Constant *, 8> LocalVarsSet;
+    for (GlobalVariable *LocalVar : LocalVars)
+      LocalVarsSet.insert(cast<Constant>(LocalVar->stripPointerCasts()));
+
+    removeFromUsedLists(
+        M, [&LocalVarsSet](Constant *C) { return LocalVarsSet.count(C); });
 
-    SmallPtrSet<Constant *, 32> LocalVarsSet;
     for (GlobalVariable *LocalVar : LocalVars)
-      if (Constant *C = dyn_cast<Constant>(LocalVar->stripPointerCasts()))
-        LocalVarsSet.insert(C);
-    removeFromUsedList(M, "llvm.used", LocalVarsSet);
-    removeFromUsedList(M, "llvm.compiler.used", LocalVarsSet);
+      LocalVar->removeDeadConstantUsers();
   }
 
   static void markUsedByKernel(IRBuilder<> &Builder, Function *Func,
                                GlobalVariable *SGV) {
     // The llvm.amdgcn.module.lds instance is implicitly used by all kernels
     // that might call a function which accesses a field within it. This is
     // presently approximated to 'all kernels' if there are any such functions
     // in the module. This implicit use is redefined as an explicit use here so
if (!ModuleScopeVariables.empty()) {
 
       appendToCompilerUsed(M,
                            {static_cast<GlobalValue *>(
                                ConstantExpr::getPointerBitCastOrAddrSpaceCast(
                                    cast<Constant>(ModuleScopeReplacement.SGV),
                                    Type::getInt8PtrTy(Ctx)))});
 
       // historic
-      removeFromUsedLists(M, ModuleScopeVariables);
+      removeLocalVarsFromUsedLists(M, ModuleScopeVariables);
 
       // Replace all uses of module scope variable from non-kernel functions
       replaceLDSVariablesWithStruct(
           M, ModuleScopeVariables, ModuleScopeReplacement, [&](Use &U) {
             Instruction *I = dyn_cast<Instruction>(U.getUser());
             if (!I) {
               return false;
             }
for (Function &Func : M.functions()) {
 
       std::string VarName =
           (Twine("llvm.amdgcn.kernel.") + Func.getName() + ".lds").str();
 
       auto Replacement =
           createLDSVariableReplacement(M, VarName, KernelUsedVariables);
 
       // remove preserves existing codegen
-      removeFromUsedLists(M, KernelUsedVariables);
+      removeLocalVarsFromUsedLists(M, KernelUsedVariables);
       KernelToReplacement[&Func] = Replacement;
 
       // Rewrite uses within kernel to the new struct
       replaceLDSVariablesWithStruct(
           M, KernelUsedVariables, Replacement, [&Func](Use &U) {
             Instruction *I = dyn_cast<Instruction>(U.getUser());
             return I && I->getFunction() == &Func;
           });

llvm/lib/Transforms/Utils/ModuleUtils.cpp

 void llvm::appendToGlobalCtors(Module &M, Function *F, int Priority, Constant *Data) {
   appendToGlobalArray("llvm.global_ctors", M, F, Priority, Data);
 }
 
 void llvm::appendToGlobalDtors(Module &M, Function *F, int Priority, Constant *Data) {
   appendToGlobalArray("llvm.global_dtors", M, F, Priority, Data);
 }
 
-static void appendToUsedList(Module &M, StringRef Name, ArrayRef<GlobalValue *> Values) {
-  GlobalVariable *GV = M.getGlobalVariable(Name);
-  SmallPtrSet<Constant *, 16> InitAsSet;
-  SmallVector<Constant *, 16> Init;
-  if (GV) {
-    if (GV->hasInitializer()) {
-      auto *CA = cast<ConstantArray>(GV->getInitializer());
-      for (auto &Op : CA->operands()) {
-        Constant *C = cast_or_null<Constant>(Op);
-        if (InitAsSet.insert(C).second)
-          Init.push_back(C);
-      }
-    }
+static void collectUsedGlobals(GlobalVariable *GV,
+                               SmallSetVector<Constant *, 16> &Init) {
+  if (!GV || !GV->hasInitializer())
+    return;
+
+  for (Use &Op : CA->operands())
+    Init.insert(cast<Constant>(Op));
+
+static void appendToUsedList(Module &M, StringRef Name, ArrayRef<GlobalValue *> Values) {
+  GlobalVariable *GV = M.getGlobalVariable(Name);
+
+  SmallSetVector<Constant *, 16> Init;
+  collectUsedGlobals(GV, Init);
+  if (GV)
     GV->eraseFromParent();
-  }
 
-  Type *Int8PtrTy = llvm::Type::getInt8PtrTy(M.getContext());
-  for (auto *V : Values) {
-    Constant *C = ConstantExpr::getPointerBitCastOrAddrSpaceCast(V, Int8PtrTy);
-    if (InitAsSet.insert(C).second)
-      Init.push_back(C);
-  }
+  Type *ArrayEltTy = llvm::Type::getInt8PtrTy(M.getContext());
+  for (auto *V : Values)
+    Init.insert(ConstantExpr::getPointerBitCastOrAddrSpaceCast(V, ArrayEltTy));
 
   if (Init.empty())
     return;
 
-  ArrayType *ATy = ArrayType::get(Int8PtrTy, Init.size());
+  ArrayType *ATy = ArrayType::get(ArrayEltTy, Init.size());
   GV = new llvm::GlobalVariable(M, ATy, false, GlobalValue::AppendingLinkage,
-                                ConstantArray::get(ATy, Init), Name);
+                                ConstantArray::get(ATy, Init.getArrayRef()),
+                                Name);
   GV->setSection("llvm.metadata");
 }
 
 void llvm::appendToUsed(Module &M, ArrayRef<GlobalValue *> Values) {
   appendToUsedList(M, "llvm.used", Values);
 }
 
 void llvm::appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values) {
   appendToUsedList(M, "llvm.compiler.used", Values);
 }
 
+static void removeFromUsedList(Module &M, StringRef Name,
+                               std::function<bool(Constant *)> ShouldRemove) {
+  GlobalVariable *GV = M.getNamedGlobal(Name);
+  if (!GV)
+    return;
+
+  SmallSetVector<Constant *, 16> Init;
+  collectUsedGlobals(GV, Init);
+
+  StringRef Section = GV->getSection();
+  unsigned AddrSpace = GV->getAddressSpace();
+  GlobalValue::ThreadLocalMode TLM = GV->getThreadLocalMode();
+
+  Type *ArrayEltTy = cast<ArrayType>(GV->getValueType())->getElementType();
+
+  GV->eraseFromParent();
+
+  SmallVector<Constant *, 16> NewInit;
+  for (Constant *MaybeRemoved : Init.getArrayRef()) {
+    if (!ShouldRemove(MaybeRemoved->stripPointerCasts()))
+      NewInit.push_back(MaybeRemoved);
+  }
+
+  if (!NewInit.empty()) {
+    ArrayType *ATy = ArrayType::get(ArrayEltTy, NewInit.size());
+    GV = new llvm::GlobalVariable(M, ATy, false, GlobalValue::AppendingLinkage,
+                                  ConstantArray::get(ATy, NewInit), Name,
+                                  nullptr, TLM, AddrSpace);
+    GV->setSection(Section);
+  }
+}
+
+void llvm::removeFromUsedLists(Module &M,
+                               std::function<bool(Constant *)> ShouldRemove) {
+  removeFromUsedList(M, "llvm.used", ShouldRemove);
+  removeFromUsedList(M, "llvm.compiler.used", ShouldRemove);
+}
+
 static void setKCFIType(Module &M, Function &F, StringRef MangledType) {
   if (!M.getModuleFlag("kcfi"))
     return;
   // Matches CodeGenModule::CreateKCFITypeId in Clang.
   LLVMContext &Ctx = M.getContext();
   MDBuilder MDB(Ctx);
   F.setMetadata(
       LLVMContext::MD_kcfi_type,

llvm/test/CodeGen/AMDGPU/lower-kernel-and-module-lds.ll

 ; CHECK: %llvm.amdgcn.module.lds.t = type { [8 x i8], [1 x i8] }
 ; CHECK: %llvm.amdgcn.kernel.k0.lds.t = type { [16 x i8], [4 x i8], [2 x i8], [1 x i8] }
 ; CHECK: %llvm.amdgcn.kernel.k1.lds.t = type { [16 x i8], [4 x i8], [2 x i8] }
 ; CHECK: %llvm.amdgcn.kernel.k2.lds.t = type { [2 x i8] }
 ; CHECK: %llvm.amdgcn.kernel.k3.lds.t = type { [4 x i8] }
 
 ;.
 ; CHECK: @llvm.amdgcn.module.lds = internal addrspace(3) global %llvm.amdgcn.module.lds.t undef, align 8
-; CHECK: @llvm.compiler.used = appending global [1 x i8*] [i8* addrspacecast (i8 addrspace(3)* getelementptr inbounds (%llvm.amdgcn.module.lds.t, %llvm.amdgcn.module.lds.t addrspace(3)* @llvm.amdgcn.module.lds, i32 0, i32 0, i32 0) to i8*)], section "llvm.metadata"
 ; CHECK: @llvm.amdgcn.kernel.k0.lds = internal addrspace(3) global %llvm.amdgcn.kernel.k0.lds.t undef, align 16
 ; CHECK: @llvm.amdgcn.kernel.k1.lds = internal addrspace(3) global %llvm.amdgcn.kernel.k1.lds.t undef, align 16
 ; CHECK: @llvm.amdgcn.kernel.k2.lds = internal addrspace(3) global %llvm.amdgcn.kernel.k2.lds.t undef, align 2
 ; CHECK: @llvm.amdgcn.kernel.k3.lds = internal addrspace(3) global %llvm.amdgcn.kernel.k3.lds.t undef, align 4
+; CHECK: @llvm.compiler.used = appending global [1 x i8*] [i8* addrspacecast (i8 addrspace(3)* getelementptr inbounds (%llvm.amdgcn.module.lds.t, %llvm.amdgcn.module.lds.t addrspace(3)* @llvm.amdgcn.module.lds, i32 0, i32 0, i32 0) to i8*)], section "llvm.metadata"
 ;.
 define amdgpu_kernel void @k0() #0 {
 ; CHECK-LABEL: @k0(
 ; CHECK-NEXT:    %lds.size.1.align.1.bc = bitcast [1 x i8] addrspace(3)* getelementptr inbounds (%llvm.amdgcn.kernel.k0.lds.t, %llvm.amdgcn.kernel.k0.lds.t addrspace(3)* @llvm.amdgcn.kernel.k0.lds, i32 0, i32 3) to i8 addrspace(3)*
 ; CHECK-NEXT:    store i8 1, i8 addrspace(3)* %lds.size.1.align.1.bc, align 2, !alias.scope !0, !noalias !3
 ; CHECK-NEXT:    %lds.size.2.align.2.bc = bitcast [2 x i8] addrspace(3)* getelementptr inbounds (%llvm.amdgcn.kernel.k0.lds.t, %llvm.amdgcn.kernel.k0.lds.t addrspace(3)* @llvm.amdgcn.kernel.k0.lds, i32 0, i32 2) to i8 addrspace(3)*
 ; CHECK-NEXT:    store i8 2, i8 addrspace(3)* %lds.size.2.align.2.bc, align 4
 ; CHECK-NEXT:    %lds.size.4.align.4.bc = bitcast [4 x i8] addrspace(3)* getelementptr inbounds (%llvm.amdgcn.kernel.k0.lds.t, %llvm.amdgcn.kernel.k0.lds.t addrspace(3)* @llvm.amdgcn.kernel.k0.lds, i32 0, i32 1) to i8 addrspace(3)*

llvm/test/tools/llvm-reduce/remove-functions-used.ll

+; RUN: llvm-reduce -abort-on-invalid-reduction --delta-passes=functions --test FileCheck --test-arg --check-prefix=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t.0
+; RUN: FileCheck --implicit-check-not=define --check-prefix=CHECK-FINAL %s < %t.0
+
+; Check a case where llvm.used is fully deleted
+; RUN: llvm-reduce -abort-on-invalid-reduction --delta-passes=functions --test FileCheck --test-arg --check-prefixes=CHECK-OTHER --test-arg %s --test-arg --input-file %s -o %t.1
+; RUN: FileCheck --implicit-check-not=define --check-prefix=CHECK-REMOVED %s < %t.1
+
[e-mail] = appending global [2 x ptr] [ptr @kept_used, ptr @removed_used ]
[e-mail] = appending global [2 x ptr] [ptr @kept_compiler_used, ptr @removed_compiler_used ]
+
+
+; CHECK-REMOVED-NOT: @llvm.used
+; CHECK-REMOVED-NOT: @llvm.compiler.used
+
+; CHECK-FINAL: @llvm.used = appending global [1 x ptr] [ptr @kept_used]
+; CHECK-FINAL: @llvm.compiler.used = appending global [1 x ptr] [ptr @kept_compiler_used]
+
+
+; CHECK-INTERESTINGNESS: define void @kept_used(
+; CHECK-FINAL: define void @kept_used(
+define void @kept_used() {
+  ret void
+}
+
+define void @removed_used() {
+  ret void
+}
+
+; CHECK-INTERESTINGNESS: define void @kept_compiler_used(
+; CHECK-FINAL: define void @kept_compiler_used(
+define void @kept_compiler_used() {
+  ret void
+}
+
+define void @removed_compiler_used() {
+  ret void
+}
+
+; CHECK-OTHER: define void @foo(
+; CHECK-REMOVED: define void @foo(
+define void @foo() {
+  ret void
+}
+

llvm/test/tools/llvm-reduce/remove-global-used.ll

+; RUN: llvm-reduce -abort-on-invalid-reduction --delta-passes=global-variables --test FileCheck --test-arg --check-prefix=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t.0
+; RUN: FileCheck --implicit-check-not=define --check-prefix=CHECK-FINAL %s < %t.0
+
+; Check a case where llvm.used is fully deleted
+; RUN: llvm-reduce -abort-on-invalid-reduction --delta-passes=global-variables --test FileCheck --test-arg --check-prefixes=CHECK-OTHER --test-arg %s --test-arg --input-file %s -o %t.1
+; RUN: FileCheck --implicit-check-not=define --check-prefix=CHECK-REMOVED %s < %t.1
+
+; CHECK-INTERESTINGNESS: @kept_used = global
+; CHECK-FINAL: @kept_used = global
+@kept_used = global i32 0
+
+@removed_used = global i32 1
+
+; CHECK-INTERESTINGNESS: @kept_compiler_used = global
+; CHECK-FINAL: @kept_compiler_used = global
+@kept_compiler_used = global i32 2
+
+@removed_compiler_used = global i32 3
+
+; CHECK-OTHER: @foo = global
+; CHECK-REMOVED: @foo = global
+@foo = global i32 4
+
[e-mail] = appending global [2 x ptr] [ptr @kept_used, ptr @removed_used ]
[e-mail] = appending global [2 x ptr] [ptr @kept_compiler_used, ptr @removed_compiler_used ]
+
+
+; CHECK-REMOVED-NOT: @llvm.used
+; CHECK-REMOVED-NOT: @llvm.compiler.used
+
+; CHECK-FINAL: @llvm.used = appending global [1 x ptr] [ptr @kept_used]
+; CHECK-FINAL: @llvm.compiler.used = appending global [1 x ptr] [ptr @kept_compiler_used]

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

 // Module.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceFunctions.h"
 #include "Delta.h"
 #include "Utils.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <iterator>
 #include <vector>
 
 using namespace llvm;
 
 /// Removes all the Defined Functions
 /// that aren't inside any of the desired Chunks.
 static void extractFunctionsFromModule(Oracle &O, Module &Program) {
   // Record all out-of-chunk functions.
-  std::vector<std::reference_wrapper<Function>> FuncsToRemove;
-  copy_if(Program.functions(), std::back_inserter(FuncsToRemove),
-          [&O](Function &F) {
-            // Intrinsics don't have function bodies that are useful to
-            // reduce. Additionally, intrinsics may have additional operand
-            // constraints. But, do drop intrinsics that are not referenced.
-            return (!F.isIntrinsic() || F.use_empty()) && !hasAliasUse(F) &&
-                   !O.shouldKeep();
-          });
+  SmallPtrSet<Constant *, 8> FuncsToRemove;
+  for (Function &F : Program.functions()) {
+    if ((!F.isIntrinsic() || F.use_empty()) && !hasAliasUse(F) &&
+        !O.shouldKeep())
+      FuncsToRemove.insert(&F);
+  }
+
+  removeFromUsedLists(Program, [&FuncsToRemove](Constant *C) {
+    return FuncsToRemove.count(C);
 
   // Then, drop body of each of them. We want to batch this and do nothing else
   // here so that minimal number of remaining exteranal uses will remain.
-  for (Function &F : FuncsToRemove)
-    F.dropAllReferences();
+  for (Constant *F : FuncsToRemove)
+    F->dropAllReferences();
 
   // And finally, we can actually delete them.
-  for (Function &F : FuncsToRemove) {
+  for (Constant *F : FuncsToRemove) {
     // Replace all *still* remaining uses with the default value.
-    F.replaceAllUsesWith(getDefaultValue(F.getType()));
+    F->replaceAllUsesWith(getDefaultValue(F->getType()));
     // And finally, fully drop it.
-    F.eraseFromParent();
+    cast<Function>(F)->eraseFromParent();
   }
 }
 
 void llvm::reduceFunctionsDeltaPass(TestRunner &Test) {
   runDeltaPass(Test, extractFunctionsFromModule, "Reducing Functions");
 }

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

 //===- ReduceGlobalVars.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 Global Variables in the provided Module.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceGlobalVars.h"
 #include "Utils.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <set>
 
 using namespace llvm;
 
 /// Removes all the GVs that aren't inside the desired Chunks.
 static void extractGVsFromModule(Oracle &O, Module &Program) {
   // Get GVs inside desired chunks
-  std::vector<GlobalVariable *> InitGVsToKeep;
-  for (auto &GV : Program.globals())
-    if (O.shouldKeep())
+  std::vector<Constant *> InitGVsToKeep;
+  for (auto &GV : Program.globals()) {
+    if ((GV.getName() == "llvm.used" || GV.getName() == "llvm.compiler.used") ||
+        O.shouldKeep())
       InitGVsToKeep.push_back(&GV);
+  }
 
   // We create a vector first, then convert it to a set, so that we don't have
   // to pay the cost of rebalancing the set frequently if the order we insert
   // the elements doesn't match the order they should appear inside the set.
-  std::set<GlobalVariable *> GVsToKeep(InitGVsToKeep.begin(),
-                                       InitGVsToKeep.end());
+  std::set<Constant *> GVsToKeep(InitGVsToKeep.begin(), InitGVsToKeep.end());
 
   // Delete out-of-chunk GVs and their uses
-  std::vector<GlobalVariable *> ToRemove;
+  DenseSet<Constant *> ToRemove;
   std::vector<WeakVH> InstToRemove;
-  for (auto &GV : Program.globals())
+  for (auto &GV : Program.globals()) {
     if (!GVsToKeep.count(&GV)) {
       for (auto *U : GV.users())
         if (auto *Inst = dyn_cast<Instruction>(U))
           InstToRemove.push_back(Inst);
 
-      GV.replaceAllUsesWith(getDefaultValue(GV.getType()));
-      ToRemove.push_back(&GV);
-    }
+      ToRemove.insert(&GV);
+    }
 
+  removeFromUsedLists(Program,
+                      [&ToRemove](Constant *C) { return ToRemove.count(C); });
+
   // Delete (unique) Instruction uses of unwanted GVs
   for (Value *V : InstToRemove) {
     if (!V)
       continue;
     auto *Inst = cast<Instruction>(V);
     Inst->replaceAllUsesWith(getDefaultValue(Inst->getType()));
     Inst->eraseFromParent();
   }
 
-  for (auto *GV : ToRemove)
-    GV->eraseFromParent();
+  for (auto *GV : ToRemove) {
+    GV->replaceAllUsesWith(getDefaultValue(GV->getType()));
+    cast<GlobalVariable>(GV)->eraseFromParent();
+  }
 }
 
 void llvm::reduceGlobalsDeltaPass(TestRunner &Test) {
   runDeltaPass(Test, extractGVsFromModule, "Reducing GlobalVariables");
 }