source/fuzz/transformation_move_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_move_instruction_down.h"
  16
  17 #include "source/fuzz/fuzzer_util.h"
  18 #include "source/fuzz/instruction_descriptor.h"
  19 #include "spirv/unified1/GLSL.std.450.h"
  20
  21 namespace spvtools {
  22 namespace fuzz {
  23 namespace {
  24
  25 const char* const kExtensionSetName = "GLSL.std.450";
  26
  27 std::string GetExtensionSet(opt::IRContext* ir_context,
  28                             const opt::Instruction& op_ext_inst) {
  29   assert(op_ext_inst.opcode() == spv::Op::OpExtInst && "Wrong opcode");
  30
  31   const auto* ext_inst_import = ir_context->get_def_use_mgr()->GetDef(
  32       op_ext_inst.GetSingleWordInOperand(0));
  33   assert(ext_inst_import && "Extension set is not imported");
  34
  35   return ext_inst_import->GetInOperand(0).AsString();
  36 }
  37
  38 }  // namespace
  39
  40 TransformationMoveInstructionDown::TransformationMoveInstructionDown(
  41     protobufs::TransformationMoveInstructionDown message)
  42     : message_(std::move(message)) {}
  43
  44 TransformationMoveInstructionDown::TransformationMoveInstructionDown(
  45     const protobufs::InstructionDescriptor& instruction) {
  46   *message_.mutable_instruction() = instruction;
  47 }
  48
  49 bool TransformationMoveInstructionDown::IsApplicable(
  50     opt::IRContext* ir_context,
  51     const TransformationContext& transformation_context) const {
  52   // |instruction| must be valid.
  53   auto* inst = FindInstruction(message_.instruction(), ir_context);
  54   if (!inst) {
  55     return false;
  56   }
  57
  58   // Instruction's opcode must be supported by this transformation.
  59   if (!IsInstructionSupported(ir_context, *inst)) {
  60     return false;
  61   }
  62
  63   auto* inst_block = ir_context->get_instr_block(inst);
  64   assert(inst_block &&
  65          "Global instructions and function parameters are not supported");
  66
  67   auto inst_it = fuzzerutil::GetIteratorForInstruction(inst_block, inst);
  68   assert(inst_it != inst_block->end() &&
  69          "Can't get an iterator for the instruction");
  70
  71   // |instruction| can't be the last instruction in the block.
  72   auto successor_it = ++inst_it;
  73   if (successor_it == inst_block->end()) {
  74     return false;
  75   }
  76
  77   // We don't risk swapping a memory instruction with an unsupported one.
  78   if (!IsSimpleInstruction(ir_context, *inst) &&
  79       !IsInstructionSupported(ir_context, *successor_it)) {
  80     return false;
  81   }
  82
  83   // It must be safe to swap the instructions without changing the semantics of
  84   // the module.
  85   if (IsInstructionSupported(ir_context, *successor_it) &&
  86       !CanSafelySwapInstructions(ir_context, *inst, *successor_it,
  87                                  *transformation_context.GetFactManager())) {
  88     return false;
  89   }
  90
  91   // Check that we can insert |instruction| after |inst_it|.
  92   auto successors_successor_it = ++inst_it;
  93   if (successors_successor_it == inst_block->end() ||
  94       !fuzzerutil::CanInsertOpcodeBeforeInstruction(inst->opcode(),
  95                                                     successors_successor_it)) {
  96     return false;
  97   }
  98
  99   // Check that |instruction|'s successor doesn't depend on the |instruction|.
 100   if (inst->result_id()) {
 101     for (uint32_t i = 0; i < successor_it->NumInOperands(); ++i) {
 102       const auto& operand = successor_it->GetInOperand(i);
 103       if (spvIsInIdType(operand.type) &&
 104           operand.words[0] == inst->result_id()) {
 105         return false;
 106       }
 107     }
 108   }
 109
 110   return true;
 111 }
 112
 113 void TransformationMoveInstructionDown::Apply(
 114     opt::IRContext* ir_context, TransformationContext* /*unused*/) const {
 115   auto* inst = FindInstruction(message_.instruction(), ir_context);
 116   assert(inst &&
 117          "The instruction should've been validated in the IsApplicable");
 118
 119   auto inst_it = fuzzerutil::GetIteratorForInstruction(
 120       ir_context->get_instr_block(inst), inst);
 121
 122   // Move the instruction down in the block.
 123   inst->InsertAfter(&*++inst_it);
 124
 125   ir_context->InvalidateAnalyses(opt::IRContext::kAnalysisNone);
 126 }
 127
 128 protobufs::Transformation TransformationMoveInstructionDown::ToMessage() const {
 129   protobufs::Transformation result;
 130   *result.mutable_move_instruction_down() = message_;
 131   return result;
 132 }
 133
 134 bool TransformationMoveInstructionDown::IsInstructionSupported(
 135     opt::IRContext* ir_context, const opt::Instruction& inst) {
 136   // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3605):
 137   //  Add support for more instructions here.
 138   return IsSimpleInstruction(ir_context, inst) ||
 139          IsMemoryInstruction(ir_context, inst) || IsBarrierInstruction(inst);
 140 }
 141
 142 bool TransformationMoveInstructionDown::IsSimpleInstruction(
 143     opt::IRContext* ir_context, const opt::Instruction& inst) {
 144   switch (inst.opcode()) {
 145     case spv::Op::OpNop:
 146     case spv::Op::OpUndef:
 147     case spv::Op::OpAccessChain:
 148     case spv::Op::OpInBoundsAccessChain:
 149       // OpAccessChain and OpInBoundsAccessChain are considered simple
 150       // instructions since they result in a pointer to the object in memory,
 151       // not the object itself.
 152     case spv::Op::OpVectorExtractDynamic:
 153     case spv::Op::OpVectorInsertDynamic:
 154     case spv::Op::OpVectorShuffle:
 155     case spv::Op::OpCompositeConstruct:
 156     case spv::Op::OpCompositeExtract:
 157     case spv::Op::OpCompositeInsert:
 158     case spv::Op::OpCopyObject:
 159     case spv::Op::OpTranspose:
 160     case spv::Op::OpConvertFToU:
 161     case spv::Op::OpConvertFToS:
 162     case spv::Op::OpConvertSToF:
 163     case spv::Op::OpConvertUToF:
 164     case spv::Op::OpUConvert:
 165     case spv::Op::OpSConvert:
 166     case spv::Op::OpFConvert:
 167     case spv::Op::OpQuantizeToF16:
 168     case spv::Op::OpSatConvertSToU:
 169     case spv::Op::OpSatConvertUToS:
 170     case spv::Op::OpBitcast:
 171     case spv::Op::OpSNegate:
 172     case spv::Op::OpFNegate:
 173     case spv::Op::OpIAdd:
 174     case spv::Op::OpFAdd:
 175     case spv::Op::OpISub:
 176     case spv::Op::OpFSub:
 177     case spv::Op::OpIMul:
 178     case spv::Op::OpFMul:
 179     case spv::Op::OpUDiv:
 180     case spv::Op::OpSDiv:
 181     case spv::Op::OpFDiv:
 182     case spv::Op::OpUMod:
 183     case spv::Op::OpSRem:
 184     case spv::Op::OpSMod:
 185     case spv::Op::OpFRem:
 186     case spv::Op::OpFMod:
 187     case spv::Op::OpVectorTimesScalar:
 188     case spv::Op::OpMatrixTimesScalar:
 189     case spv::Op::OpVectorTimesMatrix:
 190     case spv::Op::OpMatrixTimesVector:
 191     case spv::Op::OpMatrixTimesMatrix:
 192     case spv::Op::OpOuterProduct:
 193     case spv::Op::OpDot:
 194     case spv::Op::OpIAddCarry:
 195     case spv::Op::OpISubBorrow:
 196     case spv::Op::OpUMulExtended:
 197     case spv::Op::OpSMulExtended:
 198     case spv::Op::OpAny:
 199     case spv::Op::OpAll:
 200     case spv::Op::OpIsNan:
 201     case spv::Op::OpIsInf:
 202     case spv::Op::OpIsFinite:
 203     case spv::Op::OpIsNormal:
 204     case spv::Op::OpSignBitSet:
 205     case spv::Op::OpLessOrGreater:
 206     case spv::Op::OpOrdered:
 207     case spv::Op::OpUnordered:
 208     case spv::Op::OpLogicalEqual:
 209     case spv::Op::OpLogicalNotEqual:
 210     case spv::Op::OpLogicalOr:
 211     case spv::Op::OpLogicalAnd:
 212     case spv::Op::OpLogicalNot:
 213     case spv::Op::OpSelect:
 214     case spv::Op::OpIEqual:
 215     case spv::Op::OpINotEqual:
 216     case spv::Op::OpUGreaterThan:
 217     case spv::Op::OpSGreaterThan:
 218     case spv::Op::OpUGreaterThanEqual:
 219     case spv::Op::OpSGreaterThanEqual:
 220     case spv::Op::OpULessThan:
 221     case spv::Op::OpSLessThan:
 222     case spv::Op::OpULessThanEqual:
 223     case spv::Op::OpSLessThanEqual:
 224     case spv::Op::OpFOrdEqual:
 225     case spv::Op::OpFUnordEqual:
 226     case spv::Op::OpFOrdNotEqual:
 227     case spv::Op::OpFUnordNotEqual:
 228     case spv::Op::OpFOrdLessThan:
 229     case spv::Op::OpFUnordLessThan:
 230     case spv::Op::OpFOrdGreaterThan:
 231     case spv::Op::OpFUnordGreaterThan:
 232     case spv::Op::OpFOrdLessThanEqual:
 233     case spv::Op::OpFUnordLessThanEqual:
 234     case spv::Op::OpFOrdGreaterThanEqual:
 235     case spv::Op::OpFUnordGreaterThanEqual:
 236     case spv::Op::OpShiftRightLogical:
 237     case spv::Op::OpShiftRightArithmetic:
 238     case spv::Op::OpShiftLeftLogical:
 239     case spv::Op::OpBitwiseOr:
 240     case spv::Op::OpBitwiseXor:
 241     case spv::Op::OpBitwiseAnd:
 242     case spv::Op::OpNot:
 243     case spv::Op::OpBitFieldInsert:
 244     case spv::Op::OpBitFieldSExtract:
 245     case spv::Op::OpBitFieldUExtract:
 246     case spv::Op::OpBitReverse:
 247     case spv::Op::OpBitCount:
 248     case spv::Op::OpCopyLogical:
 249       return true;
 250     case spv::Op::OpExtInst: {
 251       const auto* ext_inst_import =
 252           ir_context->get_def_use_mgr()->GetDef(inst.GetSingleWordInOperand(0));
 253
 254       if (ext_inst_import->GetInOperand(0).AsString() != kExtensionSetName) {
 255         return false;
 256       }
 257
 258       switch (static_cast<GLSLstd450>(inst.GetSingleWordInOperand(1))) {
 259         case GLSLstd450Round:
 260         case GLSLstd450RoundEven:
 261         case GLSLstd450Trunc:
 262         case GLSLstd450FAbs:
 263         case GLSLstd450SAbs:
 264         case GLSLstd450FSign:
 265         case GLSLstd450SSign:
 266         case GLSLstd450Floor:
 267         case GLSLstd450Ceil:
 268         case GLSLstd450Fract:
 269         case GLSLstd450Radians:
 270         case GLSLstd450Degrees:
 271         case GLSLstd450Sin:
 272         case GLSLstd450Cos:
 273         case GLSLstd450Tan:
 274         case GLSLstd450Asin:
 275         case GLSLstd450Acos:
 276         case GLSLstd450Atan:
 277         case GLSLstd450Sinh:
 278         case GLSLstd450Cosh:
 279         case GLSLstd450Tanh:
 280         case GLSLstd450Asinh:
 281         case GLSLstd450Acosh:
 282         case GLSLstd450Atanh:
 283         case GLSLstd450Atan2:
 284         case GLSLstd450Pow:
 285         case GLSLstd450Exp:
 286         case GLSLstd450Log:
 287         case GLSLstd450Exp2:
 288         case GLSLstd450Log2:
 289         case GLSLstd450Sqrt:
 290         case GLSLstd450InverseSqrt:
 291         case GLSLstd450Determinant:
 292         case GLSLstd450MatrixInverse:
 293         case GLSLstd450ModfStruct:
 294         case GLSLstd450FMin:
 295         case GLSLstd450UMin:
 296         case GLSLstd450SMin:
 297         case GLSLstd450FMax:
 298         case GLSLstd450UMax:
 299         case GLSLstd450SMax:
 300         case GLSLstd450FClamp:
 301         case GLSLstd450UClamp:
 302         case GLSLstd450SClamp:
 303         case GLSLstd450FMix:
 304         case GLSLstd450IMix:
 305         case GLSLstd450Step:
 306         case GLSLstd450SmoothStep:
 307         case GLSLstd450Fma:
 308         case GLSLstd450FrexpStruct:
 309         case GLSLstd450Ldexp:
 310         case GLSLstd450PackSnorm4x8:
 311         case GLSLstd450PackUnorm4x8:
 312         case GLSLstd450PackSnorm2x16:
 313         case GLSLstd450PackUnorm2x16:
 314         case GLSLstd450PackHalf2x16:
 315         case GLSLstd450PackDouble2x32:
 316         case GLSLstd450UnpackSnorm2x16:
 317         case GLSLstd450UnpackUnorm2x16:
 318         case GLSLstd450UnpackHalf2x16:
 319         case GLSLstd450UnpackSnorm4x8:
 320         case GLSLstd450UnpackUnorm4x8:
 321         case GLSLstd450UnpackDouble2x32:
 322         case GLSLstd450Length:
 323         case GLSLstd450Distance:
 324         case GLSLstd450Cross:
 325         case GLSLstd450Normalize:
 326         case GLSLstd450FaceForward:
 327         case GLSLstd450Reflect:
 328         case GLSLstd450Refract:
 329         case GLSLstd450FindILsb:
 330         case GLSLstd450FindSMsb:
 331         case GLSLstd450FindUMsb:
 332         case GLSLstd450NMin:
 333         case GLSLstd450NMax:
 334         case GLSLstd450NClamp:
 335           return true;
 336         default:
 337           return false;
 338       }
 339     }
 340     default:
 341       return false;
 342   }
 343 }
 344
 345 bool TransformationMoveInstructionDown::IsMemoryReadInstruction(
 346     opt::IRContext* ir_context, const opt::Instruction& inst) {
 347   switch (inst.opcode()) {
 348       // Some simple instructions.
 349     case spv::Op::OpLoad:
 350     case spv::Op::OpCopyMemory:
 351       // Image instructions.
 352     case spv::Op::OpImageSampleImplicitLod:
 353     case spv::Op::OpImageSampleExplicitLod:
 354     case spv::Op::OpImageSampleDrefImplicitLod:
 355     case spv::Op::OpImageSampleDrefExplicitLod:
 356     case spv::Op::OpImageSampleProjImplicitLod:
 357     case spv::Op::OpImageSampleProjExplicitLod:
 358     case spv::Op::OpImageSampleProjDrefImplicitLod:
 359     case spv::Op::OpImageSampleProjDrefExplicitLod:
 360     case spv::Op::OpImageFetch:
 361     case spv::Op::OpImageGather:
 362     case spv::Op::OpImageDrefGather:
 363     case spv::Op::OpImageRead:
 364     case spv::Op::OpImageSparseSampleImplicitLod:
 365     case spv::Op::OpImageSparseSampleExplicitLod:
 366     case spv::Op::OpImageSparseSampleDrefImplicitLod:
 367     case spv::Op::OpImageSparseSampleDrefExplicitLod:
 368     case spv::Op::OpImageSparseSampleProjImplicitLod:
 369     case spv::Op::OpImageSparseSampleProjExplicitLod:
 370     case spv::Op::OpImageSparseSampleProjDrefImplicitLod:
 371     case spv::Op::OpImageSparseSampleProjDrefExplicitLod:
 372     case spv::Op::OpImageSparseFetch:
 373     case spv::Op::OpImageSparseGather:
 374     case spv::Op::OpImageSparseDrefGather:
 375     case spv::Op::OpImageSparseRead:
 376       // Atomic instructions.
 377     case spv::Op::OpAtomicLoad:
 378     case spv::Op::OpAtomicExchange:
 379     case spv::Op::OpAtomicCompareExchange:
 380     case spv::Op::OpAtomicCompareExchangeWeak:
 381     case spv::Op::OpAtomicIIncrement:
 382     case spv::Op::OpAtomicIDecrement:
 383     case spv::Op::OpAtomicIAdd:
 384     case spv::Op::OpAtomicISub:
 385     case spv::Op::OpAtomicSMin:
 386     case spv::Op::OpAtomicUMin:
 387     case spv::Op::OpAtomicSMax:
 388     case spv::Op::OpAtomicUMax:
 389     case spv::Op::OpAtomicAnd:
 390     case spv::Op::OpAtomicOr:
 391     case spv::Op::OpAtomicXor:
 392     case spv::Op::OpAtomicFlagTestAndSet:
 393       return true;
 394       // Extensions.
 395     case spv::Op::OpExtInst: {
 396       if (GetExtensionSet(ir_context, inst) != kExtensionSetName) {
 397         return false;
 398       }
 399
 400       switch (static_cast<GLSLstd450>(inst.GetSingleWordInOperand(1))) {
 401         case GLSLstd450InterpolateAtCentroid:
 402         case GLSLstd450InterpolateAtOffset:
 403         case GLSLstd450InterpolateAtSample:
 404           return true;
 405         default:
 406           return false;
 407       }
 408     }
 409     default:
 410       return false;
 411   }
 412 }
 413
 414 uint32_t TransformationMoveInstructionDown::GetMemoryReadTarget(
 415     opt::IRContext* ir_context, const opt::Instruction& inst) {
 416   (void)ir_context;  // |ir_context| is only used in assertions.
 417   assert(IsMemoryReadInstruction(ir_context, inst) &&
 418          "|inst| is not a memory read instruction");
 419
 420   switch (inst.opcode()) {
 421       // Simple instructions.
 422     case spv::Op::OpLoad:
 423       // Image instructions.
 424     case spv::Op::OpImageSampleImplicitLod:
 425     case spv::Op::OpImageSampleExplicitLod:
 426     case spv::Op::OpImageSampleDrefImplicitLod:
 427     case spv::Op::OpImageSampleDrefExplicitLod:
 428     case spv::Op::OpImageSampleProjImplicitLod:
 429     case spv::Op::OpImageSampleProjExplicitLod:
 430     case spv::Op::OpImageSampleProjDrefImplicitLod:
 431     case spv::Op::OpImageSampleProjDrefExplicitLod:
 432     case spv::Op::OpImageFetch:
 433     case spv::Op::OpImageGather:
 434     case spv::Op::OpImageDrefGather:
 435     case spv::Op::OpImageRead:
 436     case spv::Op::OpImageSparseSampleImplicitLod:
 437     case spv::Op::OpImageSparseSampleExplicitLod:
 438     case spv::Op::OpImageSparseSampleDrefImplicitLod:
 439     case spv::Op::OpImageSparseSampleDrefExplicitLod:
 440     case spv::Op::OpImageSparseSampleProjImplicitLod:
 441     case spv::Op::OpImageSparseSampleProjExplicitLod:
 442     case spv::Op::OpImageSparseSampleProjDrefImplicitLod:
 443     case spv::Op::OpImageSparseSampleProjDrefExplicitLod:
 444     case spv::Op::OpImageSparseFetch:
 445     case spv::Op::OpImageSparseGather:
 446     case spv::Op::OpImageSparseDrefGather:
 447     case spv::Op::OpImageSparseRead:
 448       // Atomic instructions.
 449     case spv::Op::OpAtomicLoad:
 450     case spv::Op::OpAtomicExchange:
 451     case spv::Op::OpAtomicCompareExchange:
 452     case spv::Op::OpAtomicCompareExchangeWeak:
 453     case spv::Op::OpAtomicIIncrement:
 454     case spv::Op::OpAtomicIDecrement:
 455     case spv::Op::OpAtomicIAdd:
 456     case spv::Op::OpAtomicISub:
 457     case spv::Op::OpAtomicSMin:
 458     case spv::Op::OpAtomicUMin:
 459     case spv::Op::OpAtomicSMax:
 460     case spv::Op::OpAtomicUMax:
 461     case spv::Op::OpAtomicAnd:
 462     case spv::Op::OpAtomicOr:
 463     case spv::Op::OpAtomicXor:
 464     case spv::Op::OpAtomicFlagTestAndSet:
 465       return inst.GetSingleWordInOperand(0);
 466     case spv::Op::OpCopyMemory:
 467       return inst.GetSingleWordInOperand(1);
 468     case spv::Op::OpExtInst: {
 469       assert(GetExtensionSet(ir_context, inst) == kExtensionSetName &&
 470              "Extension set is not supported");
 471
 472       switch (static_cast<GLSLstd450>(inst.GetSingleWordInOperand(1))) {
 473         case GLSLstd450InterpolateAtCentroid:
 474         case GLSLstd450InterpolateAtOffset:
 475         case GLSLstd450InterpolateAtSample:
 476           return inst.GetSingleWordInOperand(2);
 477         default:
 478           // This assertion will fail if not all memory read extension
 479           // instructions are handled in the switch.
 480           assert(false && "Not all memory opcodes are handled");
 481           return 0;
 482       }
 483     }
 484     default:
 485       // This assertion will fail if not all memory read opcodes are handled in
 486       // the switch.
 487       assert(false && "Not all memory opcodes are handled");
 488       return 0;
 489   }
 490 }
 491
 492 bool TransformationMoveInstructionDown::IsMemoryWriteInstruction(
 493     opt::IRContext* ir_context, const opt::Instruction& inst) {
 494   switch (inst.opcode()) {
 495       // Simple Instructions.
 496     case spv::Op::OpStore:
 497     case spv::Op::OpCopyMemory:
 498       // Image instructions.
 499     case spv::Op::OpImageWrite:
 500       // Atomic instructions.
 501     case spv::Op::OpAtomicStore:
 502     case spv::Op::OpAtomicExchange:
 503     case spv::Op::OpAtomicCompareExchange:
 504     case spv::Op::OpAtomicCompareExchangeWeak:
 505     case spv::Op::OpAtomicIIncrement:
 506     case spv::Op::OpAtomicIDecrement:
 507     case spv::Op::OpAtomicIAdd:
 508     case spv::Op::OpAtomicISub:
 509     case spv::Op::OpAtomicSMin:
 510     case spv::Op::OpAtomicUMin:
 511     case spv::Op::OpAtomicSMax:
 512     case spv::Op::OpAtomicUMax:
 513     case spv::Op::OpAtomicAnd:
 514     case spv::Op::OpAtomicOr:
 515     case spv::Op::OpAtomicXor:
 516     case spv::Op::OpAtomicFlagTestAndSet:
 517     case spv::Op::OpAtomicFlagClear:
 518       return true;
 519       // Extensions.
 520     case spv::Op::OpExtInst: {
 521       if (GetExtensionSet(ir_context, inst) != kExtensionSetName) {
 522         return false;
 523       }
 524
 525       auto extension = static_cast<GLSLstd450>(inst.GetSingleWordInOperand(1));
 526       return extension == GLSLstd450Modf || extension == GLSLstd450Frexp;
 527     }
 528     default:
 529       return false;
 530   }
 531 }
 532
 533 uint32_t TransformationMoveInstructionDown::GetMemoryWriteTarget(
 534     opt::IRContext* ir_context, const opt::Instruction& inst) {
 535   (void)ir_context;  // |ir_context| is only used in assertions.
 536   assert(IsMemoryWriteInstruction(ir_context, inst) &&
 537          "|inst| is not a memory write instruction");
 538
 539   switch (inst.opcode()) {
 540     case spv::Op::OpStore:
 541     case spv::Op::OpCopyMemory:
 542     case spv::Op::OpImageWrite:
 543     case spv::Op::OpAtomicStore:
 544     case spv::Op::OpAtomicExchange:
 545     case spv::Op::OpAtomicCompareExchange:
 546     case spv::Op::OpAtomicCompareExchangeWeak:
 547     case spv::Op::OpAtomicIIncrement:
 548     case spv::Op::OpAtomicIDecrement:
 549     case spv::Op::OpAtomicIAdd:
 550     case spv::Op::OpAtomicISub:
 551     case spv::Op::OpAtomicSMin:
 552     case spv::Op::OpAtomicUMin:
 553     case spv::Op::OpAtomicSMax:
 554     case spv::Op::OpAtomicUMax:
 555     case spv::Op::OpAtomicAnd:
 556     case spv::Op::OpAtomicOr:
 557     case spv::Op::OpAtomicXor:
 558     case spv::Op::OpAtomicFlagTestAndSet:
 559     case spv::Op::OpAtomicFlagClear:
 560       return inst.GetSingleWordInOperand(0);
 561     case spv::Op::OpExtInst: {
 562       assert(GetExtensionSet(ir_context, inst) == kExtensionSetName &&
 563              "Extension set is not supported");
 564
 565       switch (static_cast<GLSLstd450>(inst.GetSingleWordInOperand(1))) {
 566         case GLSLstd450Modf:
 567         case GLSLstd450Frexp:
 568           return inst.GetSingleWordInOperand(3);
 569         default:
 570           // This assertion will fail if not all memory write extension
 571           // instructions are handled in the switch.
 572           assert(false && "Not all opcodes are handled");
 573           return 0;
 574       }
 575     }
 576     default:
 577       // This assertion will fail if not all memory write opcodes are handled in
 578       // the switch.
 579       assert(false && "Not all opcodes are handled");
 580       return 0;
 581   }
 582 }
 583
 584 bool TransformationMoveInstructionDown::IsMemoryInstruction(
 585     opt::IRContext* ir_context, const opt::Instruction& inst) {
 586   return IsMemoryReadInstruction(ir_context, inst) ||
 587          IsMemoryWriteInstruction(ir_context, inst);
 588 }
 589
 590 bool TransformationMoveInstructionDown::IsBarrierInstruction(
 591     const opt::Instruction& inst) {
 592   switch (inst.opcode()) {
 593     case spv::Op::OpMemoryBarrier:
 594     case spv::Op::OpControlBarrier:
 595     case spv::Op::OpMemoryNamedBarrier:
 596       return true;
 597     default:
 598       return false;
 599   }
 600 }
 601
 602 bool TransformationMoveInstructionDown::CanSafelySwapInstructions(
 603     opt::IRContext* ir_context, const opt::Instruction& a,
 604     const opt::Instruction& b, const FactManager& fact_manager) {
 605   assert(IsInstructionSupported(ir_context, a) &&
 606          IsInstructionSupported(ir_context, b) &&
 607          "Both opcodes must be supported");
 608
 609   // One of opcodes is simple - we can swap them without any side-effects.
 610   if (IsSimpleInstruction(ir_context, a) ||
 611       IsSimpleInstruction(ir_context, b)) {
 612     return true;
 613   }
 614
 615   // Both parameters are either memory instruction or barriers.
 616
 617   // One of the opcodes is a barrier - can't swap them.
 618   if (IsBarrierInstruction(a) || IsBarrierInstruction(b)) {
 619     return false;
 620   }
 621
 622   // Both parameters are memory instructions.
 623
 624   // Both parameters only read from memory - it's OK to swap them.
 625   if (!IsMemoryWriteInstruction(ir_context, a) &&
 626       !IsMemoryWriteInstruction(ir_context, b)) {
 627     return true;
 628   }
 629
 630   // At least one of parameters is a memory read instruction.
 631
 632   // In theory, we can swap two memory instructions, one of which reads
 633   // from the memory, if the read target (the pointer the memory is read from)
 634   // and the write target (the memory is written into):
 635   // - point to different memory regions
 636   // - point to the same region with irrelevant value
 637   // - point to the same region and the region is not used anymore.
 638   //
 639   // However, we can't currently determine if two pointers point to two
 640   // different memory regions. That being said, if two pointers are not
 641   // synonymous, they still might point to the same memory region. For example:
 642   //   %1 = OpVariable ...
 643   //   %2 = OpAccessChain %1 0
 644   //   %3 = OpAccessChain %1 0
 645   // In this pseudo-code, %2 and %3 are not synonymous but point to the same
 646   // memory location. This implies that we can't determine if some memory
 647   // location is not used in the block.
 648   //
 649   // With this in mind, consider two cases (we will build a table for each one):
 650   // - one instruction only reads from memory, the other one only writes to it.
 651   //   S - both point to the same memory region.
 652   //   D - both point to different memory regions.
 653   //   0, 1, 2 - neither, one of or both of the memory regions are irrelevant.
 654   //   |-| - can't swap; |+| - can swap.
 655   //     | 0 | 1 | 2 |
 656   //   S : -   +   +
 657   //   D : +   +   +
 658   // - both instructions write to memory. Notation is the same.
 659   //     | 0 | 1 | 2 |
 660   //   S : *   +   +
 661   //   D : +   +   +
 662   //   * - we can swap two instructions that write into the same non-irrelevant
 663   //   memory region if the written value is the same.
 664   //
 665   // Note that we can't always distinguish between S and D. Also note that
 666   // in case of S, if one of the instructions is marked with
 667   // PointeeValueIsIrrelevant, then the pointee of the other one is irrelevant
 668   // as well even if the instruction is not marked with that fact.
 669   //
 670   // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3723):
 671   //  This procedure can be improved when we can determine if two pointers point
 672   //  to different memory regions.
 673
 674   // From now on we will denote an instruction that:
 675   // - only reads from memory - R
 676   // - only writes into memory - W
 677   // - reads and writes - RW
 678   //
 679   // Both |a| and |b| can be either W or RW at this point. Additionally, at most
 680   // one of them can be R. The procedure below checks all possible combinations
 681   // of R, W and RW according to the tables above. We conservatively assume that
 682   // both |a| and |b| point to the same memory region.
 683
 684   auto memory_is_irrelevant = [ir_context, &fact_manager](uint32_t id) {
 685     const auto* inst = ir_context->get_def_use_mgr()->GetDef(id);
 686     if (!inst->type_id()) {
 687       return false;
 688     }
 689
 690     const auto* type = ir_context->get_type_mgr()->GetType(inst->type_id());
 691     assert(type && "|id| has invalid type");
 692
 693     if (!type->AsPointer()) {
 694       return false;
 695     }
 696
 697     return fact_manager.PointeeValueIsIrrelevant(id);
 698   };
 699
 700   if (IsMemoryWriteInstruction(ir_context, a) &&
 701       IsMemoryWriteInstruction(ir_context, b) &&
 702       (memory_is_irrelevant(GetMemoryWriteTarget(ir_context, a)) ||
 703        memory_is_irrelevant(GetMemoryWriteTarget(ir_context, b)))) {
 704     // We ignore the case when the written value is the same. This is because
 705     // the written value might not be equal to any of the instruction's
 706     // operands.
 707     return true;
 708   }
 709
 710   if (IsMemoryReadInstruction(ir_context, a) &&
 711       IsMemoryWriteInstruction(ir_context, b) &&
 712       !memory_is_irrelevant(GetMemoryReadTarget(ir_context, a)) &&
 713       !memory_is_irrelevant(GetMemoryWriteTarget(ir_context, b))) {
 714     return false;
 715   }
 716
 717   if (IsMemoryWriteInstruction(ir_context, a) &&
 718       IsMemoryReadInstruction(ir_context, b) &&
 719       !memory_is_irrelevant(GetMemoryWriteTarget(ir_context, a)) &&
 720       !memory_is_irrelevant(GetMemoryReadTarget(ir_context, b))) {
 721     return false;
 722   }
 723
 724   return IsMemoryReadInstruction(ir_context, a) ||
 725          IsMemoryReadInstruction(ir_context, b);
 726 }
 727
 728 std::unordered_set<uint32_t> TransformationMoveInstructionDown::GetFreshIds()
 729     const {
 730   return std::unordered_set<uint32_t>();
 731 }
 732
 733 }  // namespace fuzz
 734 }  // namespace spvtools