diff --git a/source/fuzz/fuzzer_pass_add_composite_types.cpp b/source/fuzz/fuzzer_pass_add_composite_types.cpp
index a59cbfa..3dfbd69 100644
--- a/source/fuzz/fuzzer_pass_add_composite_types.cpp
+++ b/source/fuzz/fuzzer_pass_add_composite_types.cpp
@@ -123,7 +123,9 @@
         break;
       case SpvOpTypeStruct: {
         if (!fuzzerutil::MembersHaveBuiltInDecoration(GetIRContext(),
-                                                      inst.result_id())) {
+                                                      inst.result_id()) &&
+            !fuzzerutil::HasBlockOrBufferBlockDecoration(GetIRContext(),
+                                                         inst.result_id())) {
           candidates.push_back(inst.result_id());
         }
       } break;
diff --git a/source/fuzz/fuzzer_pass_construct_composites.cpp b/source/fuzz/fuzzer_pass_construct_composites.cpp
index dc02424..1a174cf 100644
--- a/source/fuzz/fuzzer_pass_construct_composites.cpp
+++ b/source/fuzz/fuzzer_pass_construct_composites.cpp
@@ -16,6 +16,7 @@
 
 #include <memory>
 
+#include "source/fuzz/available_instructions.h"
 #include "source/fuzz/fuzzer_util.h"
 #include "source/fuzz/transformation_composite_construct.h"
 
@@ -42,12 +43,40 @@
     }
   }
 
+  if (composite_type_ids.empty()) {
+    // There are no composite types, so this fuzzer pass cannot do anything.
+    return;
+  }
+
+  AvailableInstructions available_composite_constituents(
+      GetIRContext(),
+      [this](opt::IRContext* ir_context, opt::Instruction* inst) -> bool {
+        if (!inst->result_id() || !inst->type_id()) {
+          return false;
+        }
+
+        // If the id is irrelevant, we can use it since it will not
+        // participate in DataSynonym fact. Otherwise, we should be able
+        // to produce a synonym out of the id.
+        return GetTransformationContext()->GetFactManager()->IdIsIrrelevant(
+                   inst->result_id()) ||
+               fuzzerutil::CanMakeSynonymOf(ir_context,
+                                            *GetTransformationContext(), inst);
+      });
+
   ForEachInstructionWithInstructionDescriptor(
-      [this, &composite_type_ids](
-          opt::Function* function, opt::BasicBlock* block,
+      [this, &available_composite_constituents, &composite_type_ids](
+          opt::Function* /*unused*/, opt::BasicBlock* /*unused*/,
           opt::BasicBlock::iterator inst_it,
           const protobufs::InstructionDescriptor& instruction_descriptor)
           -> void {
+        // Randomly decide whether to try inserting a composite construction
+        // here.
+        if (!GetFuzzerContext()->ChoosePercentage(
+                GetFuzzerContext()->GetChanceOfConstructingComposite())) {
+          return;
+        }
+
         // Check whether it is legitimate to insert a composite construction
         // before the instruction.
         if (!fuzzerutil::CanInsertOpcodeBeforeInstruction(
@@ -55,36 +84,21 @@
           return;
         }
 
-        // Randomly decide whether to try inserting an object copy here.
-        if (!GetFuzzerContext()->ChoosePercentage(
-                GetFuzzerContext()->GetChanceOfConstructingComposite())) {
-          return;
-        }
-
         // For each instruction that is available at this program point (i.e. an
         // instruction that is global or whose definition strictly dominates the
         // program point) and suitable for making a synonym of, associate it
         // with the id of its result type.
         TypeIdToInstructions type_id_to_available_instructions;
-        auto available_instructions = FindAvailableInstructions(
-            function, block, inst_it,
-            [this](opt::IRContext* ir_context, opt::Instruction* inst) {
-              if (!inst->result_id() || !inst->type_id()) {
-                return false;
-              }
-
-              // If the id is irrelevant, we can use it since it will not
-              // participate in DataSynonym fact. Otherwise, we should be able
-              // to produce a synonym out of the id.
-              return GetTransformationContext()
-                         ->GetFactManager()
-                         ->IdIsIrrelevant(inst->result_id()) ||
-                     fuzzerutil::CanMakeSynonymOf(
-                         ir_context, *GetTransformationContext(), inst);
-            });
-        for (auto instruction : available_instructions) {
-          RecordAvailableInstruction(instruction,
-                                     &type_id_to_available_instructions);
+        auto available_instructions =
+            available_composite_constituents.GetAvailableBeforeInstruction(
+                &*inst_it);
+        for (uint32_t available_instruction_index = 0;
+             available_instruction_index < available_instructions.size();
+             available_instruction_index++) {
+          opt::Instruction* inst =
+              available_instructions[available_instruction_index];
+          type_id_to_available_instructions[inst->type_id()].push_back(
+              inst->result_id());
         }
 
         // At this point, |composite_type_ids| captures all the composite types
@@ -92,68 +106,41 @@
         // captures all the available result ids we might use, organized by
         // type.
 
-        // Now we try to find a composite that we can construct.  We might not
-        // manage, if there is a paucity of available ingredients in the module
-        // (e.g. if our only available composite was a boolean vector and we had
-        // no instructions generating boolean result types available).
-        //
-        // If we succeed, |chosen_composite_type| will end up being non-zero,
-        // and |constructor_arguments| will end up giving us result ids suitable
-        // for constructing a composite of that type.  Otherwise these variables
-        // will remain 0 and null respectively.
-        uint32_t chosen_composite_type = 0;
+        // Now we choose a composite type to construct, building it from
+        // available constituent components and using zero constants if suitable
+        // components are not available.
+
         std::vector<uint32_t> constructor_arguments;
+        uint32_t chosen_composite_type =
+            composite_type_ids[GetFuzzerContext()->RandomIndex(
+                composite_type_ids)];
 
-        // Initially, all composite type ids are available for us to try.  Keep
-        // trying until we run out of options.
-        auto composites_to_try_constructing = composite_type_ids;
-        while (!composites_to_try_constructing.empty()) {
-          // Remove a composite type from the composite types left for us to
-          // try.
-          auto next_composite_to_try_constructing =
-              GetFuzzerContext()->RemoveAtRandomIndex(
-                  &composites_to_try_constructing);
-
-          // Now try to construct a composite of this type, using an appropriate
-          // helper method depending on the kind of composite type.
-          auto composite_type_inst = GetIRContext()->get_def_use_mgr()->GetDef(
-              next_composite_to_try_constructing);
-          switch (composite_type_inst->opcode()) {
-            case SpvOpTypeArray:
-              constructor_arguments = FindComponentsToConstructArray(
-                  *composite_type_inst, type_id_to_available_instructions);
-              break;
-            case SpvOpTypeMatrix:
-              constructor_arguments = FindComponentsToConstructMatrix(
-                  *composite_type_inst, type_id_to_available_instructions);
-              break;
-            case SpvOpTypeStruct:
-              constructor_arguments = FindComponentsToConstructStruct(
-                  *composite_type_inst, type_id_to_available_instructions);
-              break;
-            case SpvOpTypeVector:
-              constructor_arguments = FindComponentsToConstructVector(
-                  *composite_type_inst, type_id_to_available_instructions);
-              break;
-            default:
-              assert(false &&
-                     "The space of possible composite types should be covered "
-                     "by the above cases.");
-              break;
-          }
-          if (!constructor_arguments.empty()) {
-            // We succeeded!  Note the composite type we finally settled on, and
-            // exit from the loop.
-            chosen_composite_type = next_composite_to_try_constructing;
+        // Construct a composite of this type, using an appropriate helper
+        // method depending on the kind of composite type.
+        auto composite_type_inst =
+            GetIRContext()->get_def_use_mgr()->GetDef(chosen_composite_type);
+        switch (composite_type_inst->opcode()) {
+          case SpvOpTypeArray:
+            constructor_arguments = FindComponentsToConstructArray(
+                *composite_type_inst, type_id_to_available_instructions);
             break;
-          }
-        }
-
-        if (!chosen_composite_type) {
-          // We did not manage to make a composite; return 0 to indicate that no
-          // instructions were added.
-          assert(constructor_arguments.empty());
-          return;
+          case SpvOpTypeMatrix:
+            constructor_arguments = FindComponentsToConstructMatrix(
+                *composite_type_inst, type_id_to_available_instructions);
+            break;
+          case SpvOpTypeStruct:
+            constructor_arguments = FindComponentsToConstructStruct(
+                *composite_type_inst, type_id_to_available_instructions);
+            break;
+          case SpvOpTypeVector:
+            constructor_arguments = FindComponentsToConstructVector(
+                *composite_type_inst, type_id_to_available_instructions);
+            break;
+          default:
+            assert(false &&
+                   "The space of possible composite types should be covered "
+                   "by the above cases.");
+            break;
         }
         assert(!constructor_arguments.empty());
 
@@ -164,15 +151,6 @@
       });
 }
 
-void FuzzerPassConstructComposites::RecordAvailableInstruction(
-    opt::Instruction* inst,
-    TypeIdToInstructions* type_id_to_available_instructions) {
-  if (type_id_to_available_instructions->count(inst->type_id()) == 0) {
-    (*type_id_to_available_instructions)[inst->type_id()] = {};
-  }
-  type_id_to_available_instructions->at(inst->type_id()).push_back(inst);
-}
-
 std::vector<uint32_t>
 FuzzerPassConstructComposites::FindComponentsToConstructArray(
     const opt::Instruction& array_type_instruction,
@@ -188,13 +166,6 @@
   auto available_instructions =
       type_id_to_available_instructions.find(element_type_id);
 
-  if (available_instructions == type_id_to_available_instructions.cend()) {
-    // If there are not any instructions available that compute the element type
-    // of the array then we are not in a position to construct a composite with
-    // this array type.
-    return {};
-  }
-
   uint32_t array_length =
       GetIRContext()
           ->get_def_use_mgr()
@@ -203,10 +174,14 @@
 
   std::vector<uint32_t> result;
   for (uint32_t index = 0; index < array_length; index++) {
-    result.push_back(available_instructions
-                         ->second[GetFuzzerContext()->RandomIndex(
-                             available_instructions->second)]
-                         ->result_id());
+    if (available_instructions == type_id_to_available_instructions.cend()) {
+      // No suitable instructions are available, so use a zero constant
+      result.push_back(FindOrCreateZeroConstant(element_type_id, true));
+    } else {
+      result.push_back(
+          available_instructions->second[GetFuzzerContext()->RandomIndex(
+              available_instructions->second)]);
+    }
   }
   return result;
 }
@@ -226,19 +201,17 @@
   auto available_instructions =
       type_id_to_available_instructions.find(element_type_id);
 
-  if (available_instructions == type_id_to_available_instructions.cend()) {
-    // If there are not any instructions available that compute the element type
-    // of the matrix then we are not in a position to construct a composite with
-    // this matrix type.
-    return {};
-  }
   std::vector<uint32_t> result;
   for (uint32_t index = 0;
        index < matrix_type_instruction.GetSingleWordInOperand(1); index++) {
-    result.push_back(available_instructions
-                         ->second[GetFuzzerContext()->RandomIndex(
-                             available_instructions->second)]
-                         ->result_id());
+    if (available_instructions == type_id_to_available_instructions.cend()) {
+      // No suitable components are available, so use a zero constant.
+      result.push_back(FindOrCreateZeroConstant(element_type_id, true));
+    } else {
+      result.push_back(
+          available_instructions->second[GetFuzzerContext()->RandomIndex(
+              available_instructions->second)]);
+    }
   }
   return result;
 }
@@ -261,14 +234,14 @@
     auto available_instructions =
         type_id_to_available_instructions.find(element_type_id);
     if (available_instructions == type_id_to_available_instructions.cend()) {
-      // If there are no such instructions, we cannot construct a composite of
-      // this struct type.
-      return {};
+      // No suitable component is available for this element type, so use a zero
+      // constant.
+      result.push_back(FindOrCreateZeroConstant(element_type_id, true));
+    } else {
+      result.push_back(
+          available_instructions->second[GetFuzzerContext()->RandomIndex(
+              available_instructions->second)]);
     }
-    result.push_back(available_instructions
-                         ->second[GetFuzzerContext()->RandomIndex(
-                             available_instructions->second)]
-                         ->result_id());
   }
   return result;
 }
@@ -323,12 +296,13 @@
   // (otherwise there will not be space left for a vec3).
 
   uint32_t vector_slots_used = 0;
-  // The instructions we will use to construct the vector, in no particular
-  // order at this stage.
-  std::vector<opt::Instruction*> instructions_to_use;
+
+  // The instructions result ids we will use to construct the vector, in no
+  // particular order at this stage.
+  std::vector<uint32_t> result;
 
   while (vector_slots_used < element_count) {
-    std::vector<opt::Instruction*> instructions_to_choose_from;
+    std::vector<uint32_t> instructions_to_choose_from;
     for (auto& entry : smaller_vector_type_id_to_width) {
       if (entry.second >
           std::min(element_count - 1, element_count - vector_slots_used)) {
@@ -343,19 +317,16 @@
                                          available_instructions->second.begin(),
                                          available_instructions->second.end());
     }
-    if (instructions_to_choose_from.empty()) {
-      // We may get unlucky and find that there are not any instructions to
-      // choose from.  In this case we give up constructing a composite of this
-      // vector type.  It might be that we could construct the composite in
-      // another manner, so we could opt to retry a few times here, but it is
-      // simpler to just give up on the basis that this will not happen
-      // frequently.
-      return {};
-    }
-    auto instruction_to_use =
-        instructions_to_choose_from[GetFuzzerContext()->RandomIndex(
-            instructions_to_choose_from)];
-    instructions_to_use.push_back(instruction_to_use);
+    // If there are no instructions to choose from then use a zero constant,
+    // otherwise select one of the instructions at random.
+    uint32_t id_of_instruction_to_use =
+        instructions_to_choose_from.empty()
+            ? FindOrCreateZeroConstant(element_type_id, true)
+            : instructions_to_choose_from[GetFuzzerContext()->RandomIndex(
+                  instructions_to_choose_from)];
+    opt::Instruction* instruction_to_use =
+        GetIRContext()->get_def_use_mgr()->GetDef(id_of_instruction_to_use);
+    result.push_back(instruction_to_use->result_id());
     auto chosen_type =
         GetIRContext()->get_type_mgr()->GetType(instruction_to_use->type_id());
     if (chosen_type->AsVector()) {
@@ -371,14 +342,7 @@
   }
   assert(vector_slots_used == element_count);
 
-  std::vector<uint32_t> result;
-  std::vector<uint32_t> operands;
-  while (!instructions_to_use.empty()) {
-    auto index = GetFuzzerContext()->RandomIndex(instructions_to_use);
-    result.push_back(instructions_to_use[index]->result_id());
-    instructions_to_use.erase(instructions_to_use.begin() + index);
-  }
-  assert(result.size() > 1);
+  GetFuzzerContext()->Shuffle(&result);
   return result;
 }
 
diff --git a/source/fuzz/fuzzer_pass_construct_composites.h b/source/fuzz/fuzzer_pass_construct_composites.h
index cc5f98b..333ac93 100644
--- a/source/fuzz/fuzzer_pass_construct_composites.h
+++ b/source/fuzz/fuzzer_pass_construct_composites.h
@@ -15,7 +15,7 @@
 #ifndef SOURCE_FUZZ_FUZZER_PASS_CONSTRUCT_COMPOSITES_H_
 #define SOURCE_FUZZ_FUZZER_PASS_CONSTRUCT_COMPOSITES_H_
 
-#include <map>
+#include <unordered_map>
 #include <vector>
 
 #include "source/fuzz/fuzzer_pass.h"
@@ -34,18 +34,9 @@
   void Apply() override;
 
  private:
-  // Used to map a type id to relevant instructions whose result type matches
-  // the type id.
-  typedef std::map<uint32_t, std::vector<opt::Instruction*>>
-      TypeIdToInstructions;
-
-  // Considers all instructions that are available at |inst| - instructions
-  // whose results could be packed into a composite - and updates
-  // |type_id_to_available_instructions| so that each such instruction is
-  // associated with its the id of its result type.
-  void RecordAvailableInstruction(
-      opt::Instruction* inst,
-      TypeIdToInstructions* type_id_to_available_instructions);
+  // Used to map a type id to the ids of relevant instructions of the type.
+  using TypeIdToInstructions =
+      std::unordered_map<uint32_t, std::vector<uint32_t>>;
 
   // Requires that |array_type_instruction| has opcode OpTypeArray.
   // Attempts to find suitable instruction result ids from the values of
diff --git a/source/fuzz/transformation_add_type_array.cpp b/source/fuzz/transformation_add_type_array.cpp
index 87b4447..45bc8df 100644
--- a/source/fuzz/transformation_add_type_array.cpp
+++ b/source/fuzz/transformation_add_type_array.cpp
@@ -39,9 +39,11 @@
   }
   auto element_type =
       ir_context->get_type_mgr()->GetType(message_.element_type_id());
-  if (!element_type || element_type->AsFunction()) {
-    // The element type id either does not refer to a type, or refers to a
-    // function type; both are illegal.
+  if (!element_type || element_type->AsFunction() ||
+      fuzzerutil::HasBlockOrBufferBlockDecoration(ir_context,
+                                                  message_.element_type_id())) {
+    // The element type id either does not refer to a type, refers to a function
+    // type, or refers to a block-decorated struct. These cases are all illegal.
     return false;
   }
   auto constant =
diff --git a/source/fuzz/transformation_add_type_array.h b/source/fuzz/transformation_add_type_array.h
index 4767fb8..3162497 100644
--- a/source/fuzz/transformation_add_type_array.h
+++ b/source/fuzz/transformation_add_type_array.h
@@ -33,8 +33,10 @@
 
   // - |message_.fresh_id| must be fresh
   // - |message_.element_type_id| must be the id of a non-function type
+  // - |message_.member_type_id| must not be the result id of an OpTypeStruct
+  //   instruction that has the Block or BufferBlock decoration
   // - |message_.size_id| must be the id of a 32-bit integer constant that is
-  //   positive when interpreted as signed.
+  //   positive when interpreted as signed
   bool IsApplicable(
       opt::IRContext* ir_context,
       const TransformationContext& transformation_context) const override;
diff --git a/source/fuzz/transformation_add_type_struct.cpp b/source/fuzz/transformation_add_type_struct.cpp
index 3d5e15a..d7f0711 100644
--- a/source/fuzz/transformation_add_type_struct.cpp
+++ b/source/fuzz/transformation_add_type_struct.cpp
@@ -39,9 +39,11 @@
   }
   for (auto member_type : message_.member_type_id()) {
     auto type = ir_context->get_type_mgr()->GetType(member_type);
-    if (!type || type->AsFunction()) {
-      // The member type id either does not refer to a type, or refers to a
-      // function type; both are illegal.
+    if (!type || type->AsFunction() ||
+        fuzzerutil::HasBlockOrBufferBlockDecoration(ir_context, member_type)) {
+      // The member type id either does not refer to a type, refers to a
+      // function type, or refers to a block-decorated struct. These cases are
+      // all illegal.
       return false;
     }
 
diff --git a/source/fuzz/transformation_add_type_struct.h b/source/fuzz/transformation_add_type_struct.h
index ea30d9b..6a8dce7 100644
--- a/source/fuzz/transformation_add_type_struct.h
+++ b/source/fuzz/transformation_add_type_struct.h
@@ -37,7 +37,9 @@
   // - |message_.member_type_id| must be a sequence of non-function type ids
   // - |message_.member_type_id| may not contain a result id of an OpTypeStruct
   //   instruction with BuiltIn members (i.e. members of the struct are
-  //   decorated via OpMemberDecorate with BuiltIn decoration).
+  //   decorated via OpMemberDecorate with BuiltIn decoration)
+  // - |message_.member_type_id| may not contain a result id of an OpTypeStruct
+  //   instruction that has the Block or BufferBlock decoration
   bool IsApplicable(
       opt::IRContext* ir_context,
       const TransformationContext& transformation_context) const override;