Add transformation to replace a boolean constant with a numeric comparison (#2659)

The transformation can, for example, replace "true" with "12.0 > 6.0",
if constants for those floating-point values are available.

This introduces a new 'id use descriptor' structure, which provides a
way to describe a particular use of an id, and which will be heavily
used in future transformations.  Describing an id use is trivial if
the use occurs in an instruction that itself generates an id, but is
less straightforward if the id of interest is used by an instruction
such as OpStore that does not have a result id.  The 'id use
descriptor' structure caters for such cases.
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index fbcac72..c1c0c1f 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -35,6 +35,7 @@
         fuzzer_pass_permute_blocks.h
         fuzzer_pass_split_blocks.h
         fuzzer_util.h
+        id_use_descriptor.h
         protobufs/spirvfuzz_protobufs.h
         pseudo_random_generator.h
         random_generator.h
@@ -45,6 +46,7 @@
         transformation_add_type_float.h
         transformation_add_type_int.h
         transformation_move_block_down.h
+        transformation_replace_boolean_constant_with_constant_binary.h
         transformation_split_block.h
         ${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.h
 
@@ -57,6 +59,7 @@
         fuzzer_pass_permute_blocks.cpp
         fuzzer_pass_split_blocks.cpp
         fuzzer_util.cpp
+        id_use_descriptor.cpp
         pseudo_random_generator.cpp
         random_generator.cpp
         transformation_add_constant_boolean.cpp
@@ -66,6 +69,7 @@
         transformation_add_type_float.cpp
         transformation_add_type_int.cpp
         transformation_move_block_down.cpp
+        transformation_replace_boolean_constant_with_constant_binary.cpp
         transformation_split_block.cpp
         ${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.cc
         )
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 20a30ba..936ffbc 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -42,8 +42,8 @@
   // Probabilities associated with applying various transformations.
   // Keep them in alphabetical order.
   uint32_t GetChanceOfAddingDeadBreak() { return chance_of_adding_dead_break_; }
-  uint32_t GetChanceOfSplittingBlock() { return chance_of_splitting_block_; }
   uint32_t GetChanceOfMovingBlockDown() { return chance_of_moving_block_down_; }
+  uint32_t GetChanceOfSplittingBlock() { return chance_of_splitting_block_; }
 
  private:
   // The source of randomness.
diff --git a/source/fuzz/id_use_descriptor.cpp b/source/fuzz/id_use_descriptor.cpp
new file mode 100644
index 0000000..33d2ca0
--- /dev/null
+++ b/source/fuzz/id_use_descriptor.cpp
@@ -0,0 +1,82 @@
+// Copyright (c) 2019 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 "source/fuzz/id_use_descriptor.h"
+
+namespace spvtools {
+namespace fuzz {
+
+opt::Instruction* transformation::FindInstruction(
+    const protobufs::IdUseDescriptor& descriptor,
+    spvtools::opt::IRContext* context) {
+  for (auto& function : *context->module()) {
+    for (auto& block : function) {
+      bool found_base = block.id() == descriptor.base_instruction_result_id();
+      uint32_t num_ignored = 0;
+      for (auto& instruction : block) {
+        if (instruction.HasResultId() &&
+            instruction.result_id() ==
+                descriptor.base_instruction_result_id()) {
+          assert(!found_base &&
+                 "It should not be possible to find the base instruction "
+                 "multiple times.");
+          found_base = true;
+          assert(num_ignored == 0 &&
+                 "The skipped instruction count should only be incremented "
+                 "after the instruction base has been found.");
+        }
+        if (found_base &&
+            instruction.opcode() == descriptor.target_instruction_opcode()) {
+          if (num_ignored == descriptor.num_opcodes_to_ignore()) {
+            if (descriptor.in_operand_index() >= instruction.NumInOperands()) {
+              return nullptr;
+            }
+            auto in_operand =
+                instruction.GetInOperand(descriptor.in_operand_index());
+            if (in_operand.type != SPV_OPERAND_TYPE_ID) {
+              return nullptr;
+            }
+            if (in_operand.words[0] != descriptor.id_of_interest()) {
+              return nullptr;
+            }
+            return &instruction;
+          }
+          num_ignored++;
+        }
+      }
+      if (found_base) {
+        // We found the base instruction, but did not find the target
+        // instruction in the same block.
+        return nullptr;
+      }
+    }
+  }
+  return nullptr;
+}
+
+protobufs::IdUseDescriptor transformation::MakeIdUseDescriptor(
+    uint32_t id_of_interest, SpvOp target_instruction_opcode,
+    uint32_t in_operand_index, uint32_t base_instruction_result_id,
+    uint32_t num_opcodes_to_ignore) {
+  protobufs::IdUseDescriptor result;
+  result.set_id_of_interest(id_of_interest);
+  result.set_target_instruction_opcode(target_instruction_opcode);
+  result.set_in_operand_index(in_operand_index);
+  result.set_base_instruction_result_id(base_instruction_result_id);
+  result.set_num_opcodes_to_ignore(num_opcodes_to_ignore);
+  return result;
+}
+
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/id_use_descriptor.h b/source/fuzz/id_use_descriptor.h
new file mode 100644
index 0000000..63016c5
--- /dev/null
+++ b/source/fuzz/id_use_descriptor.h
@@ -0,0 +1,42 @@
+// Copyright (c) 2019 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.
+
+#ifndef SOURCE_FUZZ_ID_USE_LOCATOR_H_
+#define SOURCE_FUZZ_ID_USE_LOCATOR_H_
+
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace transformation {
+
+// Looks for an instruction in |context| such that the id use represented by
+// |descriptor| is one of the operands to said instruction.  Returns |nullptr|
+// if no such instruction can be found.
+opt::Instruction* FindInstruction(const protobufs::IdUseDescriptor& descriptor,
+                                  opt::IRContext* context);
+
+// Creates an IdUseDescriptor protobuf message from the given components.
+// See the protobuf definition for details of what these components mean.
+protobufs::IdUseDescriptor MakeIdUseDescriptor(
+    uint32_t id_of_interest, SpvOp target_instruction_opcode,
+    uint32_t in_operand_index, uint32_t base_instruction_result_id,
+    uint32_t num_opcodes_to_ignore);
+
+}  // namespace transformation
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_ID_USE_LOCATOR_H_
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index bf2c3d0..f00c518 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -21,6 +21,42 @@
 
 package spvtools.fuzz.protobufs;
 
+message IdUseDescriptor {
+
+  // Describes a use of an id as an input operand to an instruction in some block
+  // of a function.
+
+  // Example:
+  //   - id_of_interest = 42
+  //   - target_instruction_opcode = OpStore
+  //   - in_operand_index = 1
+  //   - base_instruction_result_id = 50
+  //   - num_opcodes_to_ignore = 7
+  // represents a use of id 42 as input operand 1 to an OpStore instruction,
+  // such that the OpStore instruction can be found in the same basic block as
+  // the instruction with result id 50, and in particular is the 8th OpStore
+  // instruction found from instruction 50 onwards (i.e. 7 OpStore
+  // instructions are skipped).
+
+  // An id that we would like to be able to find a use of.
+  uint32 id_of_interest = 1;
+
+  // The opcode for the instruction that uses the id.
+  uint32 target_instruction_opcode = 2;
+
+  // The input operand index at which the use is expected.
+  uint32 in_operand_index = 3;
+
+  // The id of an instruction after which the instruction that contains the use
+  // is believed to occur; it might be the using instruction itself.
+  uint32 base_instruction_result_id = 4;
+
+  // The number of matching opcodes to skip over when searching for the using
+  // instruction from the base instruction.
+  uint32 num_opcodes_to_ignore = 5;
+
+}
+
 message FactSequence {
   repeated Fact fact = 1;
 }
@@ -45,6 +81,7 @@
     TransformationAddTypeFloat add_type_float = 6;
     TransformationAddTypeInt add_type_int = 7;
     TransformationAddDeadBreak add_dead_break = 8;
+    TransformationReplaceBooleanConstantWithConstantBinary replace_boolean_constant_with_constant_binary = 9;
     // Add additional option using the next available number.
   }
 }
@@ -144,6 +181,27 @@
 
 }
 
+message TransformationReplaceBooleanConstantWithConstantBinary {
+  // A transformation to capture replacing a use of a boolean constant with
+  // binary operation on two constant values
+
+  // A descriptor for the boolean constant id we would like to replace
+  IdUseDescriptor id_use_descriptor = 1;
+
+  // Id for the constant to be used on the LHS of the comparision
+  uint32 lhs_id = 2;
+
+  // Id for the constant to be used on the RHS of the comparision
+  uint32 rhs_id = 3;
+
+  // Opcode for binary operator
+  uint32 opcode = 4;
+
+  // Id that will store the result of the binary operation instruction
+  uint32 fresh_id_for_binary_operation = 5;
+
+}
+
 message TransformationSplitBlock {
 
   // A transformation that splits a basic block into two basic blocks.
diff --git a/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.cpp b/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.cpp
new file mode 100644
index 0000000..85844c5
--- /dev/null
+++ b/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.cpp
@@ -0,0 +1,282 @@
+// Copyright (c) 2019 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 "source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h"
+
+#include <cmath>
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/id_use_descriptor.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace transformation {
+
+namespace {
+
+// Given floating-point values |lhs| and |rhs|, and a floating-point binary
+// operator |binop|, returns true if it is certain that 'lhs binop rhs'
+// evaluates to |required_value|.
+template <typename T>
+bool float_binop_evaluates_to(T lhs, T rhs, SpvOp binop, bool required_value) {
+  // Infinity and NaN values are conservatively treated as out of scope.
+  if (!std::isfinite(lhs) || !std::isfinite(rhs)) {
+    return false;
+  }
+  bool binop_result;
+  // The following captures the binary operators that spirv-fuzz can actually
+  // generate when turning a boolean constant into a binary expression.
+  switch (binop) {
+    case SpvOpFOrdGreaterThanEqual:
+    case SpvOpFUnordGreaterThanEqual:
+      binop_result = (lhs >= rhs);
+      break;
+    case SpvOpFOrdGreaterThan:
+    case SpvOpFUnordGreaterThan:
+      binop_result = (lhs > rhs);
+      break;
+    case SpvOpFOrdLessThanEqual:
+    case SpvOpFUnordLessThanEqual:
+      binop_result = (lhs <= rhs);
+      break;
+    case SpvOpFOrdLessThan:
+    case SpvOpFUnordLessThan:
+      binop_result = (lhs < rhs);
+      break;
+    default:
+      return false;
+  }
+  return binop_result == required_value;
+}
+
+// Analogous to 'float_binop_evaluates_to', but for signed int values.
+template <typename T>
+bool signed_int_binop_evaluates_to(T lhs, T rhs, SpvOp binop,
+                                   bool required_value) {
+  bool binop_result;
+  switch (binop) {
+    case SpvOpSGreaterThanEqual:
+      binop_result = (lhs >= rhs);
+      break;
+    case SpvOpSGreaterThan:
+      binop_result = (lhs > rhs);
+      break;
+    case SpvOpSLessThanEqual:
+      binop_result = (lhs <= rhs);
+      break;
+    case SpvOpSLessThan:
+      binop_result = (lhs < rhs);
+      break;
+    default:
+      return false;
+  }
+  return binop_result == required_value;
+}
+
+// Analogous to 'float_binop_evaluates_to', but for unsigned int values.
+template <typename T>
+bool unsigned_int_binop_evaluates_to(T lhs, T rhs, SpvOp binop,
+                                     bool required_value) {
+  bool binop_result;
+  switch (binop) {
+    case SpvOpUGreaterThanEqual:
+      binop_result = (lhs >= rhs);
+      break;
+    case SpvOpUGreaterThan:
+      binop_result = (lhs > rhs);
+      break;
+    case SpvOpULessThanEqual:
+      binop_result = (lhs <= rhs);
+      break;
+    case SpvOpULessThan:
+      binop_result = (lhs < rhs);
+      break;
+    default:
+      return false;
+  }
+  return binop_result == required_value;
+}
+
+}  // namespace
+
+bool IsApplicable(
+    const protobufs::TransformationReplaceBooleanConstantWithConstantBinary&
+        message,
+    opt::IRContext* context, const FactManager& /*unused*/) {
+  // The id for the binary result must be fresh
+  if (!fuzzerutil::IsFreshId(context,
+                             message.fresh_id_for_binary_operation())) {
+    return false;
+  }
+
+  // The used id must be for a boolean constant
+  auto boolean_constant = context->get_def_use_mgr()->GetDef(
+      message.id_use_descriptor().id_of_interest());
+  if (!boolean_constant) {
+    return false;
+  }
+  if (!(boolean_constant->opcode() == SpvOpConstantFalse ||
+        boolean_constant->opcode() == SpvOpConstantTrue)) {
+    return false;
+  }
+
+  // The left-hand-side id must correspond to a constant instruction.
+  auto lhs_constant_inst = context->get_def_use_mgr()->GetDef(message.lhs_id());
+  if (!lhs_constant_inst) {
+    return false;
+  }
+  if (lhs_constant_inst->opcode() != SpvOpConstant) {
+    return false;
+  }
+
+  // The right-hand-side id must correspond to a constant instruction.
+  auto rhs_constant_inst = context->get_def_use_mgr()->GetDef(message.rhs_id());
+  if (!rhs_constant_inst) {
+    return false;
+  }
+  if (rhs_constant_inst->opcode() != SpvOpConstant) {
+    return false;
+  }
+
+  // The left- and right-hand side instructions must have the same type.
+  if (lhs_constant_inst->type_id() != rhs_constant_inst->type_id()) {
+    return false;
+  }
+
+  // The expression 'LHS opcode RHS' must evaluate to the boolean constant.
+  auto lhs_constant =
+      context->get_constant_mgr()->FindDeclaredConstant(message.lhs_id());
+  auto rhs_constant =
+      context->get_constant_mgr()->FindDeclaredConstant(message.rhs_id());
+  bool expected_result = (boolean_constant->opcode() == SpvOpConstantTrue);
+
+  const SpvOp binary_opcode = static_cast<SpvOp>(message.opcode());
+
+  // We consider the floating point, signed and unsigned integer cases
+  // separately.  In each case the logic is very similar.
+  if (lhs_constant->AsFloatConstant()) {
+    assert(rhs_constant->AsFloatConstant() &&
+           "Both constants should be of the same type.");
+    if (lhs_constant->type()->AsFloat()->width() == 32) {
+      if (!float_binop_evaluates_to(lhs_constant->GetFloat(),
+                                    rhs_constant->GetFloat(), binary_opcode,
+                                    expected_result)) {
+        return false;
+      }
+    } else {
+      assert(lhs_constant->type()->AsFloat()->width() == 64);
+      if (!float_binop_evaluates_to(lhs_constant->GetDouble(),
+                                    rhs_constant->GetDouble(), binary_opcode,
+                                    expected_result)) {
+        return false;
+      }
+    }
+  } else {
+    assert(lhs_constant->AsIntConstant() && "Constants should be in or float.");
+    assert(rhs_constant->AsIntConstant() &&
+           "Both constants should be of the same type.");
+    if (lhs_constant->type()->AsInteger()->IsSigned()) {
+      if (lhs_constant->type()->AsInteger()->width() == 32) {
+        if (!signed_int_binop_evaluates_to(lhs_constant->GetS32(),
+                                           rhs_constant->GetS32(),
+                                           binary_opcode, expected_result)) {
+          return false;
+        }
+      } else {
+        assert(lhs_constant->type()->AsInteger()->width() == 64);
+        if (!signed_int_binop_evaluates_to(lhs_constant->GetS64(),
+                                           rhs_constant->GetS64(),
+                                           binary_opcode, expected_result)) {
+          return false;
+        }
+      }
+    } else {
+      if (lhs_constant->type()->AsInteger()->width() == 32) {
+        if (!unsigned_int_binop_evaluates_to(lhs_constant->GetU32(),
+                                             rhs_constant->GetU32(),
+                                             binary_opcode, expected_result)) {
+          return false;
+        }
+      } else {
+        assert(lhs_constant->type()->AsInteger()->width() == 64);
+        if (!unsigned_int_binop_evaluates_to(lhs_constant->GetU64(),
+                                             rhs_constant->GetU64(),
+                                             binary_opcode, expected_result)) {
+          return false;
+        }
+      }
+    }
+  }
+
+  // The id use descriptor must identify some instruction
+  return transformation::FindInstruction(message.id_use_descriptor(),
+                                         context) != nullptr;
+}
+
+opt::Instruction* Apply(
+    const protobufs::TransformationReplaceBooleanConstantWithConstantBinary&
+        message,
+    opt::IRContext* context, FactManager* /*unused*/) {
+  opt::analysis::Bool bool_type;
+  opt::Instruction::OperandList operands = {
+      {SPV_OPERAND_TYPE_ID, {message.lhs_id()}},
+      {SPV_OPERAND_TYPE_ID, {message.rhs_id()}}};
+  auto binary_instruction = MakeUnique<opt::Instruction>(
+      context, static_cast<SpvOp>(message.opcode()),
+      context->get_type_mgr()->GetId(&bool_type),
+      message.fresh_id_for_binary_operation(), operands);
+  opt::Instruction* result = binary_instruction.get();
+  auto instruction_containing_constant_use =
+      transformation::FindInstruction(message.id_use_descriptor(), context);
+
+  // We want to insert the new instruction before the instruction that contains
+  // the use of the boolean, but we need to go backwards one more instruction if
+  // the using instruction is preceded by a merge instruction.
+  auto instruction_before_which_to_insert = instruction_containing_constant_use;
+  {
+    opt::Instruction* previous_node =
+        instruction_before_which_to_insert->PreviousNode();
+    if (previous_node && (previous_node->opcode() == SpvOpLoopMerge ||
+                          previous_node->opcode() == SpvOpSelectionMerge)) {
+      instruction_before_which_to_insert = previous_node;
+    }
+  }
+  instruction_before_which_to_insert->InsertBefore(
+      std::move(binary_instruction));
+  instruction_containing_constant_use->SetInOperand(
+      message.id_use_descriptor().in_operand_index(),
+      {message.fresh_id_for_binary_operation()});
+  fuzzerutil::UpdateModuleIdBound(context,
+                                  message.fresh_id_for_binary_operation());
+  context->InvalidateAnalysesExceptFor(opt::IRContext::Analysis::kAnalysisNone);
+  return result;
+}
+
+protobufs::TransformationReplaceBooleanConstantWithConstantBinary
+MakeTransformationReplaceBooleanConstantWithConstantBinary(
+    const protobufs::IdUseDescriptor& id_use_descriptor, uint32_t lhs_id,
+    uint32_t rhs_id, SpvOp comparison_opcode,
+    uint32_t fresh_id_for_binary_operation) {
+  protobufs::TransformationReplaceBooleanConstantWithConstantBinary result;
+  *result.mutable_id_use_descriptor() = id_use_descriptor;
+  result.set_lhs_id(lhs_id);
+  result.set_rhs_id(rhs_id);
+  result.set_opcode(comparison_opcode);
+  result.set_fresh_id_for_binary_operation(fresh_id_for_binary_operation);
+  return result;
+}
+
+}  // namespace transformation
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h b/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h
new file mode 100644
index 0000000..a6dae2a
--- /dev/null
+++ b/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h
@@ -0,0 +1,59 @@
+// Copyright (c) 2019 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.
+
+#ifndef SOURCE_FUZZ_TRANSFORMATION_REPLACE_BOOLEAN_CONSTANT_WITH_CONSTANT_BINARY_H_
+#define SOURCE_FUZZ_TRANSFORMATION_REPLACE_BOOLEAN_CONSTANT_WITH_CONSTANT_BINARY_H_
+
+#include "source/fuzz/fact_manager.h"
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace transformation {
+
+// - |message.fresh_id_for_binary_operation| must not already be used by the
+//   module.
+// - |message.id_use_descriptor| must identify a use of a boolean constant c.
+// - |message.lhs_id| and |message.rhs_id| must be the ids of constant
+//   instructions with the same type
+// - |message.opcode| must be suitable for applying to |message.lhs_id| and
+//   |message.rhs_id|, and the result must evaluate to the boolean constant c.
+bool IsApplicable(
+    const protobufs::TransformationReplaceBooleanConstantWithConstantBinary&
+        message,
+    opt::IRContext* context, const FactManager& fact_manager);
+
+// A new instruction is added before the boolean constant usage that computes
+// the result of applying |message.opcode| to |message.lhs_id| and
+// |message.rhs_id| is added, with result id
+// |message.fresh_id_for_binary_operation|.  The boolean constant usage is
+// replaced with this result id.
+opt::Instruction* Apply(
+    const protobufs::TransformationReplaceBooleanConstantWithConstantBinary&
+        message,
+    opt::IRContext* context, FactManager* fact_manager);
+
+// Helper factory to create a transformation message.
+protobufs::TransformationReplaceBooleanConstantWithConstantBinary
+MakeTransformationReplaceBooleanConstantWithConstantBinary(
+    const protobufs::IdUseDescriptor& id_use_descriptor, uint32_t lhs_id,
+    uint32_t rhs_id, SpvOp comparison_opcode,
+    uint32_t fresh_id_for_binary_operation);
+
+}  // namespace transformation
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_TRANSFORMATION_REPLACE_BOOLEAN_CONSTANT_WITH_CONSTANT_BINARY_H_
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 9578352..88635c7 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -26,6 +26,7 @@
           transformation_add_type_float_test.cpp
           transformation_add_type_int_test.cpp
           transformation_move_block_down_test.cpp
+          transformation_replace_boolean_constant_with_constant_binary_test.cpp
           transformation_split_block_test.cpp)
 
   add_spvtools_unittest(TARGET fuzz
diff --git a/test/fuzz/transformation_replace_boolean_constant_with_constant_binary_test.cpp b/test/fuzz/transformation_replace_boolean_constant_with_constant_binary_test.cpp
new file mode 100644
index 0000000..8472633
--- /dev/null
+++ b/test/fuzz/transformation_replace_boolean_constant_with_constant_binary_test.cpp
@@ -0,0 +1,630 @@
+// Copyright (c) 2019 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 "source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h"
+
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/id_use_descriptor.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationReplaceBooleanConstantWithConstantBinaryTest,
+     BasicReplacements) {
+  // The test came from the following pseudo-GLSL, where int64 and uint64 denote
+  // 64-bit integer types (they were replaced with int and uint during
+  // translation to SPIR-V, and the generated SPIR-V has been doctored to
+  // accommodate them).
+  //
+  // #version 450
+  //
+  // void main() {
+  //   double d1, d2;
+  //   d1 = 1.0;
+  //   d2 = 2.0;
+  //   float f1, f2;
+  //   f1 = 4.0;
+  //   f2 = 8.0;
+  //   int i1, i2;
+  //   i1 = 100;
+  //   i2 = 200;
+  //
+  //   uint u1, u2;
+  //   u1 = 300u;
+  //   u2 = 400u;
+  //
+  //   int64 i64_1, i64_2;
+  //   i64_1 = 500;
+  //   i64_2 = 600;
+  //
+  //   uint64 u64_1, u64_2;
+  //   u64_1 = 700u;
+  //   u64_2 = 800u;
+  //
+  //   bool b, c, d, e;
+  //   b = true;
+  //   c = false;
+  //   d = true || c;
+  //   c = c && false;
+  // }
+  std::string shader = R"(
+               OpCapability Shader
+               OpCapability Float64
+               OpCapability Int64
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource GLSL 450
+               OpName %4 "main"
+               OpName %8 "d1"
+               OpName %10 "d2"
+               OpName %14 "f1"
+               OpName %16 "f2"
+               OpName %20 "i1"
+               OpName %22 "i2"
+               OpName %26 "u1"
+               OpName %28 "u2"
+               OpName %30 "i64_1"
+               OpName %32 "i64_2"
+               OpName %34 "u64_1"
+               OpName %36 "u64_2"
+               OpName %40 "b"
+               OpName %42 "c"
+               OpName %44 "d"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 64
+          %7 = OpTypePointer Function %6
+          %9 = OpConstant %6 1
+         %11 = OpConstant %6 2
+         %12 = OpTypeFloat 32
+         %13 = OpTypePointer Function %12
+         %15 = OpConstant %12 4
+         %17 = OpConstant %12 8
+         %18 = OpTypeInt 32 1
+         %60 = OpTypeInt 64 1
+         %61 = OpTypePointer Function %60
+         %19 = OpTypePointer Function %18
+         %21 = OpConstant %18 -100
+         %23 = OpConstant %18 200
+         %24 = OpTypeInt 32 0
+         %62 = OpTypeInt 64 0
+         %63 = OpTypePointer Function %62
+         %25 = OpTypePointer Function %24
+         %27 = OpConstant %24 300
+         %29 = OpConstant %24 400
+         %31 = OpConstant %60 -600
+         %33 = OpConstant %60 -500
+         %35 = OpConstant %62 700
+         %37 = OpConstant %62 800
+         %38 = OpTypeBool
+         %39 = OpTypePointer Function %38
+         %41 = OpConstantTrue %38
+         %43 = OpConstantFalse %38
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function
+         %10 = OpVariable %7 Function
+         %14 = OpVariable %13 Function
+         %16 = OpVariable %13 Function
+         %20 = OpVariable %19 Function
+         %22 = OpVariable %19 Function
+         %26 = OpVariable %25 Function
+         %28 = OpVariable %25 Function
+         %30 = OpVariable %61 Function
+         %32 = OpVariable %61 Function
+         %34 = OpVariable %63 Function
+         %36 = OpVariable %63 Function
+         %40 = OpVariable %39 Function
+         %42 = OpVariable %39 Function
+         %44 = OpVariable %39 Function
+               OpStore %8 %9
+               OpStore %10 %11
+               OpStore %14 %15
+               OpStore %16 %17
+               OpStore %20 %21
+               OpStore %22 %23
+               OpStore %26 %27
+               OpStore %28 %29
+               OpStore %30 %31
+               OpStore %32 %33
+               OpStore %34 %35
+               OpStore %36 %37
+               OpStore %40 %41
+               OpStore %42 %43
+         %45 = OpLoad %38 %42
+         %46 = OpLogicalOr %38 %41 %45
+               OpStore %44 %46
+         %47 = OpLoad %38 %42
+         %48 = OpLogicalAnd %38 %47 %43
+               OpStore %42 %48
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_3;
+  const auto consumer = nullptr;
+  const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  FactManager fact_manager;
+
+  std::vector<protobufs::IdUseDescriptor> uses_of_true = {
+      transformation::MakeIdUseDescriptor(41, SpvOpStore, 1, 44, 12),
+      transformation::MakeIdUseDescriptor(41, SpvOpLogicalOr, 0, 46, 0)};
+
+  std::vector<protobufs::IdUseDescriptor> uses_of_false = {
+      transformation::MakeIdUseDescriptor(43, SpvOpStore, 1, 44, 13),
+      transformation::MakeIdUseDescriptor(43, SpvOpLogicalAnd, 1, 48, 0)};
+
+  const uint32_t fresh_id = 100;
+
+  std::vector<SpvOp> fp_gt_opcodes = {
+      SpvOpFOrdGreaterThan, SpvOpFOrdGreaterThanEqual, SpvOpFUnordGreaterThan,
+      SpvOpFUnordGreaterThanEqual};
+
+  std::vector<SpvOp> fp_lt_opcodes = {SpvOpFOrdLessThan, SpvOpFOrdLessThanEqual,
+                                      SpvOpFUnordLessThan,
+                                      SpvOpFUnordLessThanEqual};
+
+  std::vector<SpvOp> int_gt_opcodes = {SpvOpSGreaterThan,
+                                       SpvOpSGreaterThanEqual};
+
+  std::vector<SpvOp> int_lt_opcodes = {SpvOpSLessThan, SpvOpSLessThanEqual};
+
+  std::vector<SpvOp> uint_gt_opcodes = {SpvOpUGreaterThan,
+                                        SpvOpUGreaterThanEqual};
+
+  std::vector<SpvOp> uint_lt_opcodes = {SpvOpULessThan, SpvOpULessThanEqual};
+
+#define CHECK_OPERATOR(USE_DESCRIPTOR, LHS_ID, RHS_ID, OPCODE, FRESH_ID) \
+  ASSERT_TRUE(transformation::IsApplicable(                              \
+      transformation::                                                   \
+          MakeTransformationReplaceBooleanConstantWithConstantBinary(    \
+              USE_DESCRIPTOR, LHS_ID, RHS_ID, OPCODE, FRESH_ID),         \
+      context.get(), fact_manager));                                     \
+  ASSERT_FALSE(transformation::IsApplicable(                             \
+      transformation::                                                   \
+          MakeTransformationReplaceBooleanConstantWithConstantBinary(    \
+              USE_DESCRIPTOR, RHS_ID, LHS_ID, OPCODE, FRESH_ID),         \
+      context.get(), fact_manager));
+
+#define CHECK_TRANSFORMATION_APPLICABILITY(GT_OPCODES, LT_OPCODES, SMALL_ID, \
+                                           LARGE_ID)                         \
+  for (auto gt_opcode : GT_OPCODES) {                                        \
+    for (auto& true_use : uses_of_true) {                                    \
+      CHECK_OPERATOR(true_use, LARGE_ID, SMALL_ID, gt_opcode, fresh_id);     \
+    }                                                                        \
+    for (auto& false_use : uses_of_false) {                                  \
+      CHECK_OPERATOR(false_use, SMALL_ID, LARGE_ID, gt_opcode, fresh_id);    \
+    }                                                                        \
+  }                                                                          \
+  for (auto lt_opcode : LT_OPCODES) {                                        \
+    for (auto& true_use : uses_of_true) {                                    \
+      CHECK_OPERATOR(true_use, SMALL_ID, LARGE_ID, lt_opcode, fresh_id);     \
+    }                                                                        \
+    for (auto& false_use : uses_of_false) {                                  \
+      CHECK_OPERATOR(false_use, LARGE_ID, SMALL_ID, lt_opcode, fresh_id);    \
+    }                                                                        \
+  }
+
+  // Float
+  { CHECK_TRANSFORMATION_APPLICABILITY(fp_gt_opcodes, fp_lt_opcodes, 15, 17); }
+
+  // Double
+  { CHECK_TRANSFORMATION_APPLICABILITY(fp_gt_opcodes, fp_lt_opcodes, 9, 11); }
+
+  // Int32
+  {
+    CHECK_TRANSFORMATION_APPLICABILITY(int_gt_opcodes, int_lt_opcodes, 21, 23);
+  }
+
+  // Int64
+  {
+    CHECK_TRANSFORMATION_APPLICABILITY(int_gt_opcodes, int_lt_opcodes, 31, 33);
+  }
+
+  // Uint32
+  {
+    CHECK_TRANSFORMATION_APPLICABILITY(uint_gt_opcodes, uint_lt_opcodes, 27,
+                                       29);
+  }
+
+  // Uint64
+  {
+    CHECK_TRANSFORMATION_APPLICABILITY(uint_gt_opcodes, uint_lt_opcodes, 35,
+                                       37);
+  }
+
+  // Target id is not fresh
+  ASSERT_FALSE(transformation::IsApplicable(
+      transformation::
+          MakeTransformationReplaceBooleanConstantWithConstantBinary(
+              uses_of_true[0], 15, 17, SpvOpFOrdLessThan, 15),
+      context.get(), fact_manager));
+
+  // LHS id does not exist
+  ASSERT_FALSE(transformation::IsApplicable(
+      transformation::
+          MakeTransformationReplaceBooleanConstantWithConstantBinary(
+              uses_of_true[0], 300, 17, SpvOpFOrdLessThan, 200),
+      context.get(), fact_manager));
+
+  // RHS id does not exist
+  ASSERT_FALSE(transformation::IsApplicable(
+      transformation::
+          MakeTransformationReplaceBooleanConstantWithConstantBinary(
+              uses_of_true[0], 15, 300, SpvOpFOrdLessThan, 200),
+      context.get(), fact_manager));
+
+  // LHS and RHS ids do not match type
+  ASSERT_FALSE(transformation::IsApplicable(
+      transformation::
+          MakeTransformationReplaceBooleanConstantWithConstantBinary(
+              uses_of_true[0], 11, 17, SpvOpFOrdLessThan, 200),
+      context.get(), fact_manager));
+
+  // Opcode not appropriate
+  ASSERT_FALSE(transformation::IsApplicable(
+      transformation::
+          MakeTransformationReplaceBooleanConstantWithConstantBinary(
+              uses_of_true[0], 15, 17, SpvOpFDiv, 200),
+      context.get(), fact_manager));
+
+  auto replace_true_with_double_comparison = transformation::
+      MakeTransformationReplaceBooleanConstantWithConstantBinary(
+          uses_of_true[0], 11, 9, SpvOpFUnordGreaterThan, 100);
+  auto replace_true_with_uint32_comparison = transformation::
+      MakeTransformationReplaceBooleanConstantWithConstantBinary(
+          uses_of_true[1], 27, 29, SpvOpULessThanEqual, 101);
+  auto replace_false_with_float_comparison = transformation::
+      MakeTransformationReplaceBooleanConstantWithConstantBinary(
+          uses_of_false[0], 17, 15, SpvOpFOrdLessThan, 102);
+  auto replace_false_with_sint64_comparison = transformation::
+      MakeTransformationReplaceBooleanConstantWithConstantBinary(
+          uses_of_false[1], 33, 31, SpvOpSLessThan, 103);
+
+  ASSERT_TRUE(transformation::IsApplicable(replace_true_with_double_comparison,
+                                           context.get(), fact_manager));
+  transformation::Apply(replace_true_with_double_comparison, context.get(),
+                        &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+  ASSERT_TRUE(transformation::IsApplicable(replace_true_with_uint32_comparison,
+                                           context.get(), fact_manager));
+  transformation::Apply(replace_true_with_uint32_comparison, context.get(),
+                        &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+  ASSERT_TRUE(transformation::IsApplicable(replace_false_with_float_comparison,
+                                           context.get(), fact_manager));
+  transformation::Apply(replace_false_with_float_comparison, context.get(),
+                        &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+  ASSERT_TRUE(transformation::IsApplicable(replace_false_with_sint64_comparison,
+                                           context.get(), fact_manager));
+  transformation::Apply(replace_false_with_sint64_comparison, context.get(),
+                        &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  std::string after = R"(
+               OpCapability Shader
+               OpCapability Float64
+               OpCapability Int64
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource GLSL 450
+               OpName %4 "main"
+               OpName %8 "d1"
+               OpName %10 "d2"
+               OpName %14 "f1"
+               OpName %16 "f2"
+               OpName %20 "i1"
+               OpName %22 "i2"
+               OpName %26 "u1"
+               OpName %28 "u2"
+               OpName %30 "i64_1"
+               OpName %32 "i64_2"
+               OpName %34 "u64_1"
+               OpName %36 "u64_2"
+               OpName %40 "b"
+               OpName %42 "c"
+               OpName %44 "d"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeFloat 64
+          %7 = OpTypePointer Function %6
+          %9 = OpConstant %6 1
+         %11 = OpConstant %6 2
+         %12 = OpTypeFloat 32
+         %13 = OpTypePointer Function %12
+         %15 = OpConstant %12 4
+         %17 = OpConstant %12 8
+         %18 = OpTypeInt 32 1
+         %60 = OpTypeInt 64 1
+         %61 = OpTypePointer Function %60
+         %19 = OpTypePointer Function %18
+         %21 = OpConstant %18 -100
+         %23 = OpConstant %18 200
+         %24 = OpTypeInt 32 0
+         %62 = OpTypeInt 64 0
+         %63 = OpTypePointer Function %62
+         %25 = OpTypePointer Function %24
+         %27 = OpConstant %24 300
+         %29 = OpConstant %24 400
+         %31 = OpConstant %60 -600
+         %33 = OpConstant %60 -500
+         %35 = OpConstant %62 700
+         %37 = OpConstant %62 800
+         %38 = OpTypeBool
+         %39 = OpTypePointer Function %38
+         %41 = OpConstantTrue %38
+         %43 = OpConstantFalse %38
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function
+         %10 = OpVariable %7 Function
+         %14 = OpVariable %13 Function
+         %16 = OpVariable %13 Function
+         %20 = OpVariable %19 Function
+         %22 = OpVariable %19 Function
+         %26 = OpVariable %25 Function
+         %28 = OpVariable %25 Function
+         %30 = OpVariable %61 Function
+         %32 = OpVariable %61 Function
+         %34 = OpVariable %63 Function
+         %36 = OpVariable %63 Function
+         %40 = OpVariable %39 Function
+         %42 = OpVariable %39 Function
+         %44 = OpVariable %39 Function
+               OpStore %8 %9
+               OpStore %10 %11
+               OpStore %14 %15
+               OpStore %16 %17
+               OpStore %20 %21
+               OpStore %22 %23
+               OpStore %26 %27
+               OpStore %28 %29
+               OpStore %30 %31
+               OpStore %32 %33
+               OpStore %34 %35
+               OpStore %36 %37
+        %100 = OpFUnordGreaterThan %38 %11 %9
+               OpStore %40 %100
+        %102 = OpFOrdLessThan %38 %17 %15
+               OpStore %42 %102
+         %45 = OpLoad %38 %42
+        %101 = OpULessThanEqual %38 %27 %29
+         %46 = OpLogicalOr %38 %101 %45
+               OpStore %44 %46
+         %47 = OpLoad %38 %42
+        %103 = OpSLessThan %38 %33 %31
+         %48 = OpLogicalAnd %38 %47 %103
+               OpStore %42 %48
+               OpReturn
+               OpFunctionEnd
+  )";
+  ASSERT_TRUE(IsEqual(env, after, context.get()));
+
+  if (std::numeric_limits<double>::has_quiet_NaN) {
+    double quiet_nan_double = std::numeric_limits<double>::quiet_NaN();
+    uint32_t words[2];
+    memcpy(words, &quiet_nan_double, sizeof(double));
+    opt::Instruction::OperandList operands = {
+        {SPV_OPERAND_TYPE_LITERAL_INTEGER, {words[0]}},
+        {SPV_OPERAND_TYPE_LITERAL_INTEGER, {words[1]}}};
+    context->module()->AddGlobalValue(MakeUnique<opt::Instruction>(
+        context.get(), SpvOpConstant, 6, 200, operands));
+    fuzzerutil::UpdateModuleIdBound(context.get(), 200);
+    ASSERT_TRUE(IsValid(env, context.get()));
+    // The transformation is not applicable because %200 is NaN.
+    ASSERT_FALSE(transformation::IsApplicable(
+        transformation::
+            MakeTransformationReplaceBooleanConstantWithConstantBinary(
+                uses_of_true[0], 11, 200, SpvOpFOrdLessThan, 300),
+        context.get(), fact_manager));
+  }
+  if (std::numeric_limits<double>::has_infinity) {
+    double positive_infinity_double = std::numeric_limits<double>::infinity();
+    uint32_t words[2];
+    memcpy(words, &positive_infinity_double, sizeof(double));
+    opt::Instruction::OperandList operands = {
+        {SPV_OPERAND_TYPE_LITERAL_INTEGER, {words[0]}},
+        {SPV_OPERAND_TYPE_LITERAL_INTEGER, {words[1]}}};
+    context->module()->AddGlobalValue(MakeUnique<opt::Instruction>(
+        context.get(), SpvOpConstant, 6, 201, operands));
+    fuzzerutil::UpdateModuleIdBound(context.get(), 201);
+    ASSERT_TRUE(IsValid(env, context.get()));
+    // Even though the double constant %11 is less than the infinity %201, the
+    // transformation is restricted to only apply to finite values.
+    ASSERT_FALSE(transformation::IsApplicable(
+        transformation::
+            MakeTransformationReplaceBooleanConstantWithConstantBinary(
+                uses_of_true[0], 11, 201, SpvOpFOrdLessThan, 300),
+        context.get(), fact_manager));
+  }
+  if (std::numeric_limits<float>::has_infinity) {
+    float positive_infinity_float = std::numeric_limits<float>::infinity();
+    float negative_infinity_float = -1 * positive_infinity_float;
+    uint32_t words_positive_infinity[1];
+    uint32_t words_negative_infinity[1];
+    memcpy(words_positive_infinity, &positive_infinity_float, sizeof(float));
+    memcpy(words_negative_infinity, &negative_infinity_float, sizeof(float));
+    opt::Instruction::OperandList operands_positive_infinity = {
+        {SPV_OPERAND_TYPE_LITERAL_INTEGER, {words_positive_infinity[0]}}};
+    context->module()->AddGlobalValue(MakeUnique<opt::Instruction>(
+        context.get(), SpvOpConstant, 12, 202, operands_positive_infinity));
+    fuzzerutil::UpdateModuleIdBound(context.get(), 202);
+    opt::Instruction::OperandList operands = {
+        {SPV_OPERAND_TYPE_LITERAL_INTEGER, {words_negative_infinity[0]}}};
+    context->module()->AddGlobalValue(MakeUnique<opt::Instruction>(
+        context.get(), SpvOpConstant, 12, 203, operands));
+    fuzzerutil::UpdateModuleIdBound(context.get(), 203);
+    ASSERT_TRUE(IsValid(env, context.get()));
+    // Even though the negative infinity at %203 is less than the positive
+    // infinity %202, the transformation is restricted to only apply to finite
+    // values.
+    ASSERT_FALSE(transformation::IsApplicable(
+        transformation::
+            MakeTransformationReplaceBooleanConstantWithConstantBinary(
+                uses_of_true[0], 203, 202, SpvOpFOrdLessThan, 300),
+        context.get(), fact_manager));
+  }
+}
+
+TEST(TransformationReplaceBooleanConstantWithConstantBinaryTest,
+     MergeInstructions) {
+  // The test came from the following GLSL:
+  //
+  // void main() {
+  //   int x = 1;
+  //   int y = 2;
+  //   if (true) {
+  //     x = 2;
+  //   }
+  //   while(false) {
+  //     y = 2;
+  //   }
+  // }
+
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource GLSL 450
+               OpName %4 "main"
+               OpName %8 "x"
+               OpName %10 "y"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypePointer Function %6
+          %9 = OpConstant %6 1
+         %11 = OpConstant %6 2
+         %12 = OpTypeBool
+         %13 = OpConstantTrue %12
+         %21 = OpConstantFalse %12
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function
+         %10 = OpVariable %7 Function
+               OpStore %8 %9
+               OpStore %10 %11
+               OpSelectionMerge %15 None
+               OpBranchConditional %13 %14 %15
+         %14 = OpLabel
+               OpStore %8 %11
+               OpBranch %15
+         %15 = OpLabel
+               OpBranch %16
+         %16 = OpLabel
+               OpLoopMerge %18 %19 None
+               OpBranchConditional %21 %17 %18
+         %17 = OpLabel
+               OpStore %10 %11
+               OpBranch %19
+         %19 = OpLabel
+               OpBranch %16
+         %18 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_3;
+  const auto consumer = nullptr;
+  const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  FactManager fact_manager;
+
+  auto use_of_true_in_if =
+      transformation::MakeIdUseDescriptor(13, SpvOpBranchConditional, 0, 10, 0);
+  auto use_of_false_in_while =
+      transformation::MakeIdUseDescriptor(21, SpvOpBranchConditional, 0, 16, 0);
+
+  auto replacement_1 = transformation::
+      MakeTransformationReplaceBooleanConstantWithConstantBinary(
+          use_of_true_in_if, 9, 11, SpvOpSLessThan, 100);
+  auto replacement_2 = transformation::
+      MakeTransformationReplaceBooleanConstantWithConstantBinary(
+          use_of_false_in_while, 9, 11, SpvOpSGreaterThanEqual, 101);
+
+  ASSERT_TRUE(
+      transformation::IsApplicable(replacement_1, context.get(), fact_manager));
+  transformation::Apply(replacement_1, context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  ASSERT_TRUE(
+      transformation::IsApplicable(replacement_2, context.get(), fact_manager));
+  transformation::Apply(replacement_2, context.get(), &fact_manager);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  std::string after = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource GLSL 450
+               OpName %4 "main"
+               OpName %8 "x"
+               OpName %10 "y"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypePointer Function %6
+          %9 = OpConstant %6 1
+         %11 = OpConstant %6 2
+         %12 = OpTypeBool
+         %13 = OpConstantTrue %12
+         %21 = OpConstantFalse %12
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function
+         %10 = OpVariable %7 Function
+               OpStore %8 %9
+               OpStore %10 %11
+        %100 = OpSLessThan %12 %9 %11
+               OpSelectionMerge %15 None
+               OpBranchConditional %100 %14 %15
+         %14 = OpLabel
+               OpStore %8 %11
+               OpBranch %15
+         %15 = OpLabel
+               OpBranch %16
+         %16 = OpLabel
+        %101 = OpSGreaterThanEqual %12 %9 %11
+               OpLoopMerge %18 %19 None
+               OpBranchConditional %101 %17 %18
+         %17 = OpLabel
+               OpStore %10 %11
+               OpBranch %19
+         %19 = OpLabel
+               OpBranch %16
+         %18 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  ASSERT_TRUE(IsEqual(env, after, context.get()));
+}
+
+}  // namespace
+}  // namespace fuzz
+}  // namespace spvtools