diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 7166d5c..330bbf0 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -29,6 +29,7 @@
   )
 
   set(SPIRV_TOOLS_FUZZ_SOURCES
+        call_graph.h
         data_descriptor.h
         equivalence_relation.h
         fact_manager.h
@@ -40,6 +41,7 @@
         fuzzer_pass_add_dead_blocks.h
         fuzzer_pass_add_dead_breaks.h
         fuzzer_pass_add_dead_continues.h
+        fuzzer_pass_add_function_calls.h
         fuzzer_pass_add_global_variables.h
         fuzzer_pass_add_loads.h
         fuzzer_pass_add_local_variables.h
@@ -92,6 +94,7 @@
         transformation_composite_construct.h
         transformation_composite_extract.h
         transformation_copy_object.h
+        transformation_function_call.h
         transformation_load.h
         transformation_merge_blocks.h
         transformation_move_block_down.h
@@ -109,6 +112,7 @@
         uniform_buffer_element_descriptor.h
         ${CMAKE_CURRENT_BINARY_DIR}/protobufs/spvtoolsfuzz.pb.h
 
+        call_graph.cpp
         data_descriptor.cpp
         fact_manager.cpp
         force_render_red.cpp
@@ -119,6 +123,7 @@
         fuzzer_pass_add_dead_blocks.cpp
         fuzzer_pass_add_dead_breaks.cpp
         fuzzer_pass_add_dead_continues.cpp
+        fuzzer_pass_add_function_calls.cpp
         fuzzer_pass_add_global_variables.cpp
         fuzzer_pass_add_loads.cpp
         fuzzer_pass_add_local_variables.cpp
@@ -170,6 +175,7 @@
         transformation_composite_construct.cpp
         transformation_composite_extract.cpp
         transformation_copy_object.cpp
+        transformation_function_call.cpp
         transformation_load.cpp
         transformation_merge_blocks.cpp
         transformation_move_block_down.cpp
diff --git a/source/fuzz/call_graph.cpp b/source/fuzz/call_graph.cpp
new file mode 100644
index 0000000..15416fe
--- /dev/null
+++ b/source/fuzz/call_graph.cpp
@@ -0,0 +1,81 @@
+// Copyright (c) 2020 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/call_graph.h"
+
+#include <queue>
+
+namespace spvtools {
+namespace fuzz {
+
+CallGraph::CallGraph(opt::IRContext* context) {
+  // Initialize function in-degree and call graph edges to 0 and empty.
+  for (auto& function : *context->module()) {
+    function_in_degree_[function.result_id()] = 0;
+    call_graph_edges_[function.result_id()] = std::set<uint32_t>();
+  }
+
+  // Consider every function.
+  for (auto& function : *context->module()) {
+    // Avoid considering the same callee of this function multiple times by
+    // recording known callees.
+    std::set<uint32_t> known_callees;
+    // Consider every function call instruction in every block.
+    for (auto& block : function) {
+      for (auto& instruction : block) {
+        if (instruction.opcode() != SpvOpFunctionCall) {
+          continue;
+        }
+        // Get the id of the function being called.
+        uint32_t callee = instruction.GetSingleWordInOperand(0);
+        if (known_callees.count(callee)) {
+          // We have already considered a call to this function - ignore it.
+          continue;
+        }
+        // Increase the callee's in-degree and add an edge to the call graph.
+        function_in_degree_[callee]++;
+        call_graph_edges_[function.result_id()].insert(callee);
+        // Mark the callee as 'known'.
+        known_callees.insert(callee);
+      }
+    }
+  }
+}
+
+void CallGraph::PushDirectCallees(uint32_t function_id,
+                                  std::queue<uint32_t>* queue) const {
+  for (auto callee : GetDirectCallees(function_id)) {
+    queue->push(callee);
+  }
+}
+
+std::set<uint32_t> CallGraph::GetIndirectCallees(uint32_t function_id) const {
+  std::set<uint32_t> result;
+  std::queue<uint32_t> queue;
+  PushDirectCallees(function_id, &queue);
+
+  while (!queue.empty()) {
+    auto next = queue.front();
+    queue.pop();
+    if (result.count(next)) {
+      continue;
+    }
+    result.insert(next);
+    PushDirectCallees(next, &queue);
+  }
+  return result;
+}
+
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/call_graph.h b/source/fuzz/call_graph.h
new file mode 100644
index 0000000..14cd23b
--- /dev/null
+++ b/source/fuzz/call_graph.h
@@ -0,0 +1,62 @@
+// Copyright (c) 2020 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_CALL_GRAPH_H_
+#define SOURCE_FUZZ_CALL_GRAPH_H_
+
+#include <map>
+#include <set>
+
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Represents the acyclic call graph of a SPIR-V module.
+class CallGraph {
+ public:
+  // Creates a call graph corresponding to the given SPIR-V module.
+  explicit CallGraph(opt::IRContext* context);
+
+  // Returns a mapping from each function to its number of distinct callers.
+  const std::map<uint32_t, uint32_t>& GetFunctionInDegree() const {
+    return function_in_degree_;
+  }
+
+  // Returns the ids of the functions that |function_id| directly invokes.
+  const std::set<uint32_t>& GetDirectCallees(uint32_t function_id) const {
+    return call_graph_edges_.at(function_id);
+  }
+
+  // Returns the ids of the functions that |function_id| directly or indirectly
+  // invokes.
+  std::set<uint32_t> GetIndirectCallees(uint32_t function_id) const;
+
+ private:
+  // Pushes the direct callees of |function_id| on to |queue|.
+  void PushDirectCallees(uint32_t function_id,
+                         std::queue<uint32_t>* queue) const;
+
+  // Maps each function id to the ids of its immediate callees.
+  std::map<uint32_t, std::set<uint32_t>> call_graph_edges_;
+
+  // For each function id, stores the number of distinct functions that call
+  // the function.
+  std::map<uint32_t, uint32_t> function_in_degree_;
+};
+
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_CALL_GRAPH_H_
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index c66d8e5..a427619 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -25,6 +25,7 @@
 #include "source/fuzz/fuzzer_pass_add_dead_blocks.h"
 #include "source/fuzz/fuzzer_pass_add_dead_breaks.h"
 #include "source/fuzz/fuzzer_pass_add_dead_continues.h"
+#include "source/fuzz/fuzzer_pass_add_function_calls.h"
 #include "source/fuzz/fuzzer_pass_add_global_variables.h"
 #include "source/fuzz/fuzzer_pass_add_loads.h"
 #include "source/fuzz/fuzzer_pass_add_local_variables.h"
@@ -195,6 +196,9 @@
     MaybeAddPass<FuzzerPassAddDeadContinues>(&passes, ir_context.get(),
                                              &fact_manager, &fuzzer_context,
                                              transformation_sequence_out);
+    MaybeAddPass<FuzzerPassAddFunctionCalls>(&passes, ir_context.get(),
+                                             &fact_manager, &fuzzer_context,
+                                             transformation_sequence_out);
     MaybeAddPass<FuzzerPassAddGlobalVariables>(&passes, ir_context.get(),
                                                &fact_manager, &fuzzer_context,
                                                transformation_sequence_out);
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index b84227e..a434661 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -44,6 +44,7 @@
                                                                             90};
 const std::pair<uint32_t, uint32_t> kChanceOfAdjustingSelectionControl = {20,
                                                                           90};
+const std::pair<uint32_t, uint32_t> kChanceOfCallingFunction = {1, 10};
 const std::pair<uint32_t, uint32_t> kChanceOfChoosingStructTypeVsArrayType = {
     20, 80};
 const std::pair<uint32_t, uint32_t> kChanceOfConstructingComposite = {20, 50};
@@ -112,6 +113,8 @@
       ChooseBetweenMinAndMax(kChanceOfAdjustingMemoryOperandsMask);
   chance_of_adjusting_selection_control_ =
       ChooseBetweenMinAndMax(kChanceOfAdjustingSelectionControl);
+  chance_of_calling_function_ =
+      ChooseBetweenMinAndMax(kChanceOfCallingFunction);
   chance_of_choosing_struct_type_vs_array_type_ =
       ChooseBetweenMinAndMax(kChanceOfChoosingStructTypeVsArrayType);
   chance_of_constructing_composite_ =
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 21f8a62..1d1245c 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -46,12 +46,22 @@
   // method, and which must be non-empty.  Typically 'HasSizeMethod' will be an
   // std::vector.
   template <typename HasSizeMethod>
-  uint32_t RandomIndex(const HasSizeMethod& sequence) {
+  uint32_t RandomIndex(const HasSizeMethod& sequence) const {
     assert(sequence.size() > 0);
     return random_generator_->RandomUint32(
         static_cast<uint32_t>(sequence.size()));
   }
 
+  // Selects a random index into |sequence|, removes the element at that index
+  // and returns it.
+  template <typename T>
+  T RemoveAtRandomIndex(std::vector<T>* sequence) const {
+    uint32_t index = RandomIndex(*sequence);
+    T result = sequence->at(index);
+    sequence->erase(sequence->begin() + index);
+    return result;
+  }
+
   // Yields an id that is guaranteed not to be used in the module being fuzzed,
   // or to have been issued before.
   uint32_t GetFreshId();
@@ -98,6 +108,7 @@
   uint32_t GetChanceOfAdjustingSelectionControl() {
     return chance_of_adjusting_selection_control_;
   }
+  uint32_t GetChanceOfCallingFunction() { return chance_of_calling_function_; }
   uint32_t GetChanceOfChoosingStructTypeVsArrayType() {
     return chance_of_choosing_struct_type_vs_array_type_;
   }
@@ -167,6 +178,7 @@
   uint32_t chance_of_adjusting_loop_control_;
   uint32_t chance_of_adjusting_memory_operands_mask_;
   uint32_t chance_of_adjusting_selection_control_;
+  uint32_t chance_of_calling_function_;
   uint32_t chance_of_choosing_struct_type_vs_array_type_;
   uint32_t chance_of_constructing_composite_;
   uint32_t chance_of_copying_object_;
diff --git a/source/fuzz/fuzzer_pass.cpp b/source/fuzz/fuzzer_pass.cpp
index 40eb3bd..1ecfa8d 100644
--- a/source/fuzz/fuzzer_pass.cpp
+++ b/source/fuzz/fuzzer_pass.cpp
@@ -41,10 +41,10 @@
 FuzzerPass::~FuzzerPass() = default;
 
 std::vector<opt::Instruction*> FuzzerPass::FindAvailableInstructions(
-    const opt::Function& function, opt::BasicBlock* block,
-    opt::BasicBlock::iterator inst_it,
+    opt::Function* function, opt::BasicBlock* block,
+    const opt::BasicBlock::iterator& inst_it,
     std::function<bool(opt::IRContext*, opt::Instruction*)>
-        instruction_is_relevant) {
+        instruction_is_relevant) const {
   // TODO(afd) The following is (relatively) simple, but may end up being
   //  prohibitively inefficient, as it walks the whole dominator tree for
   //  every instruction that is considered.
@@ -57,6 +57,14 @@
     }
   }
 
+  // Consider all function parameters
+  function->ForEachParam(
+      [this, &instruction_is_relevant, &result](opt::Instruction* param) {
+        if (instruction_is_relevant(GetIRContext(), param)) {
+          result.push_back(param);
+        }
+      });
+
   // Consider all previous instructions in this block
   for (auto prev_inst_it = block->begin(); prev_inst_it != inst_it;
        ++prev_inst_it) {
@@ -67,7 +75,7 @@
 
   // Walk the dominator tree to consider all instructions from dominating
   // blocks
-  auto dominator_analysis = GetIRContext()->GetDominatorAnalysis(&function);
+  auto dominator_analysis = GetIRContext()->GetDominatorAnalysis(function);
   for (auto next_dominator = dominator_analysis->ImmediateDominator(block);
        next_dominator != nullptr;
        next_dominator =
@@ -83,7 +91,7 @@
 
 void FuzzerPass::MaybeAddTransformationBeforeEachInstruction(
     std::function<
-        void(const opt::Function& function, opt::BasicBlock* block,
+        void(opt::Function* function, opt::BasicBlock* block,
              opt::BasicBlock::iterator inst_it,
              const protobufs::InstructionDescriptor& instruction_descriptor)>
         maybe_apply_transformation) {
@@ -125,7 +133,7 @@
 
         // Invoke the provided function, which might apply a transformation.
         maybe_apply_transformation(
-            function, &block, inst_it,
+            &function, &block, inst_it,
             MakeInstructionDescriptor(
                 base, opcode,
                 skip_count.count(opcode) ? skip_count.at(opcode) : 0));
diff --git a/source/fuzz/fuzzer_pass.h b/source/fuzz/fuzzer_pass.h
index 4b78f29..6853179 100644
--- a/source/fuzz/fuzzer_pass.h
+++ b/source/fuzz/fuzzer_pass.h
@@ -61,10 +61,10 @@
   // |instruction_is_relevant| predicate.  This, for instance, could ignore all
   // instructions that have a particular decoration.
   std::vector<opt::Instruction*> FindAvailableInstructions(
-      const opt::Function& function, opt::BasicBlock* block,
-      opt::BasicBlock::iterator inst_it,
+      opt::Function* function, opt::BasicBlock* block,
+      const opt::BasicBlock::iterator& inst_it,
       std::function<bool(opt::IRContext*, opt::Instruction*)>
-          instruction_is_relevant);
+          instruction_is_relevant) const;
 
   // A helper method that iterates through each instruction in each block, at
   // all times tracking an instruction descriptor that allows the latest
@@ -84,7 +84,7 @@
   // apply it.
   void MaybeAddTransformationBeforeEachInstruction(
       std::function<
-          void(const opt::Function& function, opt::BasicBlock* block,
+          void(opt::Function* function, opt::BasicBlock* block,
                opt::BasicBlock::iterator inst_it,
                const protobufs::InstructionDescriptor& instruction_descriptor)>
           maybe_apply_transformation);
diff --git a/source/fuzz/fuzzer_pass_add_function_calls.cpp b/source/fuzz/fuzzer_pass_add_function_calls.cpp
new file mode 100644
index 0000000..c89ae51
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_add_function_calls.cpp
@@ -0,0 +1,247 @@
+// Copyright (c) 2020 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/fuzzer_pass_add_function_calls.h"
+
+#include "source/fuzz/call_graph.h"
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/transformation_add_global_variable.h"
+#include "source/fuzz/transformation_add_local_variable.h"
+#include "source/fuzz/transformation_function_call.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassAddFunctionCalls::FuzzerPassAddFunctionCalls(
+    opt::IRContext* ir_context, FactManager* fact_manager,
+    FuzzerContext* fuzzer_context,
+    protobufs::TransformationSequence* transformations)
+    : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {}
+
+FuzzerPassAddFunctionCalls::~FuzzerPassAddFunctionCalls() = default;
+
+void FuzzerPassAddFunctionCalls::Apply() {
+  MaybeAddTransformationBeforeEachInstruction(
+      [this](opt::Function* function, opt::BasicBlock* block,
+             opt::BasicBlock::iterator inst_it,
+             const protobufs::InstructionDescriptor& instruction_descriptor)
+          -> void {
+        // Check whether it is legitimate to insert a function call before the
+        // instruction.
+        if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(SpvOpFunctionCall,
+                                                          inst_it)) {
+          return;
+        }
+
+        // Randomly decide whether to try inserting a function call here.
+        if (!GetFuzzerContext()->ChoosePercentage(
+                GetFuzzerContext()->GetChanceOfCallingFunction())) {
+          return;
+        }
+
+        // Compute the module's call graph - we don't cache it since it may
+        // change each time we apply a transformation.  If this proves to be
+        // a bottleneck the call graph data structure could be made updatable.
+        CallGraph call_graph(GetIRContext());
+
+        // Gather all the non-entry point functions different from this
+        // function.  It is important to ignore entry points as a function
+        // cannot be an entry point and the target of an OpFunctionCall
+        // instruction.  We ignore this function to avoid direct recursion.
+        std::vector<opt::Function*> candidate_functions;
+        for (auto& other_function : *GetIRContext()->module()) {
+          if (&other_function != function &&
+              !TransformationFunctionCall::FunctionIsEntryPoint(
+                  GetIRContext(), other_function.result_id())) {
+            candidate_functions.push_back(&other_function);
+          }
+        }
+
+        // Choose a function to call, at random, by considering candidate
+        // functions until a suitable one is found.
+        opt::Function* chosen_function = nullptr;
+        while (!candidate_functions.empty()) {
+          opt::Function* candidate_function =
+              GetFuzzerContext()->RemoveAtRandomIndex(&candidate_functions);
+          if (!GetFactManager()->BlockIsDead(block->id()) &&
+              !GetFactManager()->FunctionIsLivesafe(
+                  candidate_function->result_id())) {
+            // Unless in a dead block, only livesafe functions can be invoked
+            continue;
+          }
+          if (call_graph.GetIndirectCallees(candidate_function->result_id())
+                  .count(function->result_id())) {
+            // Calling this function could lead to indirect recursion
+            continue;
+          }
+          chosen_function = candidate_function;
+          break;
+        }
+
+        if (!chosen_function) {
+          // No suitable function was found to call.  (This can happen, for
+          // instance, if the current function is the only function in the
+          // module.)
+          return;
+        }
+
+        ApplyTransformation(TransformationFunctionCall(
+            GetFuzzerContext()->GetFreshId(), chosen_function->result_id(),
+            ChooseFunctionCallArguments(*chosen_function, function, block,
+                                        inst_it),
+            instruction_descriptor));
+      });
+}
+
+std::map<uint32_t, std::vector<opt::Instruction*>>
+FuzzerPassAddFunctionCalls::GetAvailableInstructionsSuitableForActualParameters(
+    opt::Function* function, opt::BasicBlock* block,
+    const opt::BasicBlock::iterator& inst_it) {
+  // Find all instructions in scope that could potentially be used as actual
+  // parameters.  Weed out unsuitable pointer arguments immediately.
+  std::vector<opt::Instruction*> potentially_suitable_instructions =
+      FindAvailableInstructions(
+          function, block, inst_it,
+          [this, block](opt::IRContext* context,
+                        opt::Instruction* inst) -> bool {
+            if (!inst->HasResultId() || !inst->type_id()) {
+              // An instruction needs a result id and type in order
+              // to be suitable as an actual parameter.
+              return false;
+            }
+            if (context->get_def_use_mgr()->GetDef(inst->type_id())->opcode() ==
+                SpvOpTypePointer) {
+              switch (inst->opcode()) {
+                case SpvOpFunctionParameter:
+                case SpvOpVariable:
+                  // Function parameters and variables are the only
+                  // kinds of pointer that can be used as actual
+                  // parameters.
+                  break;
+                default:
+                  return false;
+              }
+              if (!GetFactManager()->BlockIsDead(block->id()) &&
+                  !GetFactManager()->PointeeValueIsIrrelevant(
+                      inst->result_id())) {
+                // We can only pass a pointer as an actual parameter
+                // if the pointee value for the pointer is irrelevant,
+                // or if the block from which we would make the
+                // function call is dead.
+                return false;
+              }
+            }
+            return true;
+          });
+
+  // Group all the instructions that are potentially viable as function actual
+  // parameters by their result types.
+  std::map<uint32_t, std::vector<opt::Instruction*>> result;
+  for (auto inst : potentially_suitable_instructions) {
+    if (result.count(inst->type_id()) == 0) {
+      // This is the first instruction of this type we have seen, so populate
+      // the map with an entry.
+      result.insert({inst->type_id(), {}});
+    }
+    // Add the instruction to the sequence of instructions already associated
+    // with this type.
+    result.at(inst->type_id()).push_back(inst);
+  }
+  return result;
+}
+
+std::vector<uint32_t> FuzzerPassAddFunctionCalls::ChooseFunctionCallArguments(
+    const opt::Function& callee, opt::Function* caller_function,
+    opt::BasicBlock* caller_block,
+    const opt::BasicBlock::iterator& caller_inst_it) {
+  auto type_to_available_instructions =
+      GetAvailableInstructionsSuitableForActualParameters(
+          caller_function, caller_block, caller_inst_it);
+
+  opt::Instruction* function_type = GetIRContext()->get_def_use_mgr()->GetDef(
+      callee.DefInst().GetSingleWordInOperand(1));
+  assert(function_type->opcode() == SpvOpTypeFunction &&
+         "The function type does not have the expected opcode.");
+  std::vector<uint32_t> result;
+  for (uint32_t arg_index = 1; arg_index < function_type->NumInOperands();
+       arg_index++) {
+    auto arg_type_id =
+        GetIRContext()
+            ->get_def_use_mgr()
+            ->GetDef(function_type->GetSingleWordInOperand(arg_index))
+            ->result_id();
+    if (type_to_available_instructions.count(arg_type_id)) {
+      std::vector<opt::Instruction*>& candidate_arguments =
+          type_to_available_instructions.at(arg_type_id);
+      // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3177) The value
+      //  selected here is arbitrary.  We should consider adding this
+      //  information as a fact so that the passed parameter could be
+      //  transformed/changed.
+      result.push_back(candidate_arguments[GetFuzzerContext()->RandomIndex(
+                                               candidate_arguments)]
+                           ->result_id());
+    } else {
+      // We don't have a suitable id in scope to pass, so we must make
+      // something up.
+      auto type_instruction =
+          GetIRContext()->get_def_use_mgr()->GetDef(arg_type_id);
+
+      if (type_instruction->opcode() == SpvOpTypePointer) {
+        // In the case of a pointer, we make a new variable, at function
+        // or global scope depending on the storage class of the
+        // pointer.
+
+        // Get a fresh id for the new variable.
+        uint32_t fresh_variable_id = GetFuzzerContext()->GetFreshId();
+
+        // The id of this variable is what we pass as the parameter to
+        // the call.
+        result.push_back(fresh_variable_id);
+
+        // Now bring the variable into existence.
+        if (type_instruction->GetSingleWordInOperand(0) ==
+            SpvStorageClassFunction) {
+          // Add a new zero-initialized local variable to the current
+          // function, noting that its pointee value is irrelevant.
+          ApplyTransformation(TransformationAddLocalVariable(
+              fresh_variable_id, arg_type_id, caller_function->result_id(),
+              FindOrCreateZeroConstant(
+                  type_instruction->GetSingleWordInOperand(1)),
+              true));
+        } else {
+          assert(type_instruction->GetSingleWordInOperand(0) ==
+                     SpvStorageClassPrivate &&
+                 "Only Function and Private storage classes are "
+                 "supported at present.");
+          // Add a new zero-initialized global variable to the module,
+          // noting that its pointee value is irrelevant.
+          ApplyTransformation(TransformationAddGlobalVariable(
+              fresh_variable_id, arg_type_id,
+              FindOrCreateZeroConstant(
+                  type_instruction->GetSingleWordInOperand(1)),
+              true));
+        }
+      } else {
+        // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3177): We use
+        //  constant zero for the parameter, but could consider adding a fact
+        //  to allow further passes to obfuscate it.
+        result.push_back(FindOrCreateZeroConstant(arg_type_id));
+      }
+    }
+  }
+  return result;
+}
+
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_add_function_calls.h b/source/fuzz/fuzzer_pass_add_function_calls.h
new file mode 100644
index 0000000..5d184fd
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_add_function_calls.h
@@ -0,0 +1,58 @@
+// Copyright (c) 2020 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_FUZZER_PASS_ADD_FUNCTION_CALLS_H_
+#define SOURCE_FUZZ_FUZZER_PASS_ADD_FUNCTION_CALLS_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// Fuzzer pass that adds calls at random to (a) livesafe functions, from
+// anywhere, and (b) any functions, from dead blocks.
+class FuzzerPassAddFunctionCalls : public FuzzerPass {
+ public:
+  FuzzerPassAddFunctionCalls(
+      opt::IRContext* ir_context, FactManager* fact_manager,
+      FuzzerContext* fuzzer_context,
+      protobufs::TransformationSequence* transformations);
+
+  ~FuzzerPassAddFunctionCalls();
+
+  void Apply() override;
+
+ private:
+  // Identify all instructions available at |instr_it|, in block |block| of
+  // |function|, that are potentially suitable as function call actual
+  // parameters.  The results are grouped by type.
+  std::map<uint32_t, std::vector<opt::Instruction*>>
+  GetAvailableInstructionsSuitableForActualParameters(
+      opt::Function* function, opt::BasicBlock* block,
+      const opt::BasicBlock::iterator& inst_it);
+
+  // Randomly chooses suitable arguments to invoke |callee| right before
+  // instruction |caller_inst_it| of block |caller_block| in |caller_function|,
+  // based on both existing available instructions and the addition of new
+  // instructions to the module.
+  std::vector<uint32_t> ChooseFunctionCallArguments(
+      const opt::Function& callee, opt::Function* caller_function,
+      opt::BasicBlock* caller_block,
+      const opt::BasicBlock::iterator& caller_inst_it);
+};
+
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_FUZZER_PASS_ADD_FUNCTION_CALLS_H_
diff --git a/source/fuzz/fuzzer_pass_add_loads.cpp b/source/fuzz/fuzzer_pass_add_loads.cpp
index 7509bce..2fe1220 100644
--- a/source/fuzz/fuzzer_pass_add_loads.cpp
+++ b/source/fuzz/fuzzer_pass_add_loads.cpp
@@ -30,7 +30,7 @@
 
 void FuzzerPassAddLoads::Apply() {
   MaybeAddTransformationBeforeEachInstruction(
-      [this](const opt::Function& function, opt::BasicBlock* block,
+      [this](opt::Function* function, opt::BasicBlock* block,
              opt::BasicBlock::iterator inst_it,
              const protobufs::InstructionDescriptor& instruction_descriptor)
           -> void {
diff --git a/source/fuzz/fuzzer_pass_add_stores.cpp b/source/fuzz/fuzzer_pass_add_stores.cpp
index 120c473..d2c7b3d 100644
--- a/source/fuzz/fuzzer_pass_add_stores.cpp
+++ b/source/fuzz/fuzzer_pass_add_stores.cpp
@@ -30,7 +30,7 @@
 
 void FuzzerPassAddStores::Apply() {
   MaybeAddTransformationBeforeEachInstruction(
-      [this](const opt::Function& function, opt::BasicBlock* block,
+      [this](opt::Function* function, opt::BasicBlock* block,
              opt::BasicBlock::iterator inst_it,
              const protobufs::InstructionDescriptor& instruction_descriptor)
           -> void {
diff --git a/source/fuzz/fuzzer_pass_construct_composites.cpp b/source/fuzz/fuzzer_pass_construct_composites.cpp
index ff0adab..e160302 100644
--- a/source/fuzz/fuzzer_pass_construct_composites.cpp
+++ b/source/fuzz/fuzzer_pass_construct_composites.cpp
@@ -44,7 +44,7 @@
 
   MaybeAddTransformationBeforeEachInstruction(
       [this, &composite_type_ids](
-          const opt::Function& function, opt::BasicBlock* block,
+          opt::Function* function, opt::BasicBlock* block,
           opt::BasicBlock::iterator inst_it,
           const protobufs::InstructionDescriptor& instruction_descriptor)
           -> void {
diff --git a/source/fuzz/fuzzer_pass_copy_objects.cpp b/source/fuzz/fuzzer_pass_copy_objects.cpp
index 48ed588..0fbe5cb 100644
--- a/source/fuzz/fuzzer_pass_copy_objects.cpp
+++ b/source/fuzz/fuzzer_pass_copy_objects.cpp
@@ -30,7 +30,7 @@
 
 void FuzzerPassCopyObjects::Apply() {
   MaybeAddTransformationBeforeEachInstruction(
-      [this](const opt::Function& function, opt::BasicBlock* block,
+      [this](opt::Function* function, opt::BasicBlock* block,
              opt::BasicBlock::iterator inst_it,
              const protobufs::InstructionDescriptor& instruction_descriptor)
           -> void {
diff --git a/source/fuzz/fuzzer_pass_donate_modules.cpp b/source/fuzz/fuzzer_pass_donate_modules.cpp
index e820f25..3368665 100644
--- a/source/fuzz/fuzzer_pass_donate_modules.cpp
+++ b/source/fuzz/fuzzer_pass_donate_modules.cpp
@@ -18,6 +18,7 @@
 #include <queue>
 #include <set>
 
+#include "source/fuzz/call_graph.h"
 #include "source/fuzz/instruction_message.h"
 #include "source/fuzz/transformation_add_constant_boolean.h"
 #include "source/fuzz/transformation_add_constant_composite.h"
@@ -686,53 +687,18 @@
 std::vector<uint32_t>
 FuzzerPassDonateModules::GetFunctionsInCallGraphTopologicalOrder(
     opt::IRContext* context) {
+  CallGraph call_graph(context);
+
   // This is an implementation of Kahn’s algorithm for topological sorting.
 
-  // For each function id, stores the number of distinct functions that call
-  // the function.
-  std::map<uint32_t, uint32_t> function_in_degree;
-
-  // We first build a call graph for the module, and compute the in-degree for
-  // each function in the process.
-  // TODO(afd): If there is functionality elsewhere in the SPIR-V tools
-  //  framework to construct call graphs it could be nice to re-use it here.
-  std::map<uint32_t, std::set<uint32_t>> call_graph_edges;
-
-  // Initialize function in-degree and call graph edges to 0 and empty.
-  for (auto& function : *context->module()) {
-    function_in_degree[function.result_id()] = 0;
-    call_graph_edges[function.result_id()] = std::set<uint32_t>();
-  }
-
-  // Consider every function.
-  for (auto& function : *context->module()) {
-    // Avoid considering the same callee of this function multiple times by
-    // recording known callees.
-    std::set<uint32_t> known_callees;
-    // Consider every function call instruction in every block.
-    for (auto& block : function) {
-      for (auto& instruction : block) {
-        if (instruction.opcode() != SpvOpFunctionCall) {
-          continue;
-        }
-        // Get the id of the function being called.
-        uint32_t callee = instruction.GetSingleWordInOperand(0);
-        if (known_callees.count(callee)) {
-          // We have already considered a call to this function - ignore it.
-          continue;
-        }
-        // Increase the callee's in-degree and add an edge to the call graph.
-        function_in_degree[callee]++;
-        call_graph_edges[function.result_id()].insert(callee);
-        // Mark the callee as 'known'.
-        known_callees.insert(callee);
-      }
-    }
-  }
-
   // This is the sorted order of function ids that we will eventually return.
   std::vector<uint32_t> result;
 
+  // Get a copy of the initial in-degrees of all functions.  The algorithm
+  // involves decrementing these values, hence why we work on a copy.
+  std::map<uint32_t, uint32_t> function_in_degree =
+      call_graph.GetFunctionInDegree();
+
   // Populate a queue with all those function ids with in-degree zero.
   std::queue<uint32_t> queue;
   for (auto& entry : function_in_degree) {
@@ -748,7 +714,7 @@
     auto next = queue.front();
     queue.pop();
     result.push_back(next);
-    for (auto successor : call_graph_edges.at(next)) {
+    for (auto successor : call_graph.GetDirectCallees(next)) {
       assert(function_in_degree.at(successor) > 0 &&
              "The in-degree cannot be zero if the function is a successor.");
       function_in_degree[successor] = function_in_degree.at(successor) - 1;
diff --git a/source/fuzz/fuzzer_pass_obfuscate_constants.cpp b/source/fuzz/fuzzer_pass_obfuscate_constants.cpp
index 3df11ae..2caf0c6 100644
--- a/source/fuzz/fuzzer_pass_obfuscate_constants.cpp
+++ b/source/fuzz/fuzzer_pass_obfuscate_constants.cpp
@@ -416,13 +416,28 @@
           skipped_opcode_count.clear();
         }
 
-        // Consider each operand of the instruction, and add a constant id use
-        // for the operand if relevant.
-        for (uint32_t in_operand_index = 0;
-             in_operand_index < inst.NumInOperands(); in_operand_index++) {
-          MaybeAddConstantIdUse(inst, in_operand_index,
-                                base_instruction_result_id,
-                                skipped_opcode_count, &constant_uses);
+        switch (inst.opcode()) {
+          case SpvOpPhi:
+            // The instruction must not be an OpPhi, as we cannot insert
+            // instructions before an OpPhi.
+            // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2902):
+            //  there is scope for being less conservative.
+            break;
+          case SpvOpVariable:
+            // The instruction must not be an OpVariable, the only id that an
+            // OpVariable uses is an initializer id, which has to remain
+            // constant.
+            break;
+          default:
+            // Consider each operand of the instruction, and add a constant id
+            // use for the operand if relevant.
+            for (uint32_t in_operand_index = 0;
+                 in_operand_index < inst.NumInOperands(); in_operand_index++) {
+              MaybeAddConstantIdUse(inst, in_operand_index,
+                                    base_instruction_result_id,
+                                    skipped_opcode_count, &constant_uses);
+            }
+            break;
         }
 
         if (!inst.HasResultId()) {
diff --git a/source/fuzz/protobufs/spvtoolsfuzz.proto b/source/fuzz/protobufs/spvtoolsfuzz.proto
index 7cd59ac..8a931ba 100644
--- a/source/fuzz/protobufs/spvtoolsfuzz.proto
+++ b/source/fuzz/protobufs/spvtoolsfuzz.proto
@@ -340,6 +340,7 @@
     TransformationAddLocalVariable add_local_variable = 35;
     TransformationLoad load = 36;
     TransformationStore store = 37;
+    TransformationFunctionCall function_call = 38;
     // Add additional option using the next available number.
   }
 }
@@ -731,6 +732,29 @@
 
 }
 
+message TransformationFunctionCall {
+
+  // A transformation that introduces an OpFunctionCall instruction.  The call
+  // must not make the module's call graph cyclic.  Beyond that, if the call
+  // is in a dead block it can be to any function with arbitrary suitably-typed
+  // arguments; otherwise it must be to a livesafe function, with injected
+  // variables as pointer arguments and arbitrary non-pointer arguments.
+
+  // A fresh id for the result of the call
+  uint32 fresh_id = 1;
+
+  // Id of the function to be called
+  uint32 callee_id = 2;
+
+  // Ids for arguments to the function
+  repeated uint32 argument_id = 3;
+
+  // A descriptor for an instruction in a block before which the new
+  // OpFunctionCall instruction should be inserted
+  InstructionDescriptor instruction_to_insert_before = 4;
+
+}
+
 message TransformationLoad {
 
   // Transformation that adds an OpLoad instruction from a pointer into an id.
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index 7d32dc0..d41a734 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -40,6 +40,7 @@
 #include "source/fuzz/transformation_composite_construct.h"
 #include "source/fuzz/transformation_composite_extract.h"
 #include "source/fuzz/transformation_copy_object.h"
+#include "source/fuzz/transformation_function_call.h"
 #include "source/fuzz/transformation_load.h"
 #include "source/fuzz/transformation_merge_blocks.h"
 #include "source/fuzz/transformation_move_block_down.h"
@@ -124,6 +125,8 @@
           message.composite_extract());
     case protobufs::Transformation::TransformationCase::kCopyObject:
       return MakeUnique<TransformationCopyObject>(message.copy_object());
+    case protobufs::Transformation::TransformationCase::kFunctionCall:
+      return MakeUnique<TransformationFunctionCall>(message.function_call());
     case protobufs::Transformation::TransformationCase::kLoad:
       return MakeUnique<TransformationLoad>(message.load());
     case protobufs::Transformation::TransformationCase::kMergeBlocks:
diff --git a/source/fuzz/transformation_add_function.cpp b/source/fuzz/transformation_add_function.cpp
index 120b3df..8f0d3c9 100644
--- a/source/fuzz/transformation_add_function.cpp
+++ b/source/fuzz/transformation_add_function.cpp
@@ -132,17 +132,27 @@
     return false;
   }
 
+  // Check whether the cloned module is still valid after adding the function.
+  // If it is not, the transformation is not applicable.
+  if (!fuzzerutil::IsValid(cloned_module.get())) {
+    return false;
+  }
+
   if (message_.is_livesafe()) {
-    // We make the cloned module livesafe.
     if (!TryToMakeFunctionLivesafe(cloned_module.get(), fact_manager)) {
       return false;
     }
+    // After making the function livesafe, we check validity of the module
+    // again.  This is because the turning of OpKill, OpUnreachable and OpReturn
+    // instructions into branches changes control flow graph reachability, which
+    // has the potential to make the module invalid when it was otherwise valid.
+    // It is simpler to rely on the validator to guard against this than to
+    // consider all scenarios when making a function livesafe.
+    if (!fuzzerutil::IsValid(cloned_module.get())) {
+      return false;
+    }
   }
-
-  // Having managed to add the new function to the cloned module, and
-  // potentially also made it livesafe, we ascertain whether the cloned module
-  // is still valid.  If it is, the transformation is applicable.
-  return fuzzerutil::IsValid(cloned_module.get());
+  return true;
 }
 
 void TransformationAddFunction::Apply(
diff --git a/source/fuzz/transformation_function_call.cpp b/source/fuzz/transformation_function_call.cpp
new file mode 100644
index 0000000..6988664
--- /dev/null
+++ b/source/fuzz/transformation_function_call.cpp
@@ -0,0 +1,195 @@
+// Copyright (c) 2020 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_function_call.h"
+
+#include "source/fuzz/call_graph.h"
+#include "source/fuzz/fuzzer_util.h"
+#include "source/fuzz/instruction_descriptor.h"
+
+namespace spvtools {
+namespace fuzz {
+
+TransformationFunctionCall::TransformationFunctionCall(
+    const spvtools::fuzz::protobufs::TransformationFunctionCall& message)
+    : message_(message) {}
+
+TransformationFunctionCall::TransformationFunctionCall(
+    uint32_t fresh_id, uint32_t callee_id,
+    const std::vector<uint32_t>& argument_id,
+    const protobufs::InstructionDescriptor& instruction_to_insert_before) {
+  message_.set_fresh_id(fresh_id);
+  message_.set_callee_id(callee_id);
+  for (auto argument : argument_id) {
+    message_.add_argument_id(argument);
+  }
+  *message_.mutable_instruction_to_insert_before() =
+      instruction_to_insert_before;
+}
+
+bool TransformationFunctionCall::IsApplicable(
+    opt::IRContext* context,
+    const spvtools::fuzz::FactManager& fact_manager) const {
+  // The result id must be fresh
+  if (!fuzzerutil::IsFreshId(context, message_.fresh_id())) {
+    return false;
+  }
+
+  // The function must exist
+  auto callee_inst = context->get_def_use_mgr()->GetDef(message_.callee_id());
+  if (!callee_inst || callee_inst->opcode() != SpvOpFunction) {
+    return false;
+  }
+
+  // The function must not be an entry point
+  if (FunctionIsEntryPoint(context, message_.callee_id())) {
+    return false;
+  }
+
+  auto callee_type_inst = context->get_def_use_mgr()->GetDef(
+      callee_inst->GetSingleWordInOperand(1));
+  assert(callee_type_inst->opcode() == SpvOpTypeFunction &&
+         "Bad function type.");
+
+  // The number of expected function arguments must match the number of given
+  // arguments.  The number of expected arguments is one less than the function
+  // type's number of input operands, as one operand is for the return type.
+  if (callee_type_inst->NumInOperands() - 1 !=
+      static_cast<uint32_t>(message_.argument_id().size())) {
+    return false;
+  }
+
+  // The instruction descriptor must refer to a position where it is valid to
+  // insert the call
+  auto insert_before =
+      FindInstruction(message_.instruction_to_insert_before(), context);
+  if (!insert_before) {
+    return false;
+  }
+  if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(SpvOpFunctionCall,
+                                                    insert_before)) {
+    return false;
+  }
+
+  auto block = context->get_instr_block(insert_before);
+  auto enclosing_function = block->GetParent();
+
+  // If the block is not dead, the function must be livesafe
+  bool block_is_dead = fact_manager.BlockIsDead(block->id());
+  if (!block_is_dead &&
+      !fact_manager.FunctionIsLivesafe(message_.callee_id())) {
+    return false;
+  }
+
+  // The ids must all match and have the right types and satisfy rules on
+  // pointers.  If the block is not dead, pointers must be arbitrary.
+  for (uint32_t arg_index = 0;
+       arg_index < static_cast<uint32_t>(message_.argument_id().size());
+       arg_index++) {
+    opt::Instruction* arg_inst =
+        context->get_def_use_mgr()->GetDef(message_.argument_id(arg_index));
+    if (!arg_inst) {
+      // The given argument does not correspond to an instruction.
+      return false;
+    }
+    if (!arg_inst->type_id()) {
+      // The given argument does not have a type; it is thus not suitable.
+    }
+    if (arg_inst->type_id() !=
+        callee_type_inst->GetSingleWordInOperand(arg_index + 1)) {
+      // Argument type mismatch.
+      return false;
+    }
+    opt::Instruction* arg_type_inst =
+        context->get_def_use_mgr()->GetDef(arg_inst->type_id());
+    if (arg_type_inst->opcode() == SpvOpTypePointer) {
+      switch (arg_inst->opcode()) {
+        case SpvOpFunctionParameter:
+        case SpvOpVariable:
+          // These are OK
+          break;
+        default:
+          // Other pointer ids cannot be passed as parameters
+          return false;
+      }
+      if (!block_is_dead &&
+          !fact_manager.PointeeValueIsIrrelevant(arg_inst->result_id())) {
+        // This is not a dead block, so pointer parameters passed to the called
+        // function might really have their contents modified. We thus require
+        // such pointers to be to arbitrary-valued variables, which this is not.
+        return false;
+      }
+    }
+
+    // The argument id needs to be available (according to dominance rules) at
+    // the point where the call will occur.
+    if (!fuzzerutil::IdIsAvailableBeforeInstruction(context, insert_before,
+                                                    arg_inst->result_id())) {
+      return false;
+    }
+  }
+
+  // Introducing the call must not lead to recursion.
+  if (message_.callee_id() == enclosing_function->result_id()) {
+    // This would be direct recursion.
+    return false;
+  }
+  // Ensure the call would not lead to indirect recursion.
+  return !CallGraph(context)
+              .GetIndirectCallees(message_.callee_id())
+              .count(block->GetParent()->result_id());
+}
+
+void TransformationFunctionCall::Apply(
+    opt::IRContext* context, spvtools::fuzz::FactManager* /*unused*/) const {
+  // Update the module's bound to reflect the fresh id for the result of the
+  // function call.
+  fuzzerutil::UpdateModuleIdBound(context, message_.fresh_id());
+  // Get the return type of the function being called.
+  uint32_t return_type =
+      context->get_def_use_mgr()->GetDef(message_.callee_id())->type_id();
+  // Populate the operands to the call instruction, with the function id and the
+  // arguments.
+  opt::Instruction::OperandList operands;
+  operands.push_back({SPV_OPERAND_TYPE_ID, {message_.callee_id()}});
+  for (auto arg : message_.argument_id()) {
+    operands.push_back({SPV_OPERAND_TYPE_ID, {arg}});
+  }
+  // Insert the function call before the instruction specified in the message.
+  FindInstruction(message_.instruction_to_insert_before(), context)
+      ->InsertBefore(
+          MakeUnique<opt::Instruction>(context, SpvOpFunctionCall, return_type,
+                                       message_.fresh_id(), operands));
+  // Invalidate all analyses since we have changed the module.
+  context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
+}
+
+protobufs::Transformation TransformationFunctionCall::ToMessage() const {
+  protobufs::Transformation result;
+  *result.mutable_function_call() = message_;
+  return result;
+}
+
+bool TransformationFunctionCall::FunctionIsEntryPoint(opt::IRContext* context,
+                                                      uint32_t function_id) {
+  for (auto& entry_point : context->module()->entry_points()) {
+    if (entry_point.GetSingleWordInOperand(1) == function_id) {
+      return true;
+    }
+  }
+  return false;
+}
+
+}  // namespace fuzz
+}  // namespace spvtools
diff --git a/source/fuzz/transformation_function_call.h b/source/fuzz/transformation_function_call.h
new file mode 100644
index 0000000..e977e1d
--- /dev/null
+++ b/source/fuzz/transformation_function_call.h
@@ -0,0 +1,69 @@
+// Copyright (c) 2020 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_FUNCTION_CALL_H_
+#define SOURCE_FUZZ_TRANSFORMATION_FUNCTION_CALL_H_
+
+#include "source/fuzz/fact_manager.h"
+#include "source/fuzz/protobufs/spirvfuzz_protobufs.h"
+#include "source/fuzz/transformation.h"
+#include "source/opt/ir_context.h"
+
+namespace spvtools {
+namespace fuzz {
+
+class TransformationFunctionCall : public Transformation {
+ public:
+  explicit TransformationFunctionCall(
+      const protobufs::TransformationFunctionCall& message);
+
+  TransformationFunctionCall(
+      uint32_t fresh_id, uint32_t callee_id,
+      const std::vector<uint32_t>& argument_id,
+      const protobufs::InstructionDescriptor& instruction_to_insert_before);
+
+  // - |message_.fresh_id| must be fresh
+  // - |message_.instruction_to_insert_before| must identify an instruction
+  //   before which an OpFunctionCall can be legitimately inserted
+  // - |message_.function_id| must be the id of a function, and calling the
+  //   function before the identified instruction must not introduce recursion
+  // - |message_.arg_id| must provide suitable arguments for the function call
+  //   (they must have the right types and be available according to dominance
+  //   rules)
+  // - If the insertion point is not in a dead block then |message_function_id|
+  //   must refer to a livesafe function, and every pointer argument in
+  //   |message_.arg_id| must refer to an arbitrary-valued variable
+  bool IsApplicable(opt::IRContext* context,
+                    const FactManager& fact_manager) const override;
+
+  // Adds an instruction of the form:
+  //   |fresh_id| = OpFunctionCall %type |callee_id| |arg_id...|
+  // before |instruction_to_insert_before|, where %type is the return type of
+  // |callee_id|.
+  void Apply(opt::IRContext* context, FactManager* fact_manager) const override;
+
+  protobufs::Transformation ToMessage() const override;
+
+  // Helper to determine whether |function_id| is targeted by OpEntryPoint.
+  static bool FunctionIsEntryPoint(opt::IRContext* context,
+                                   uint32_t function_id);
+
+ private:
+  protobufs::TransformationFunctionCall message_;
+};
+
+}  // namespace fuzz
+}  // namespace spvtools
+
+#endif  // SOURCE_FUZZ_TRANSFORMATION_FUNCTION_CALL_H_
diff --git a/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.cpp b/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.cpp
index b097767..72d9b22 100644
--- a/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.cpp
+++ b/source/fuzz/transformation_replace_boolean_constant_with_constant_binary.cpp
@@ -243,11 +243,22 @@
     return false;
   }
 
-  // The instruction must not be an OpPhi, as we cannot insert a binary
-  // operator instruction before an OpPhi.
-  // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2902): there is
-  //  scope for being less conservative.
-  return instruction->opcode() != SpvOpPhi;
+  switch (instruction->opcode()) {
+    case SpvOpPhi:
+      // The instruction must not be an OpPhi, as we cannot insert a binary
+      // operator instruction before an OpPhi.
+      // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2902): there is
+      //  scope for being less conservative.
+      return false;
+    case SpvOpVariable:
+      // The instruction must not be an OpVariable, because (a) we cannot insert
+      // a binary operator before an OpVariable, but in any case (b) the
+      // constant we would be replacing is the initializer constant of the
+      // OpVariable, and this cannot be the result of a binary operation.
+      return false;
+    default:
+      return true;
+  }
 }
 
 void TransformationReplaceBooleanConstantWithConstantBinary::Apply(
diff --git a/source/fuzz/transformation_replace_constant_with_uniform.cpp b/source/fuzz/transformation_replace_constant_with_uniform.cpp
index 405776e..8e0e4e5 100644
--- a/source/fuzz/transformation_replace_constant_with_uniform.cpp
+++ b/source/fuzz/transformation_replace_constant_with_uniform.cpp
@@ -154,6 +154,12 @@
     return false;
   }
 
+  // The use must not be a variable initializer; these are required to be
+  // constants, so it would be illegal to replace one with a uniform access.
+  if (instruction_using_constant->opcode() == SpvOpVariable) {
+    return false;
+  }
+
   // The module needs to have a uniform pointer type suitable for indexing into
   // the uniform variable, i.e. matching the type of the constant we wish to
   // replace with a uniform.
diff --git a/test/fuzz/CMakeLists.txt b/test/fuzz/CMakeLists.txt
index 29d33ec..4a423a9 100644
--- a/test/fuzz/CMakeLists.txt
+++ b/test/fuzz/CMakeLists.txt
@@ -47,6 +47,7 @@
           transformation_composite_construct_test.cpp
           transformation_composite_extract_test.cpp
           transformation_copy_object_test.cpp
+          transformation_function_call_test.cpp
           transformation_load_test.cpp
           transformation_merge_blocks_test.cpp
           transformation_move_block_down_test.cpp
diff --git a/test/fuzz/transformation_function_call_test.cpp b/test/fuzz/transformation_function_call_test.cpp
new file mode 100644
index 0000000..9bd971e
--- /dev/null
+++ b/test/fuzz/transformation_function_call_test.cpp
@@ -0,0 +1,443 @@
+// Copyright (c) 2020 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_function_call.h"
+#include "source/fuzz/instruction_descriptor.h"
+#include "test/fuzz/fuzz_test_util.h"
+
+namespace spvtools {
+namespace fuzz {
+namespace {
+
+TEST(TransformationFunctionCallTest, BasicTest) {
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypePointer Function %6
+          %8 = OpTypeFunction %6 %7
+         %12 = OpTypeFloat 32
+         %13 = OpTypePointer Function %12
+         %14 = OpTypeFunction %6 %7 %13
+         %27 = OpConstant %6 1
+         %50 = OpConstant %12 1
+         %57 = OpTypeBool
+         %58 = OpConstantFalse %57
+        %204 = OpUndef %6
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %61 = OpVariable %7 Function
+         %62 = OpVariable %7 Function
+         %65 = OpVariable %13 Function
+         %66 = OpVariable %7 Function
+         %68 = OpVariable %13 Function
+         %71 = OpVariable %7 Function
+         %72 = OpVariable %13 Function
+         %73 = OpVariable %7 Function
+         %75 = OpVariable %13 Function
+         %78 = OpVariable %7 Function
+         %98 = OpAccessChain %7 %71
+         %99 = OpCopyObject %7 %71
+               OpSelectionMerge %60 None
+               OpBranchConditional %58 %59 %60
+         %59 = OpLabel
+               OpBranch %60
+         %60 = OpLabel
+               OpReturn
+               OpFunctionEnd
+         %10 = OpFunction %6 None %8
+          %9 = OpFunctionParameter %7
+         %11 = OpLabel
+         %26 = OpLoad %6 %9
+         %28 = OpIAdd %6 %26 %27
+               OpSelectionMerge %97 None
+               OpBranchConditional %58 %96 %97
+         %96 = OpLabel
+               OpBranch %97
+         %97 = OpLabel
+               OpReturnValue %28
+               OpFunctionEnd
+         %17 = OpFunction %6 None %14
+         %15 = OpFunctionParameter %7
+         %16 = OpFunctionParameter %13
+         %18 = OpLabel
+         %31 = OpVariable %7 Function
+         %32 = OpLoad %6 %15
+               OpStore %31 %32
+         %33 = OpFunctionCall %6 %10 %31
+               OpReturnValue %33
+               OpFunctionEnd
+         %21 = OpFunction %6 None %14
+         %19 = OpFunctionParameter %7
+         %20 = OpFunctionParameter %13
+         %22 = OpLabel
+         %36 = OpLoad %6 %19
+         %37 = OpLoad %12 %20
+         %38 = OpConvertFToS %6 %37
+         %39 = OpIAdd %6 %36 %38
+               OpReturnValue %39
+               OpFunctionEnd
+         %24 = OpFunction %6 None %8
+         %23 = OpFunctionParameter %7
+         %25 = OpLabel
+         %44 = OpVariable %7 Function
+         %46 = OpVariable %13 Function
+         %51 = OpVariable %7 Function
+         %52 = OpVariable %13 Function
+         %42 = OpLoad %6 %23
+         %43 = OpConvertSToF %12 %42
+         %45 = OpLoad %6 %23
+               OpStore %44 %45
+               OpStore %46 %43
+         %47 = OpFunctionCall %6 %17 %44 %46
+         %48 = OpLoad %6 %23
+         %49 = OpIAdd %6 %48 %27
+               OpStore %51 %49
+               OpStore %52 %50
+         %53 = OpFunctionCall %6 %17 %51 %52
+         %54 = OpIAdd %6 %47 %53
+               OpReturnValue %54
+               OpFunctionEnd
+        %200 = OpFunction %6 None %14
+        %201 = OpFunctionParameter %7
+        %202 = OpFunctionParameter %13
+        %203 = OpLabel
+               OpSelectionMerge %206 None
+               OpBranchConditional %58 %205 %206
+        %205 = OpLabel
+               OpBranch %206
+        %206 = OpLabel
+               OpReturnValue %204
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_4;
+  const auto consumer = nullptr;
+  const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  FactManager fact_manager;
+
+  fact_manager.AddFactBlockIsDead(59);
+  fact_manager.AddFactBlockIsDead(11);
+  fact_manager.AddFactBlockIsDead(18);
+  fact_manager.AddFactBlockIsDead(25);
+  fact_manager.AddFactBlockIsDead(96);
+  fact_manager.AddFactBlockIsDead(205);
+  fact_manager.AddFactFunctionIsLivesafe(21);
+  fact_manager.AddFactFunctionIsLivesafe(200);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(71);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(72);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(19);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(20);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(23);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(44);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(46);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(51);
+  fact_manager.AddFactValueOfPointeeIsIrrelevant(52);
+
+  // Livesafe functions with argument types: 21(7, 13), 200(7, 13)
+  // Non-livesafe functions with argument types: 4(), 10(7), 17(7, 13), 24(7)
+  // Call graph edges:
+  //    17 -> 10
+  //    24 -> 17
+
+  // Bad transformations
+  // Too many arguments
+  ASSERT_FALSE(
+      TransformationFunctionCall(100, 21, {71, 72, 71},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // Too few arguments
+  ASSERT_FALSE(TransformationFunctionCall(
+                   100, 21, {71}, MakeInstructionDescriptor(59, SpvOpBranch, 0))
+                   .IsApplicable(context.get(), fact_manager));
+  // Arguments are the wrong way around (types do not match)
+  ASSERT_FALSE(
+      TransformationFunctionCall(100, 21, {72, 71},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // 21 is not an appropriate argument
+  ASSERT_FALSE(
+      TransformationFunctionCall(100, 21, {21, 72},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // 300 does not exist
+  ASSERT_FALSE(
+      TransformationFunctionCall(100, 21, {300, 72},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // 71 is not a function
+  ASSERT_FALSE(
+      TransformationFunctionCall(100, 71, {71, 72},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // 500 does not exist
+  ASSERT_FALSE(
+      TransformationFunctionCall(100, 500, {71, 72},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // Id is not fresh
+  ASSERT_FALSE(
+      TransformationFunctionCall(21, 21, {71, 72},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // Access chain as pointer parameter
+  ASSERT_FALSE(
+      TransformationFunctionCall(100, 21, {98, 72},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // Copied object as pointer parameter
+  ASSERT_FALSE(
+      TransformationFunctionCall(100, 21, {99, 72},
+                                 MakeInstructionDescriptor(59, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // Non-livesafe called from original live block
+  ASSERT_FALSE(
+      TransformationFunctionCall(
+          100, 10, {71}, MakeInstructionDescriptor(99, SpvOpSelectionMerge, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // Non-livesafe called from livesafe function
+  ASSERT_FALSE(
+      TransformationFunctionCall(
+          100, 10, {19}, MakeInstructionDescriptor(38, SpvOpConvertFToS, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // Livesafe function called with pointer to non-arbitrary local variable
+  ASSERT_FALSE(
+      TransformationFunctionCall(
+          100, 21, {61, 72}, MakeInstructionDescriptor(38, SpvOpConvertFToS, 0))
+          .IsApplicable(context.get(), fact_manager));
+  // Direct recursion
+  ASSERT_FALSE(TransformationFunctionCall(
+                   100, 4, {}, MakeInstructionDescriptor(59, SpvOpBranch, 0))
+                   .IsApplicable(context.get(), fact_manager));
+  // Indirect recursion
+  ASSERT_FALSE(TransformationFunctionCall(
+                   100, 24, {9}, MakeInstructionDescriptor(96, SpvOpBranch, 0))
+                   .IsApplicable(context.get(), fact_manager));
+  // Parameter 23 is not available at the call site
+  ASSERT_FALSE(
+      TransformationFunctionCall(104, 10, {23},
+                                 MakeInstructionDescriptor(205, SpvOpBranch, 0))
+          .IsApplicable(context.get(), fact_manager));
+
+  // Good transformations
+  {
+    // Livesafe called from dead block: fine
+    TransformationFunctionCall transformation(
+        100, 21, {71, 72}, MakeInstructionDescriptor(59, SpvOpBranch, 0));
+    ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+    transformation.Apply(context.get(), &fact_manager);
+    ASSERT_TRUE(IsValid(env, context.get()));
+  }
+  {
+    // Livesafe called from original live block: fine
+    TransformationFunctionCall transformation(
+        101, 21, {71, 72}, MakeInstructionDescriptor(98, SpvOpAccessChain, 0));
+    ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+    transformation.Apply(context.get(), &fact_manager);
+    ASSERT_TRUE(IsValid(env, context.get()));
+  }
+  {
+    // Livesafe called from livesafe function: fine
+    TransformationFunctionCall transformation(
+        102, 200, {19, 20}, MakeInstructionDescriptor(36, SpvOpLoad, 0));
+    ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+    transformation.Apply(context.get(), &fact_manager);
+    ASSERT_TRUE(IsValid(env, context.get()));
+  }
+  {
+    // Dead called from dead block in injected function: fine
+    TransformationFunctionCall transformation(
+        103, 10, {23}, MakeInstructionDescriptor(45, SpvOpLoad, 0));
+    ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+    transformation.Apply(context.get(), &fact_manager);
+    ASSERT_TRUE(IsValid(env, context.get()));
+  }
+  {
+    // Non-livesafe called from dead block in livesafe function: OK
+    TransformationFunctionCall transformation(
+        104, 10, {201}, MakeInstructionDescriptor(205, SpvOpBranch, 0));
+    ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+    transformation.Apply(context.get(), &fact_manager);
+    ASSERT_TRUE(IsValid(env, context.get()));
+  }
+  {
+    // Livesafe called from dead block with non-arbitrary parameter
+    TransformationFunctionCall transformation(
+        105, 21, {62, 65}, MakeInstructionDescriptor(59, SpvOpBranch, 0));
+    ASSERT_TRUE(transformation.IsApplicable(context.get(), fact_manager));
+    transformation.Apply(context.get(), &fact_manager);
+    ASSERT_TRUE(IsValid(env, context.get()));
+  }
+
+  std::string after_transformation = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypePointer Function %6
+          %8 = OpTypeFunction %6 %7
+         %12 = OpTypeFloat 32
+         %13 = OpTypePointer Function %12
+         %14 = OpTypeFunction %6 %7 %13
+         %27 = OpConstant %6 1
+         %50 = OpConstant %12 1
+         %57 = OpTypeBool
+         %58 = OpConstantFalse %57
+        %204 = OpUndef %6
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %61 = OpVariable %7 Function
+         %62 = OpVariable %7 Function
+         %65 = OpVariable %13 Function
+         %66 = OpVariable %7 Function
+         %68 = OpVariable %13 Function
+         %71 = OpVariable %7 Function
+         %72 = OpVariable %13 Function
+         %73 = OpVariable %7 Function
+         %75 = OpVariable %13 Function
+         %78 = OpVariable %7 Function
+        %101 = OpFunctionCall %6 %21 %71 %72
+         %98 = OpAccessChain %7 %71
+         %99 = OpCopyObject %7 %71
+               OpSelectionMerge %60 None
+               OpBranchConditional %58 %59 %60
+         %59 = OpLabel
+        %100 = OpFunctionCall %6 %21 %71 %72
+        %105 = OpFunctionCall %6 %21 %62 %65
+               OpBranch %60
+         %60 = OpLabel
+               OpReturn
+               OpFunctionEnd
+         %10 = OpFunction %6 None %8
+          %9 = OpFunctionParameter %7
+         %11 = OpLabel
+         %26 = OpLoad %6 %9
+         %28 = OpIAdd %6 %26 %27
+               OpSelectionMerge %97 None
+               OpBranchConditional %58 %96 %97
+         %96 = OpLabel
+               OpBranch %97
+         %97 = OpLabel
+               OpReturnValue %28
+               OpFunctionEnd
+         %17 = OpFunction %6 None %14
+         %15 = OpFunctionParameter %7
+         %16 = OpFunctionParameter %13
+         %18 = OpLabel
+         %31 = OpVariable %7 Function
+         %32 = OpLoad %6 %15
+               OpStore %31 %32
+         %33 = OpFunctionCall %6 %10 %31
+               OpReturnValue %33
+               OpFunctionEnd
+         %21 = OpFunction %6 None %14
+         %19 = OpFunctionParameter %7
+         %20 = OpFunctionParameter %13
+         %22 = OpLabel
+        %102 = OpFunctionCall %6 %200 %19 %20
+         %36 = OpLoad %6 %19
+         %37 = OpLoad %12 %20
+         %38 = OpConvertFToS %6 %37
+         %39 = OpIAdd %6 %36 %38
+               OpReturnValue %39
+               OpFunctionEnd
+         %24 = OpFunction %6 None %8
+         %23 = OpFunctionParameter %7
+         %25 = OpLabel
+         %44 = OpVariable %7 Function
+         %46 = OpVariable %13 Function
+         %51 = OpVariable %7 Function
+         %52 = OpVariable %13 Function
+         %42 = OpLoad %6 %23
+         %43 = OpConvertSToF %12 %42
+        %103 = OpFunctionCall %6 %10 %23
+         %45 = OpLoad %6 %23
+               OpStore %44 %45
+               OpStore %46 %43
+         %47 = OpFunctionCall %6 %17 %44 %46
+         %48 = OpLoad %6 %23
+         %49 = OpIAdd %6 %48 %27
+               OpStore %51 %49
+               OpStore %52 %50
+         %53 = OpFunctionCall %6 %17 %51 %52
+         %54 = OpIAdd %6 %47 %53
+               OpReturnValue %54
+               OpFunctionEnd
+        %200 = OpFunction %6 None %14
+        %201 = OpFunctionParameter %7
+        %202 = OpFunctionParameter %13
+        %203 = OpLabel
+               OpSelectionMerge %206 None
+               OpBranchConditional %58 %205 %206
+        %205 = OpLabel
+        %104 = OpFunctionCall %6 %10 %201
+               OpBranch %206
+        %206 = OpLabel
+               OpReturnValue %204
+               OpFunctionEnd
+  )";
+  ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
+}
+
+TEST(TransformationFunctionCallTest, DoNotInvokeEntryPoint) {
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+               OpReturn
+               OpFunctionEnd
+         %10 = OpFunction %2 None %3
+         %11 = OpLabel
+               OpReturn
+               OpFunctionEnd
+  )";
+
+  const auto env = SPV_ENV_UNIVERSAL_1_4;
+  const auto consumer = nullptr;
+  const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
+  ASSERT_TRUE(IsValid(env, context.get()));
+
+  FactManager fact_manager;
+
+  fact_manager.AddFactBlockIsDead(11);
+
+  // 4 is an entry point, so it is not legal for it to be the target of a call.
+  ASSERT_FALSE(TransformationFunctionCall(
+                   100, 4, {}, MakeInstructionDescriptor(11, SpvOpReturn, 0))
+                   .IsApplicable(context.get(), fact_manager));
+}
+
+}  // namespace
+}  // namespace fuzz
+}  // namespace spvtools
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
index bfc7fa7..527a7b7 100644
--- a/test/fuzz/transformation_replace_boolean_constant_with_constant_binary_test.cpp
+++ b/test/fuzz/transformation_replace_boolean_constant_with_constant_binary_test.cpp
@@ -650,6 +650,45 @@
   ASSERT_FALSE(replacement.IsApplicable(context.get(), fact_manager));
 }
 
+TEST(TransformationReplaceBooleanConstantWithConstantBinaryTest,
+     DoNotReplaceVariableInitializer) {
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource ESSL 310
+               OpName %4 "main"
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeBool
+          %7 = OpTypePointer Function %6
+          %9 = OpConstantTrue %6
+         %10 = OpTypeInt 32 1
+         %13 = OpConstant %10 0
+         %15 = OpConstant %10 1
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+         %50 = OpVariable %7 Function %9
+               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;
+
+  ASSERT_FALSE(TransformationReplaceBooleanConstantWithConstantBinary(
+                   MakeIdUseDescriptor(
+                       9, MakeInstructionDescriptor(50, SpvOpVariable, 0), 1),
+                   13, 15, SpvOpSLessThan, 100)
+                   .IsApplicable(context.get(), fact_manager));
+}
+
 }  // namespace
 }  // namespace fuzz
 }  // namespace spvtools
diff --git a/test/fuzz/transformation_replace_constant_with_uniform_test.cpp b/test/fuzz/transformation_replace_constant_with_uniform_test.cpp
index ac2e3f9..58d4a89 100644
--- a/test/fuzz/transformation_replace_constant_with_uniform_test.cpp
+++ b/test/fuzz/transformation_replace_constant_with_uniform_test.cpp
@@ -1442,6 +1442,56 @@
   ASSERT_TRUE(IsEqual(env, after, context.get()));
 }
 
+TEST(TransformationReplaceConstantWithUniformTest,
+     DoNotReplaceVariableInitializer) {
+  // If a local variable has a constant initializer, this cannot be replaced
+  // by a uniform.
+
+  std::string shader = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Fragment %4 "main"
+               OpExecutionMode %4 OriginUpperLeft
+               OpSource GLSL 450
+               OpMemberDecorate %16 0 Offset 0
+               OpDecorate %16 Block
+               OpDecorate %18 DescriptorSet 0
+               OpDecorate %18 Binding 0
+          %2 = OpTypeVoid
+          %3 = OpTypeFunction %2
+          %6 = OpTypeInt 32 1
+          %7 = OpTypePointer Function %6
+         %50 = OpConstant %6 0
+         %16 = OpTypeStruct %6
+         %17 = OpTypePointer Uniform %16
+         %51 = OpTypePointer Uniform %6
+         %18 = OpVariable %17 Uniform
+          %4 = OpFunction %2 None %3
+          %5 = OpLabel
+          %8 = OpVariable %7 Function %50
+               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;
+  protobufs::UniformBufferElementDescriptor blockname_a =
+      MakeUniformBufferElementDescriptor(0, 0, {0});
+
+  ASSERT_TRUE(AddFactHelper(&fact_manager, context.get(), 0, blockname_a));
+
+  ASSERT_FALSE(TransformationReplaceConstantWithUniform(
+                   MakeIdUseDescriptor(
+                       50, MakeInstructionDescriptor(8, SpvOpVariable, 0), 1),
+                   blockname_a, 100, 101)
+                   .IsApplicable(context.get(), fact_manager));
+}
+
 }  // namespace
 }  // namespace fuzz
 }  // namespace spvtools