Index: llvm/test/tools/llvm-reduce/reduce-global-variable-terminator-user.ll
===================================================================
--- /dev/null
+++ llvm/test/tools/llvm-reduce/reduce-global-variable-terminator-user.ll
@@ -0,0 +1,19 @@
+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=global-variables --test FileCheck --test-arg --check-prefixes=INTERESTING --test-arg %s --test-arg --input-file %s -o %t
+; RUN: FileCheck --check-prefixes=RESULT %s < %t
+
+; The global variable reduction was trying to delete use instructions
+; of globals for some reason, and breaking the basic blocks that had
+; global uses in the terminator
+
+; RESULT-NOT: @zed
+@zed = global i32 0
+
+; INTERESTING: @bar
+; RESULT: @bar
+@bar = global i32 1
+
+; RESULT: define ptr @zed_user() {
+; RESULT-NEXT: ret ptr null
+define ptr @zed_user() {
+  ret ptr @zed
+}
Index: llvm/test/tools/llvm-reduce/remove-global-vars.ll
===================================================================
--- llvm/test/tools/llvm-reduce/remove-global-vars.ll
+++ llvm/test/tools/llvm-reduce/remove-global-vars.ll
@@ -1,8 +1,8 @@
 ; Test that llvm-reduce can remove uninteresting Global Variables as well as
 ; their direct uses (which in turn are replaced with '0').
 
-; RUN: llvm-reduce --delta-passes=global-variables,global-initializers --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
-; RUN: cat %t | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL --implicit-check-not=uninteresting %s
+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=global-variables,global-initializers --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL --implicit-check-not=uninteresting %s < %t
 
 $interesting5 = comdat any
 
@@ -31,11 +31,11 @@
   %0 = load i32, ptr @uninteresting, align 4
 
   ; CHECK-INTERESTINGNESS: store i32 {{.*}}, ptr @interesting, align 4
-  ; CHECK-FINAL: store i32 0, ptr @interesting, align 4
+  ; CHECK-FINAL: store i32 %0, ptr @interesting, align 4
   store i32 %0, ptr @interesting, align 4
 
   ; CHECK-INTERESTINGNESS: store i32 {{.*}}, ptr @interesting3, align 4
-  ; CHECK-FINAL: store i32 0, ptr @interesting3, align 4
+  ; CHECK-FINAL: store i32 %0, ptr @interesting3, align 4
   store i32 %0, ptr @interesting3, align 4
 
   ; CHECK-ALL: load i32, ptr @interesting, align 4
Index: llvm/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp
===================================================================
--- llvm/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp
+++ llvm/tools/llvm-reduce/deltas/ReduceGlobalVars.cpp
@@ -15,50 +15,37 @@
 #include "Utils.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
-#include <set>
 
 using namespace llvm;
 
+static bool shouldAlwaysKeep(const GlobalVariable &GV) {
+  return GV.getName() == "llvm.used" || GV.getName() == "llvm.compiler.used";
+}
+
 /// 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<Constant *> InitGVsToKeep;
   for (auto &GV : Program.globals()) {
-    if ((GV.getName() == "llvm.used" || GV.getName() == "llvm.compiler.used") ||
-        O.shouldKeep())
+    if (shouldAlwaysKeep(GV) || 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<Constant *> GVsToKeep(InitGVsToKeep.begin(), InitGVsToKeep.end());
+  DenseSet<Constant *> GVsToKeep(InitGVsToKeep.begin(), InitGVsToKeep.end());
 
   // Delete out-of-chunk GVs and their uses
   DenseSet<Constant *> ToRemove;
-  std::vector<WeakVH> InstToRemove;
   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);
-
+    if (!GVsToKeep.count(&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->replaceAllUsesWith(getDefaultValue(GV->getType()));
     cast<GlobalVariable>(GV)->eraseFromParent();