diff --git a/source/reduce/reducer.cpp b/source/reduce/reducer.cpp
index a751b71..4f4429a 100644
--- a/source/reduce/reducer.cpp
+++ b/source/reduce/reducer.cpp
@@ -81,6 +81,11 @@
 
     // Iterate through the available passes
     for (auto& pass : impl_->passes) {
+      // If this pass hasn't reached its minimum granularity then it's
+      // worth eventually doing another round of reductions, in order to
+      // try this pass at a finer granularity.
+      another_round_worthwhile |= !pass->ReachedMinimumGranularity();
+
       // Keep applying this pass at its current granularity until it stops
       // working or we hit the reduction step limit.
       impl_->consumer(SPV_MSG_INFO, nullptr, {},
@@ -89,14 +94,10 @@
         auto maybe_result = pass->TryApplyReduction(current_binary);
         if (maybe_result.empty()) {
           // This pass did not have any impact, so move on to the next pass.
-          // If this pass hasn't reached its minimum granularity then it's
-          // worth eventually doing another round of reductions, in order to
-          // try this pass at a finer granularity.
           impl_->consumer(
               SPV_MSG_INFO, nullptr, {},
               ("Pass " + pass->GetName() + " did not make a reduction step.")
                   .c_str());
-          another_round_worthwhile |= !pass->ReachedMinimumGranularity();
           break;
         }
         std::stringstream stringstream;
@@ -105,7 +106,14 @@
                      << reductions_applied << ".";
         impl_->consumer(SPV_MSG_INFO, nullptr, {},
                         (stringstream.str().c_str()));
-        if (impl_->interestingness_function(maybe_result, reductions_applied)) {
+        if (!spvtools::SpirvTools(impl_->target_env).Validate(maybe_result)) {
+          // The reduction step went wrong and an invalid binary was produced.
+          // By design, this shouldn't happen; this is a safeguard to stop an
+          // invalid binary from being regarded as interesting.
+          impl_->consumer(SPV_MSG_INFO, nullptr, {},
+                          "Reduction step produced an invalid binary.");
+        } else if (impl_->interestingness_function(maybe_result,
+                                                   reductions_applied)) {
           // Success!  The binary produced by this reduction step is
           // interesting, so make it the binary of interest henceforth, and
           // note that it's worth doing another round of reduction passes.
diff --git a/test/reduce/CMakeLists.txt b/test/reduce/CMakeLists.txt
index 69731a6..cdd27b9 100644
--- a/test/reduce/CMakeLists.txt
+++ b/test/reduce/CMakeLists.txt
@@ -21,6 +21,7 @@
         remove_opname_instruction_reduction_pass_test.cpp
         remove_unreferenced_instruction_reduction_pass_test.cpp
         structured_loop_to_selection_reduction_pass_test.cpp
+        validation_during_reduction_test.cpp
         LIBS SPIRV-Tools-reduce
         )
 
diff --git a/test/reduce/reduce_test_util.cpp b/test/reduce/reduce_test_util.cpp
index 4561439..19ef749 100644
--- a/test/reduce/reduce_test_util.cpp
+++ b/test/reduce/reduce_test_util.cpp
@@ -64,5 +64,9 @@
   return result;
 }
 
+void NopDiagnostic(spv_message_level_t /*level*/, const char* /*source*/,
+                   const spv_position_t& /*position*/,
+                   const char* /*message*/) {}
+
 }  // namespace reduce
 }  // namespace spvtools
diff --git a/test/reduce/reduce_test_util.h b/test/reduce/reduce_test_util.h
index 80cc092..499c774 100644
--- a/test/reduce/reduce_test_util.h
+++ b/test/reduce/reduce_test_util.h
@@ -72,6 +72,10 @@
 const uint32_t kReduceDisassembleOption =
     SPV_BINARY_TO_TEXT_OPTION_NO_HEADER | SPV_BINARY_TO_TEXT_OPTION_INDENT;
 
+// Don't print reducer info during testing.
+void NopDiagnostic(spv_message_level_t /*level*/, const char* /*source*/,
+                   const spv_position_t& /*position*/, const char* /*message*/);
+
 }  // namespace reduce
 }  // namespace spvtools
 
diff --git a/test/reduce/reducer_test.cpp b/test/reduce/reducer_test.cpp
index 4ce68cc..88fc5e4 100644
--- a/test/reduce/reducer_test.cpp
+++ b/test/reduce/reducer_test.cpp
@@ -23,11 +23,6 @@
 namespace reduce {
 namespace {
 
-// Don't print reducer info during testing.
-void NopDiagnostic(spv_message_level_t /*level*/, const char* /*source*/,
-                   const spv_position_t& /*position*/,
-                   const char* /*message*/) {}
-
 // This changes its mind each time IsInteresting is invoked as to whether the
 // binary is interesting, until some limit is reached after which the binary is
 // always deemed interesting.  This is useful to test that reduction passes
diff --git a/test/reduce/validation_during_reduction_test.cpp b/test/reduce/validation_during_reduction_test.cpp
new file mode 100644
index 0000000..bb7d14e
--- /dev/null
+++ b/test/reduce/validation_during_reduction_test.cpp
@@ -0,0 +1,376 @@
+// Copyright (c) 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "reduce_test_util.h"
+
+#include "source/reduce/reducer.h"
+#include "source/reduce/reduction_pass.h"
+#include "source/reduce/remove_instruction_reduction_opportunity.h"
+
+namespace spvtools {
+namespace reduce {
+namespace {
+
+// A dumb reduction pass that removes global values regardless of whether they
+// are referenced. This is very likely to make the resulting module invalid.  We
+// use this to test the reducer's behavior in the scenario where a bad reduction
+// pass leads to an invalid module.
+class BlindlyRemoveGlobalValuesPass : public ReductionPass {
+ public:
+  // Creates the reduction pass in the context of the given target environment
+  // |target_env|
+  explicit BlindlyRemoveGlobalValuesPass(const spv_target_env target_env)
+      : ReductionPass(target_env) {}
+
+  ~BlindlyRemoveGlobalValuesPass() override = default;
+
+  // The name of this pass.
+  std::string GetName() const final { return "BlindlyRemoveGlobalValuesPass"; };
+
+ protected:
+  // Adds opportunities to remove all global values.  Assuming they are all
+  // referenced (directly or indirectly) from elsewhere in the module, each such
+  // opportunity will make the module invalid.
+  std::vector<std::unique_ptr<ReductionOpportunity>> GetAvailableOpportunities(
+      opt::IRContext* context) const final {
+    std::vector<std::unique_ptr<ReductionOpportunity>> result;
+    for (auto& inst : context->module()->types_values()) {
+      if (inst.HasResultId()) {
+        result.push_back(
+            MakeUnique<RemoveInstructionReductionOpportunity>(&inst));
+      }
+    }
+    return result;
+  }
+};
+
+TEST(ValidationDuringReductionTest, CheckInvalidPassMakesNoProgress) {
+  // A module whose global values are all referenced, so that any application of
+  // MakeModuleInvalidPass will make the module invalid.
+  std::string original = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main" %60
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+               OpName %4 "main"
+               OpName %16 "buf2"
+               OpMemberName %16 0 "i"
+               OpName %18 ""
+               OpName %25 "buf1"
+               OpMemberName %25 0 "f"
+               OpName %27 ""
+               OpName %60 "_GLF_color"
+               OpMemberDecorate %16 0 Offset 0
+               OpDecorate %16 Block
+               OpDecorate %18 DescriptorSet 0
+               OpDecorate %18 Binding 2
+               OpMemberDecorate %25 0 Offset 0
+               OpDecorate %25 Block
+               OpDecorate %27 DescriptorSet 0
+               OpDecorate %27 Binding 1
+               OpDecorate %60 Location 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %9 = OpConstant %6 0
+         %16 = OpTypeStruct %6
+         %17 = OpTypePointer Uniform %16
+         %18 = OpVariable %17 Uniform
+         %19 = OpTypePointer Uniform %6
+         %22 = OpTypeBool
+         %24 = OpTypeFloat 32
+         %25 = OpTypeStruct %24
+         %26 = OpTypePointer Uniform %25
+         %27 = OpVariable %26 Uniform
+         %28 = OpTypePointer Uniform %24
+         %31 = OpConstant %24 2
+         %56 = OpConstant %6 1
+         %58 = OpTypeVector %24 4
+         %59 = OpTypePointer Output %58
+         %60 = OpVariable %59 Output
+         %72 = OpUndef %24
+         %74 = OpUndef %6
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+               OpBranch %10
+         %10 = OpLabel
+         %73 = OpPhi %6 %74 %5 %77 %34
+         %71 = OpPhi %24 %72 %5 %76 %34
+         %70 = OpPhi %6 %9 %5 %57 %34
+         %20 = OpAccessChain %19 %18 %9
+         %21 = OpLoad %6 %20
+         %23 = OpSLessThan %22 %70 %21
+               OpLoopMerge %12 %34 None
+               OpBranchConditional %23 %11 %12
+         %11 = OpLabel
+         %29 = OpAccessChain %28 %27 %9
+         %30 = OpLoad %24 %29
+         %32 = OpFOrdGreaterThan %22 %30 %31
+               OpSelectionMerge %34 None
+               OpBranchConditional %32 %33 %46
+         %33 = OpLabel
+         %40 = OpFAdd %24 %71 %30
+         %45 = OpISub %6 %73 %21
+               OpBranch %34
+         %46 = OpLabel
+         %50 = OpFMul %24 %71 %30
+         %54 = OpSDiv %6 %73 %21
+               OpBranch %34
+         %34 = OpLabel
+         %77 = OpPhi %6 %45 %33 %54 %46
+         %76 = OpPhi %24 %40 %33 %50 %46
+         %57 = OpIAdd %6 %70 %56
+               OpBranch %10
+         %12 = OpLabel
+         %61 = OpAccessChain %28 %27 %9
+         %62 = OpLoad %24 %61
+         %66 = OpConvertSToF %24 %21
+         %68 = OpConvertSToF %24 %73
+         %69 = OpCompositeConstruct %58 %62 %71 %66 %68
+               OpStore %60 %69
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
+  Reducer reducer(env);
+  reducer.SetMessageConsumer(NopDiagnostic);
+
+  // Say that every module is interesting.
+  reducer.SetInterestingnessFunction(
+      [](const std::vector<uint32_t>&, uint32_t) -> bool { return true; });
+
+  reducer.AddReductionPass(MakeUnique<BlindlyRemoveGlobalValuesPass>(env));
+
+  std::vector<uint32_t> binary_in;
+  SpirvTools t(env);
+
+  ASSERT_TRUE(t.Assemble(original, &binary_in, kReduceAssembleOption));
+  std::vector<uint32_t> binary_out;
+  spvtools::ReducerOptions reducer_options;
+  reducer_options.set_step_limit(500);
+
+  reducer.Run(std::move(binary_in), &binary_out, reducer_options);
+
+  // The reducer should have no impact.
+  CheckEqual(env, original, binary_out);
+}
+
+TEST(ValidationDuringReductionTest, CheckNotAlwaysInvalidCanMakeProgress) {
+  // A module with just one unreferenced global value.  All but one application
+  // of MakeModuleInvalidPass will make the module invalid.
+  std::string original = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main" %60
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+               OpName %4 "main"
+               OpName %16 "buf2"
+               OpMemberName %16 0 "i"
+               OpName %18 ""
+               OpName %25 "buf1"
+               OpMemberName %25 0 "f"
+               OpName %27 ""
+               OpName %60 "_GLF_color"
+               OpMemberDecorate %16 0 Offset 0
+               OpDecorate %16 Block
+               OpDecorate %18 DescriptorSet 0
+               OpDecorate %18 Binding 2
+               OpMemberDecorate %25 0 Offset 0
+               OpDecorate %25 Block
+               OpDecorate %27 DescriptorSet 0
+               OpDecorate %27 Binding 1
+               OpDecorate %60 Location 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %9 = OpConstant %6 0
+         %16 = OpTypeStruct %6
+         %17 = OpTypePointer Uniform %16
+         %18 = OpVariable %17 Uniform
+         %19 = OpTypePointer Uniform %6
+         %22 = OpTypeBool
+         %24 = OpTypeFloat 32
+         %25 = OpTypeStruct %24
+         %26 = OpTypePointer Uniform %25
+         %27 = OpVariable %26 Uniform
+         %28 = OpTypePointer Uniform %24
+         %31 = OpConstant %24 2
+         %56 = OpConstant %6 1
+       %1000 = OpConstant %6 1000 ; It should be possible to remove this instruction without making the module invalid.
+         %58 = OpTypeVector %24 4
+         %59 = OpTypePointer Output %58
+         %60 = OpVariable %59 Output
+         %72 = OpUndef %24
+         %74 = OpUndef %6
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+               OpBranch %10
+         %10 = OpLabel
+         %73 = OpPhi %6 %74 %5 %77 %34
+         %71 = OpPhi %24 %72 %5 %76 %34
+         %70 = OpPhi %6 %9 %5 %57 %34
+         %20 = OpAccessChain %19 %18 %9
+         %21 = OpLoad %6 %20
+         %23 = OpSLessThan %22 %70 %21
+               OpLoopMerge %12 %34 None
+               OpBranchConditional %23 %11 %12
+         %11 = OpLabel
+         %29 = OpAccessChain %28 %27 %9
+         %30 = OpLoad %24 %29
+         %32 = OpFOrdGreaterThan %22 %30 %31
+               OpSelectionMerge %34 None
+               OpBranchConditional %32 %33 %46
+         %33 = OpLabel
+         %40 = OpFAdd %24 %71 %30
+         %45 = OpISub %6 %73 %21
+               OpBranch %34
+         %46 = OpLabel
+         %50 = OpFMul %24 %71 %30
+         %54 = OpSDiv %6 %73 %21
+               OpBranch %34
+         %34 = OpLabel
+         %77 = OpPhi %6 %45 %33 %54 %46
+         %76 = OpPhi %24 %40 %33 %50 %46
+         %57 = OpIAdd %6 %70 %56
+               OpBranch %10
+         %12 = OpLabel
+         %61 = OpAccessChain %28 %27 %9
+         %62 = OpLoad %24 %61
+         %66 = OpConvertSToF %24 %21
+         %68 = OpConvertSToF %24 %73
+         %69 = OpCompositeConstruct %58 %62 %71 %66 %68
+               OpStore %60 %69
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  // This is the same as the original, except that the constant declaration of
+  // 1000 is gone.
+  std::string expected = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main" %60
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+               OpName %4 "main"
+               OpName %16 "buf2"
+               OpMemberName %16 0 "i"
+               OpName %18 ""
+               OpName %25 "buf1"
+               OpMemberName %25 0 "f"
+               OpName %27 ""
+               OpName %60 "_GLF_color"
+               OpMemberDecorate %16 0 Offset 0
+               OpDecorate %16 Block
+               OpDecorate %18 DescriptorSet 0
+               OpDecorate %18 Binding 2
+               OpMemberDecorate %25 0 Offset 0
+               OpDecorate %25 Block
+               OpDecorate %27 DescriptorSet 0
+               OpDecorate %27 Binding 1
+               OpDecorate %60 Location 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %9 = OpConstant %6 0
+         %16 = OpTypeStruct %6
+         %17 = OpTypePointer Uniform %16
+         %18 = OpVariable %17 Uniform
+         %19 = OpTypePointer Uniform %6
+         %22 = OpTypeBool
+         %24 = OpTypeFloat 32
+         %25 = OpTypeStruct %24
+         %26 = OpTypePointer Uniform %25
+         %27 = OpVariable %26 Uniform
+         %28 = OpTypePointer Uniform %24
+         %31 = OpConstant %24 2
+         %56 = OpConstant %6 1
+         %58 = OpTypeVector %24 4
+         %59 = OpTypePointer Output %58
+         %60 = OpVariable %59 Output
+         %72 = OpUndef %24
+         %74 = OpUndef %6
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+               OpBranch %10
+         %10 = OpLabel
+         %73 = OpPhi %6 %74 %5 %77 %34
+         %71 = OpPhi %24 %72 %5 %76 %34
+         %70 = OpPhi %6 %9 %5 %57 %34
+         %20 = OpAccessChain %19 %18 %9
+         %21 = OpLoad %6 %20
+         %23 = OpSLessThan %22 %70 %21
+               OpLoopMerge %12 %34 None
+               OpBranchConditional %23 %11 %12
+         %11 = OpLabel
+         %29 = OpAccessChain %28 %27 %9
+         %30 = OpLoad %24 %29
+         %32 = OpFOrdGreaterThan %22 %30 %31
+               OpSelectionMerge %34 None
+               OpBranchConditional %32 %33 %46
+         %33 = OpLabel
+         %40 = OpFAdd %24 %71 %30
+         %45 = OpISub %6 %73 %21
+               OpBranch %34
+         %46 = OpLabel
+         %50 = OpFMul %24 %71 %30
+         %54 = OpSDiv %6 %73 %21
+               OpBranch %34
+         %34 = OpLabel
+         %77 = OpPhi %6 %45 %33 %54 %46
+         %76 = OpPhi %24 %40 %33 %50 %46
+         %57 = OpIAdd %6 %70 %56
+               OpBranch %10
+         %12 = OpLabel
+         %61 = OpAccessChain %28 %27 %9
+         %62 = OpLoad %24 %61
+         %66 = OpConvertSToF %24 %21
+         %68 = OpConvertSToF %24 %73
+         %69 = OpCompositeConstruct %58 %62 %71 %66 %68
+               OpStore %60 %69
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
+  Reducer reducer(env);
+  reducer.SetMessageConsumer(NopDiagnostic);
+
+  // Say that every module is interesting.
+  reducer.SetInterestingnessFunction(
+      [](const std::vector<uint32_t>&, uint32_t) -> bool { return true; });
+
+  reducer.AddReductionPass(MakeUnique<BlindlyRemoveGlobalValuesPass>(env));
+
+  std::vector<uint32_t> binary_in;
+  SpirvTools t(env);
+
+  ASSERT_TRUE(t.Assemble(original, &binary_in, kReduceAssembleOption));
+  std::vector<uint32_t> binary_out;
+  spvtools::ReducerOptions reducer_options;
+  reducer_options.set_step_limit(500);
+
+  reducer.Run(std::move(binary_in), &binary_out, reducer_options);
+  CheckEqual(env, expected, binary_out);
+}
+
+}  // namespace
+}  // namespace reduce
+}  // namespace spvtools