source/fuzz/transformation_propagate_instruction_down.cpp

   1 // Copyright (c) 2020 Vasyl Teliman
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #include "source/fuzz/transformation_propagate_instruction_down.h"
  16
  17 #include "source/fuzz/fuzzer_util.h"
  18 #include "source/fuzz/instruction_descriptor.h"
  19
  20 namespace spvtools {
  21 namespace fuzz {
  22
  23 TransformationPropagateInstructionDown::TransformationPropagateInstructionDown(
  24     protobufs::TransformationPropagateInstructionDown message)
  25     : message_(std::move(message)) {}
  26
  27 TransformationPropagateInstructionDown::TransformationPropagateInstructionDown(
  28     uint32_t block_id, uint32_t phi_fresh_id,
  29     const std::map<uint32_t, uint32_t>& successor_id_to_fresh_id) {
  30   message_.set_block_id(block_id);
  31   message_.set_phi_fresh_id(phi_fresh_id);
  32   *message_.mutable_successor_id_to_fresh_id() =
  33       fuzzerutil::MapToRepeatedUInt32Pair(successor_id_to_fresh_id);
  34 }
  35
  36 bool TransformationPropagateInstructionDown::IsApplicable(
  37     opt::IRContext* ir_context,
  38     const TransformationContext& transformation_context) const {
  39   // Check that we can apply this transformation to the |block_id|.
  40   if (!IsApplicableToBlock(ir_context, message_.block_id())) {
  41     return false;
  42   }
  43
  44   const auto successor_id_to_fresh_id =
  45       fuzzerutil::RepeatedUInt32PairToMap(message_.successor_id_to_fresh_id());
  46
  47   for (auto id : GetAcceptableSuccessors(ir_context, message_.block_id())) {
  48     // Each successor must have a fresh id in the |successor_id_to_fresh_id|
  49     // map, unless overflow ids are available.
  50     if (!successor_id_to_fresh_id.count(id) &&
  51         !transformation_context.GetOverflowIdSource()->HasOverflowIds()) {
  52       return false;
  53     }
  54   }
  55
  56   std::vector<uint32_t> maybe_fresh_ids = {message_.phi_fresh_id()};
  57   maybe_fresh_ids.reserve(successor_id_to_fresh_id.size());
  58   for (const auto& entry : successor_id_to_fresh_id) {
  59     maybe_fresh_ids.push_back(entry.second);
  60   }
  61
  62   // All ids must be unique and fresh.
  63   return !fuzzerutil::HasDuplicates(maybe_fresh_ids) &&
  64          std::all_of(maybe_fresh_ids.begin(), maybe_fresh_ids.end(),
  65                      [ir_context](uint32_t id) {
  66                        return fuzzerutil::IsFreshId(ir_context, id);
  67                      });
  68 }
  69
  70 void TransformationPropagateInstructionDown::Apply(
  71     opt::IRContext* ir_context,
  72     TransformationContext* transformation_context) const {
  73   // Get instruction to propagate down. There must be one.
  74   auto* inst_to_propagate =
  75       GetInstructionToPropagate(ir_context, message_.block_id());
  76   assert(inst_to_propagate && "There must be an instruction to propagate");
  77
  78   auto successor_id_to_fresh_id =
  79       fuzzerutil::RepeatedUInt32PairToMap(message_.successor_id_to_fresh_id());
  80   std::vector<uint32_t> created_inst_ids;
  81   auto successor_ids = GetAcceptableSuccessors(ir_context, message_.block_id());
  82
  83   // Clone |inst_to_propagate| into every successor.
  84   for (auto successor_id : successor_ids) {
  85     std::unique_ptr<opt::Instruction> clone(
  86         inst_to_propagate->Clone(ir_context));
  87
  88     uint32_t new_result_id;
  89     if (successor_id_to_fresh_id.count(successor_id)) {
  90       new_result_id = successor_id_to_fresh_id.at(successor_id);
  91     } else {
  92       assert(transformation_context->GetOverflowIdSource()->HasOverflowIds() &&
  93              "Overflow ids must be available");
  94       new_result_id =
  95           transformation_context->GetOverflowIdSource()->GetNextOverflowId();
  96       successor_id_to_fresh_id[successor_id] = new_result_id;
  97     }
  98
  99     clone->SetResultId(new_result_id);
 100     fuzzerutil::UpdateModuleIdBound(ir_context, new_result_id);
 101
 102     auto* insert_before_inst = GetFirstInsertBeforeInstruction(
 103         ir_context, successor_id, clone->opcode());
 104     assert(insert_before_inst && "Can't insert into one of the successors");
 105
 106     insert_before_inst->InsertBefore(std::move(clone));
 107     created_inst_ids.push_back(new_result_id);
 108   }
 109
 110   // Add an OpPhi instruction into the module if possible.
 111   if (auto merge_block_id = GetOpPhiBlockId(
 112           ir_context, message_.block_id(), *inst_to_propagate, successor_ids)) {
 113     opt::Instruction::OperandList in_operands;
 114     std::unordered_set<uint32_t> visited_predecessors;
 115     for (auto predecessor_id : ir_context->cfg()->preds(merge_block_id)) {
 116       if (visited_predecessors.count(predecessor_id)) {
 117         // Merge block might have multiple identical predecessors.
 118         continue;
 119       }
 120
 121       visited_predecessors.insert(predecessor_id);
 122
 123       const auto* dominator_analysis = ir_context->GetDominatorAnalysis(
 124           ir_context->cfg()->block(message_.block_id())->GetParent());
 125
 126       // Find the successor of |source_block| that dominates the predecessor of
 127       // the merge block |predecessor_id|.
 128       auto it = std::find_if(
 129           successor_ids.begin(), successor_ids.end(),
 130           [predecessor_id, dominator_analysis](uint32_t successor_id) {
 131             return dominator_analysis->Dominates(successor_id, predecessor_id);
 132           });
 133
 134       // OpPhi requires a single operand pair for every predecessor of the
 135       // OpPhi's block.
 136       assert(it != successor_ids.end() && "Unable to insert OpPhi");
 137
 138       in_operands.push_back(
 139           {SPV_OPERAND_TYPE_ID, {successor_id_to_fresh_id.at(*it)}});
 140       in_operands.push_back({SPV_OPERAND_TYPE_ID, {predecessor_id}});
 141     }
 142
 143     ir_context->cfg()
 144         ->block(merge_block_id)
 145         ->begin()
 146         ->InsertBefore(MakeUnique<opt::Instruction>(
 147             ir_context, spv::Op::OpPhi, inst_to_propagate->type_id(),
 148             message_.phi_fresh_id(), std::move(in_operands)));
 149
 150     fuzzerutil::UpdateModuleIdBound(ir_context, message_.phi_fresh_id());
 151     created_inst_ids.push_back(message_.phi_fresh_id());
 152   }
 153
 154   // Make sure analyses are updated when we adjust users of |inst_to_propagate|.
 155   ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
 156
 157   // Copy decorations from the original instructions to its propagated copies.
 158   for (auto id : created_inst_ids) {
 159     ir_context->get_decoration_mgr()->CloneDecorations(
 160         inst_to_propagate->result_id(), id);
 161   }
 162
 163   // Remove all decorations from the original instruction.
 164   ir_context->get_decoration_mgr()->RemoveDecorationsFrom(
 165       inst_to_propagate->result_id());
 166
 167   // Update every use of the |inst_to_propagate| with a result id of some of the
 168   // newly created instructions.
 169   ir_context->get_def_use_mgr()->ForEachUse(
 170       inst_to_propagate, [ir_context, &created_inst_ids](
 171                              opt::Instruction* user, uint32_t operand_index) {
 172         assert(ir_context->get_instr_block(user) &&
 173                "All decorations should have already been adjusted");
 174
 175         auto in_operand_index =
 176             fuzzerutil::InOperandIndexFromOperandIndex(*user, operand_index);
 177         for (auto id : created_inst_ids) {
 178           if (fuzzerutil::IdIsAvailableAtUse(ir_context, user, in_operand_index,
 179                                              id)) {
 180             user->SetInOperand(in_operand_index, {id});
 181             return;
 182           }
 183         }
 184
 185         // Every user of |inst_to_propagate| must be updated since we will
 186         // remove that instruction from the module.
 187         assert(false && "Every user of |inst_to_propagate| must be updated");
 188       });
 189
 190   // Add synonyms about newly created instructions.
 191   assert(inst_to_propagate->HasResultId() &&
 192          "Result id is required to add facts");
 193   if (transformation_context->GetFactManager()->IdIsIrrelevant(
 194           inst_to_propagate->result_id())) {
 195     for (auto id : created_inst_ids) {
 196       transformation_context->GetFactManager()->AddFactIdIsIrrelevant(id);
 197     }
 198   } else {
 199     std::vector<uint32_t> non_irrelevant_ids;
 200     for (auto id : created_inst_ids) {
 201       // |id| can be irrelevant implicitly (e.g. if we propagate it into a dead
 202       // block).
 203       if (!transformation_context->GetFactManager()->IdIsIrrelevant(id)) {
 204         non_irrelevant_ids.push_back(id);
 205       }
 206     }
 207
 208     if (transformation_context->GetFactManager()->PointeeValueIsIrrelevant(
 209             inst_to_propagate->result_id())) {
 210       for (auto id : non_irrelevant_ids) {
 211         transformation_context->GetFactManager()
 212             ->AddFactValueOfPointeeIsIrrelevant(id);
 213       }
 214     }
 215
 216     for (auto id : non_irrelevant_ids) {
 217       transformation_context->GetFactManager()->AddFactDataSynonym(
 218           MakeDataDescriptor(id, {}),
 219           MakeDataDescriptor(non_irrelevant_ids[0], {}));
 220     }
 221   }
 222
 223   // Remove the propagated instruction from the module.
 224   ir_context->KillInst(inst_to_propagate);
 225
 226   // We've adjusted all users - make sure these changes are analyzed.
 227   ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
 228 }
 229
 230 protobufs::Transformation TransformationPropagateInstructionDown::ToMessage()
 231     const {
 232   protobufs::Transformation result;
 233   *result.mutable_propagate_instruction_down() = message_;
 234   return result;
 235 }
 236
 237 bool TransformationPropagateInstructionDown::IsOpcodeSupported(spv::Op opcode) {
 238   // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3605):
 239   //  We only support "simple" instructions that don't work with memory.
 240   //  We should extend this so that we support the ones that modify the memory
 241   //  too.
 242   switch (opcode) {
 243     case spv::Op::OpUndef:
 244     case spv::Op::OpAccessChain:
 245     case spv::Op::OpInBoundsAccessChain:
 246     case spv::Op::OpArrayLength:
 247     case spv::Op::OpVectorExtractDynamic:
 248     case spv::Op::OpVectorInsertDynamic:
 249     case spv::Op::OpVectorShuffle:
 250     case spv::Op::OpCompositeConstruct:
 251     case spv::Op::OpCompositeExtract:
 252     case spv::Op::OpCompositeInsert:
 253     case spv::Op::OpCopyObject:
 254     case spv::Op::OpTranspose:
 255     case spv::Op::OpConvertFToU:
 256     case spv::Op::OpConvertFToS:
 257     case spv::Op::OpConvertSToF:
 258     case spv::Op::OpConvertUToF:
 259     case spv::Op::OpUConvert:
 260     case spv::Op::OpSConvert:
 261     case spv::Op::OpFConvert:
 262     case spv::Op::OpQuantizeToF16:
 263     case spv::Op::OpSatConvertSToU:
 264     case spv::Op::OpSatConvertUToS:
 265     case spv::Op::OpBitcast:
 266     case spv::Op::OpSNegate:
 267     case spv::Op::OpFNegate:
 268     case spv::Op::OpIAdd:
 269     case spv::Op::OpFAdd:
 270     case spv::Op::OpISub:
 271     case spv::Op::OpFSub:
 272     case spv::Op::OpIMul:
 273     case spv::Op::OpFMul:
 274     case spv::Op::OpUDiv:
 275     case spv::Op::OpSDiv:
 276     case spv::Op::OpFDiv:
 277     case spv::Op::OpUMod:
 278     case spv::Op::OpSRem:
 279     case spv::Op::OpSMod:
 280     case spv::Op::OpFRem:
 281     case spv::Op::OpFMod:
 282     case spv::Op::OpVectorTimesScalar:
 283     case spv::Op::OpMatrixTimesScalar:
 284     case spv::Op::OpVectorTimesMatrix:
 285     case spv::Op::OpMatrixTimesVector:
 286     case spv::Op::OpMatrixTimesMatrix:
 287     case spv::Op::OpOuterProduct:
 288     case spv::Op::OpDot:
 289     case spv::Op::OpIAddCarry:
 290     case spv::Op::OpISubBorrow:
 291     case spv::Op::OpUMulExtended:
 292     case spv::Op::OpSMulExtended:
 293     case spv::Op::OpAny:
 294     case spv::Op::OpAll:
 295     case spv::Op::OpIsNan:
 296     case spv::Op::OpIsInf:
 297     case spv::Op::OpIsFinite:
 298     case spv::Op::OpIsNormal:
 299     case spv::Op::OpSignBitSet:
 300     case spv::Op::OpLessOrGreater:
 301     case spv::Op::OpOrdered:
 302     case spv::Op::OpUnordered:
 303     case spv::Op::OpLogicalEqual:
 304     case spv::Op::OpLogicalNotEqual:
 305     case spv::Op::OpLogicalOr:
 306     case spv::Op::OpLogicalAnd:
 307     case spv::Op::OpLogicalNot:
 308     case spv::Op::OpSelect:
 309     case spv::Op::OpIEqual:
 310     case spv::Op::OpINotEqual:
 311     case spv::Op::OpUGreaterThan:
 312     case spv::Op::OpSGreaterThan:
 313     case spv::Op::OpUGreaterThanEqual:
 314     case spv::Op::OpSGreaterThanEqual:
 315     case spv::Op::OpULessThan:
 316     case spv::Op::OpSLessThan:
 317     case spv::Op::OpULessThanEqual:
 318     case spv::Op::OpSLessThanEqual:
 319     case spv::Op::OpFOrdEqual:
 320     case spv::Op::OpFUnordEqual:
 321     case spv::Op::OpFOrdNotEqual:
 322     case spv::Op::OpFUnordNotEqual:
 323     case spv::Op::OpFOrdLessThan:
 324     case spv::Op::OpFUnordLessThan:
 325     case spv::Op::OpFOrdGreaterThan:
 326     case spv::Op::OpFUnordGreaterThan:
 327     case spv::Op::OpFOrdLessThanEqual:
 328     case spv::Op::OpFUnordLessThanEqual:
 329     case spv::Op::OpFOrdGreaterThanEqual:
 330     case spv::Op::OpFUnordGreaterThanEqual:
 331     case spv::Op::OpShiftRightLogical:
 332     case spv::Op::OpShiftRightArithmetic:
 333     case spv::Op::OpShiftLeftLogical:
 334     case spv::Op::OpBitwiseOr:
 335     case spv::Op::OpBitwiseXor:
 336     case spv::Op::OpBitwiseAnd:
 337     case spv::Op::OpNot:
 338     case spv::Op::OpBitFieldInsert:
 339     case spv::Op::OpBitFieldSExtract:
 340     case spv::Op::OpBitFieldUExtract:
 341     case spv::Op::OpBitReverse:
 342     case spv::Op::OpBitCount:
 343     case spv::Op::OpCopyLogical:
 344     case spv::Op::OpPtrEqual:
 345     case spv::Op::OpPtrNotEqual:
 346       return true;
 347     default:
 348       return false;
 349   }
 350 }
 351
 352 opt::Instruction*
 353 TransformationPropagateInstructionDown::GetInstructionToPropagate(
 354     opt::IRContext* ir_context, uint32_t block_id) {
 355   auto* block = ir_context->cfg()->block(block_id);
 356   assert(block && "|block_id| is invalid");
 357
 358   for (auto it = block->rbegin(); it != block->rend(); ++it) {
 359     if (!it->result_id() || !it->type_id() ||
 360         !IsOpcodeSupported(it->opcode())) {
 361       continue;
 362     }
 363
 364     auto all_users_from_different_blocks =
 365         ir_context->get_def_use_mgr()->WhileEachUser(
 366             &*it, [ir_context, block](opt::Instruction* user) {
 367               return ir_context->get_instr_block(user) != block;
 368             });
 369
 370     if (!all_users_from_different_blocks) {
 371       // We can't propagate an instruction if it's used in the same block.
 372       continue;
 373     }
 374
 375     return &*it;
 376   }
 377
 378   return nullptr;
 379 }
 380
 381 bool TransformationPropagateInstructionDown::IsApplicableToBlock(
 382     opt::IRContext* ir_context, uint32_t block_id) {
 383   // Check that |block_id| is valid.
 384   const auto* block = fuzzerutil::MaybeFindBlock(ir_context, block_id);
 385   if (!block) {
 386     return false;
 387   }
 388
 389   // |block| must be reachable.
 390   if (!ir_context->IsReachable(*block)) {
 391     return false;
 392   }
 393
 394   // The block must have an instruction to propagate.
 395   const auto* inst_to_propagate =
 396       GetInstructionToPropagate(ir_context, block_id);
 397   if (!inst_to_propagate) {
 398     return false;
 399   }
 400
 401   // Check that |block| has successors.
 402   auto successor_ids = GetAcceptableSuccessors(ir_context, block_id);
 403   if (successor_ids.empty()) {
 404     return false;
 405   }
 406
 407   // Check that |successor_block| doesn't have any OpPhi instructions that
 408   // use |inst|.
 409   for (auto successor_id : successor_ids) {
 410     for (const auto& maybe_phi_inst : *ir_context->cfg()->block(successor_id)) {
 411       if (maybe_phi_inst.opcode() != spv::Op::OpPhi) {
 412         // OpPhis can be intermixed with OpLine and OpNoLine.
 413         continue;
 414       }
 415
 416       for (uint32_t i = 0; i < maybe_phi_inst.NumInOperands(); i += 2) {
 417         if (maybe_phi_inst.GetSingleWordInOperand(i) ==
 418             inst_to_propagate->result_id()) {
 419           return false;
 420         }
 421       }
 422     }
 423   }
 424
 425   // Get the result id of the block we will insert OpPhi instruction into.
 426   // This is either 0 or a result id of some merge block in the function.
 427   auto phi_block_id =
 428       GetOpPhiBlockId(ir_context, block_id, *inst_to_propagate, successor_ids);
 429
 430   const auto* dominator_analysis =
 431       ir_context->GetDominatorAnalysis(block->GetParent());
 432
 433   // Make sure we can adjust all users of the propagated instruction.
 434   return ir_context->get_def_use_mgr()->WhileEachUse(
 435       inst_to_propagate,
 436       [ir_context, &successor_ids, dominator_analysis, phi_block_id](
 437           opt::Instruction* user, uint32_t index) {
 438         const auto* user_block = ir_context->get_instr_block(user);
 439
 440         if (!user_block) {
 441           // |user| might be a global instruction (e.g. OpDecorate).
 442           return true;
 443         }
 444
 445         // Check that at least one of the ids in |successor_ids| or a
 446         // |phi_block_id| dominates |user|'s block (or its predecessor if the
 447         // user is an OpPhi). We can't use fuzzerutil::IdIsAvailableAtUse since
 448         // the id in question hasn't yet been created in the module.
 449         auto block_id_to_dominate = user->opcode() == spv::Op::OpPhi
 450                                         ? user->GetSingleWordOperand(index + 1)
 451                                         : user_block->id();
 452
 453         if (phi_block_id != 0 &&
 454             dominator_analysis->Dominates(phi_block_id, block_id_to_dominate)) {
 455           return true;
 456         }
 457
 458         return std::any_of(
 459             successor_ids.begin(), successor_ids.end(),
 460             [dominator_analysis, block_id_to_dominate](uint32_t id) {
 461               return dominator_analysis->Dominates(id, block_id_to_dominate);
 462             });
 463       });
 464 }
 465
 466 opt::Instruction*
 467 TransformationPropagateInstructionDown::GetFirstInsertBeforeInstruction(
 468     opt::IRContext* ir_context, uint32_t block_id, spv::Op opcode) {
 469   auto* block = ir_context->cfg()->block(block_id);
 470
 471   auto it = block->begin();
 472
 473   while (it != block->end() &&
 474          !fuzzerutil::CanInsertOpcodeBeforeInstruction(opcode, it)) {
 475     ++it;
 476   }
 477
 478   return it == block->end() ? nullptr : &*it;
 479 }
 480
 481 std::unordered_set<uint32_t>
 482 TransformationPropagateInstructionDown::GetAcceptableSuccessors(
 483     opt::IRContext* ir_context, uint32_t block_id) {
 484   const auto* block = ir_context->cfg()->block(block_id);
 485   assert(block && "|block_id| is invalid");
 486
 487   const auto* inst = GetInstructionToPropagate(ir_context, block_id);
 488   assert(inst && "The block must have an instruction to propagate");
 489
 490   std::unordered_set<uint32_t> result;
 491   block->ForEachSuccessorLabel([ir_context, &result,
 492                                 inst](uint32_t successor_id) {
 493     if (result.count(successor_id)) {
 494       return;
 495     }
 496
 497     auto* successor_block = ir_context->cfg()->block(successor_id);
 498
 499     // We can't propagate |inst| into |successor_block| if the latter is not
 500     // dominated by the |inst|'s dependencies.
 501     if (!inst->WhileEachInId([ir_context, successor_block](const uint32_t* id) {
 502           return fuzzerutil::IdIsAvailableBeforeInstruction(
 503               ir_context, &*successor_block->begin(), *id);
 504         })) {
 505       return;
 506     }
 507
 508     // We don't propagate any "special" instructions (e.g. OpSelectionMerge
 509     // etc), thus, insertion point must always exist if the module is valid.
 510     assert(GetFirstInsertBeforeInstruction(ir_context, successor_id,
 511                                            inst->opcode()) &&
 512            "There must exist an insertion point.");
 513
 514     result.insert(successor_id);
 515   });
 516
 517   return result;
 518 }
 519
 520 uint32_t TransformationPropagateInstructionDown::GetOpPhiBlockId(
 521     opt::IRContext* ir_context, uint32_t block_id,
 522     const opt::Instruction& inst_to_propagate,
 523     const std::unordered_set<uint32_t>& successor_ids) {
 524   const auto* block = ir_context->cfg()->block(block_id);
 525
 526   // |block_id| must belong to some construct.
 527   auto merge_block_id =
 528       block->GetMergeInst()
 529           ? block->GetMergeInst()->GetSingleWordInOperand(0)
 530           : ir_context->GetStructuredCFGAnalysis()->MergeBlock(block_id);
 531   if (!merge_block_id) {
 532     return 0;
 533   }
 534
 535   const auto* dominator_analysis =
 536       ir_context->GetDominatorAnalysis(block->GetParent());
 537
 538   // Check that |merge_block_id| is reachable in the CFG and |block_id|
 539   // dominates |merge_block_id|.
 540   if (!ir_context->IsReachable(*ir_context->cfg()->block(merge_block_id)) ||
 541       !dominator_analysis->Dominates(block_id, merge_block_id)) {
 542     return 0;
 543   }
 544
 545   // We can't insert an OpPhi into |merge_block_id| if it's an acceptable
 546   // successor of |block_id|.
 547   if (successor_ids.count(merge_block_id)) {
 548     return 0;
 549   }
 550
 551   // All predecessors of the merge block must be dominated by at least one
 552   // successor of the |block_id|.
 553   assert(!ir_context->cfg()->preds(merge_block_id).empty() &&
 554          "Merge block must be reachable");
 555   for (auto predecessor_id : ir_context->cfg()->preds(merge_block_id)) {
 556     if (std::none_of(
 557             successor_ids.begin(), successor_ids.end(),
 558             [dominator_analysis, predecessor_id](uint32_t successor_id) {
 559               return dominator_analysis->Dominates(successor_id,
 560                                                    predecessor_id);
 561             })) {
 562       return 0;
 563     }
 564   }
 565
 566   const auto* propagate_type =
 567       ir_context->get_type_mgr()->GetType(inst_to_propagate.type_id());
 568   assert(propagate_type && "|inst_to_propagate| must have a valid type");
 569
 570   // VariablePointers capability implicitly declares
 571   // VariablePointersStorageBuffer. We need those capabilities since otherwise
 572   // OpPhi instructions cannot have operands of pointer types.
 573   if (propagate_type->AsPointer() &&
 574       !ir_context->get_feature_mgr()->HasCapability(
 575           spv::Capability::VariablePointersStorageBuffer)) {
 576     return 0;
 577   }
 578
 579   return merge_block_id;
 580 }
 581
 582 std::unordered_set<uint32_t>
 583 TransformationPropagateInstructionDown::GetFreshIds() const {
 584   std::unordered_set<uint32_t> result = {message_.phi_fresh_id()};
 585   for (const auto& pair : message_.successor_id_to_fresh_id()) {
 586     result.insert(pair.second());
 587   }
 588   return result;
 589 }
 590
 591 }  // namespace fuzz
 592 }  // namespace spvtools