| // Copyright (c) 2020 Vasyl Teliman |
| // |
| // 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_propagate_instruction_down.h" |
| |
| #include "source/fuzz/fuzzer_util.h" |
| #include "source/fuzz/instruction_descriptor.h" |
| |
| namespace spvtools { |
| namespace fuzz { |
| |
| TransformationPropagateInstructionDown::TransformationPropagateInstructionDown( |
| protobufs::TransformationPropagateInstructionDown message) |
| : message_(std::move(message)) {} |
| |
| TransformationPropagateInstructionDown::TransformationPropagateInstructionDown( |
| uint32_t block_id, uint32_t phi_fresh_id, |
| const std::map<uint32_t, uint32_t>& successor_id_to_fresh_id) { |
| message_.set_block_id(block_id); |
| message_.set_phi_fresh_id(phi_fresh_id); |
| *message_.mutable_successor_id_to_fresh_id() = |
| fuzzerutil::MapToRepeatedUInt32Pair(successor_id_to_fresh_id); |
| } |
| |
| bool TransformationPropagateInstructionDown::IsApplicable( |
| opt::IRContext* ir_context, |
| const TransformationContext& transformation_context) const { |
| // Check that we can apply this transformation to the |block_id|. |
| if (!IsApplicableToBlock(ir_context, message_.block_id())) { |
| return false; |
| } |
| |
| const auto successor_id_to_fresh_id = |
| fuzzerutil::RepeatedUInt32PairToMap(message_.successor_id_to_fresh_id()); |
| |
| for (auto id : GetAcceptableSuccessors(ir_context, message_.block_id())) { |
| // Each successor must have a fresh id in the |successor_id_to_fresh_id| |
| // map, unless overflow ids are available. |
| if (!successor_id_to_fresh_id.count(id) && |
| !transformation_context.GetOverflowIdSource()->HasOverflowIds()) { |
| return false; |
| } |
| } |
| |
| std::vector<uint32_t> maybe_fresh_ids = {message_.phi_fresh_id()}; |
| maybe_fresh_ids.reserve(successor_id_to_fresh_id.size()); |
| for (const auto& entry : successor_id_to_fresh_id) { |
| maybe_fresh_ids.push_back(entry.second); |
| } |
| |
| // All ids must be unique and fresh. |
| return !fuzzerutil::HasDuplicates(maybe_fresh_ids) && |
| std::all_of(maybe_fresh_ids.begin(), maybe_fresh_ids.end(), |
| [ir_context](uint32_t id) { |
| return fuzzerutil::IsFreshId(ir_context, id); |
| }); |
| } |
| |
| void TransformationPropagateInstructionDown::Apply( |
| opt::IRContext* ir_context, |
| TransformationContext* transformation_context) const { |
| // Get instruction to propagate down. There must be one. |
| auto* inst_to_propagate = |
| GetInstructionToPropagate(ir_context, message_.block_id()); |
| assert(inst_to_propagate && "There must be an instruction to propagate"); |
| |
| auto successor_id_to_fresh_id = |
| fuzzerutil::RepeatedUInt32PairToMap(message_.successor_id_to_fresh_id()); |
| std::vector<uint32_t> created_inst_ids; |
| auto successor_ids = GetAcceptableSuccessors(ir_context, message_.block_id()); |
| |
| // Clone |inst_to_propagate| into every successor. |
| for (auto successor_id : successor_ids) { |
| std::unique_ptr<opt::Instruction> clone( |
| inst_to_propagate->Clone(ir_context)); |
| |
| uint32_t new_result_id; |
| if (successor_id_to_fresh_id.count(successor_id)) { |
| new_result_id = successor_id_to_fresh_id.at(successor_id); |
| } else { |
| assert(transformation_context->GetOverflowIdSource()->HasOverflowIds() && |
| "Overflow ids must be available"); |
| new_result_id = |
| transformation_context->GetOverflowIdSource()->GetNextOverflowId(); |
| successor_id_to_fresh_id[successor_id] = new_result_id; |
| } |
| |
| clone->SetResultId(new_result_id); |
| fuzzerutil::UpdateModuleIdBound(ir_context, new_result_id); |
| |
| auto* insert_before_inst = GetFirstInsertBeforeInstruction( |
| ir_context, successor_id, clone->opcode()); |
| assert(insert_before_inst && "Can't insert into one of the successors"); |
| |
| insert_before_inst->InsertBefore(std::move(clone)); |
| created_inst_ids.push_back(new_result_id); |
| } |
| |
| // Add an OpPhi instruction into the module if possible. |
| if (auto merge_block_id = GetOpPhiBlockId( |
| ir_context, message_.block_id(), *inst_to_propagate, successor_ids)) { |
| opt::Instruction::OperandList in_operands; |
| std::unordered_set<uint32_t> visited_predecessors; |
| for (auto predecessor_id : ir_context->cfg()->preds(merge_block_id)) { |
| if (visited_predecessors.count(predecessor_id)) { |
| // Merge block might have multiple identical predecessors. |
| continue; |
| } |
| |
| visited_predecessors.insert(predecessor_id); |
| |
| const auto* dominator_analysis = ir_context->GetDominatorAnalysis( |
| ir_context->cfg()->block(message_.block_id())->GetParent()); |
| |
| // Find the successor of |source_block| that dominates the predecessor of |
| // the merge block |predecessor_id|. |
| auto it = std::find_if( |
| successor_ids.begin(), successor_ids.end(), |
| [predecessor_id, dominator_analysis](uint32_t successor_id) { |
| return dominator_analysis->Dominates(successor_id, predecessor_id); |
| }); |
| |
| // OpPhi requires a single operand pair for every predecessor of the |
| // OpPhi's block. |
| assert(it != successor_ids.end() && "Unable to insert OpPhi"); |
| |
| in_operands.push_back( |
| {SPV_OPERAND_TYPE_ID, {successor_id_to_fresh_id.at(*it)}}); |
| in_operands.push_back({SPV_OPERAND_TYPE_ID, {predecessor_id}}); |
| } |
| |
| ir_context->cfg() |
| ->block(merge_block_id) |
| ->begin() |
| ->InsertBefore(MakeUnique<opt::Instruction>( |
| ir_context, SpvOpPhi, inst_to_propagate->type_id(), |
| message_.phi_fresh_id(), std::move(in_operands))); |
| |
| fuzzerutil::UpdateModuleIdBound(ir_context, message_.phi_fresh_id()); |
| created_inst_ids.push_back(message_.phi_fresh_id()); |
| } |
| |
| // Make sure analyses are updated when we adjust users of |inst_to_propagate|. |
| ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone); |
| |
| // Copy decorations from the original instructions to its propagated copies. |
| for (auto id : created_inst_ids) { |
| ir_context->get_decoration_mgr()->CloneDecorations( |
| inst_to_propagate->result_id(), id); |
| } |
| |
| // Remove all decorations from the original instruction. |
| ir_context->get_decoration_mgr()->RemoveDecorationsFrom( |
| inst_to_propagate->result_id()); |
| |
| // Update every use of the |inst_to_propagate| with a result id of some of the |
| // newly created instructions. |
| ir_context->get_def_use_mgr()->ForEachUse( |
| inst_to_propagate, [ir_context, &created_inst_ids]( |
| opt::Instruction* user, uint32_t operand_index) { |
| assert(ir_context->get_instr_block(user) && |
| "All decorations should have already been adjusted"); |
| |
| auto in_operand_index = |
| fuzzerutil::InOperandIndexFromOperandIndex(*user, operand_index); |
| for (auto id : created_inst_ids) { |
| if (fuzzerutil::IdIsAvailableAtUse(ir_context, user, in_operand_index, |
| id)) { |
| user->SetInOperand(in_operand_index, {id}); |
| return; |
| } |
| } |
| |
| // Every user of |inst_to_propagate| must be updated since we will |
| // remove that instruction from the module. |
| assert(false && "Every user of |inst_to_propagate| must be updated"); |
| }); |
| |
| // Add synonyms about newly created instructions. |
| assert(inst_to_propagate->HasResultId() && |
| "Result id is required to add facts"); |
| if (transformation_context->GetFactManager()->IdIsIrrelevant( |
| inst_to_propagate->result_id())) { |
| for (auto id : created_inst_ids) { |
| transformation_context->GetFactManager()->AddFactIdIsIrrelevant(id); |
| } |
| } else { |
| std::vector<uint32_t> non_irrelevant_ids; |
| for (auto id : created_inst_ids) { |
| // |id| can be irrelevant implicitly (e.g. if we propagate it into a dead |
| // block). |
| if (!transformation_context->GetFactManager()->IdIsIrrelevant(id)) { |
| non_irrelevant_ids.push_back(id); |
| } |
| } |
| |
| if (transformation_context->GetFactManager()->PointeeValueIsIrrelevant( |
| inst_to_propagate->result_id())) { |
| for (auto id : non_irrelevant_ids) { |
| transformation_context->GetFactManager() |
| ->AddFactValueOfPointeeIsIrrelevant(id); |
| } |
| } |
| |
| for (auto id : non_irrelevant_ids) { |
| transformation_context->GetFactManager()->AddFactDataSynonym( |
| MakeDataDescriptor(id, {}), |
| MakeDataDescriptor(non_irrelevant_ids[0], {})); |
| } |
| } |
| |
| // Remove the propagated instruction from the module. |
| ir_context->KillInst(inst_to_propagate); |
| |
| // We've adjusted all users - make sure these changes are analyzed. |
| ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone); |
| } |
| |
| protobufs::Transformation TransformationPropagateInstructionDown::ToMessage() |
| const { |
| protobufs::Transformation result; |
| *result.mutable_propagate_instruction_down() = message_; |
| return result; |
| } |
| |
| bool TransformationPropagateInstructionDown::IsOpcodeSupported(SpvOp opcode) { |
| // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3605): |
| // We only support "simple" instructions that don't work with memory. |
| // We should extend this so that we support the ones that modify the memory |
| // too. |
| switch (opcode) { |
| case SpvOpUndef: |
| case SpvOpAccessChain: |
| case SpvOpInBoundsAccessChain: |
| case SpvOpArrayLength: |
| case SpvOpVectorExtractDynamic: |
| case SpvOpVectorInsertDynamic: |
| case SpvOpVectorShuffle: |
| case SpvOpCompositeConstruct: |
| case SpvOpCompositeExtract: |
| case SpvOpCompositeInsert: |
| case SpvOpCopyObject: |
| case SpvOpTranspose: |
| case SpvOpConvertFToU: |
| case SpvOpConvertFToS: |
| case SpvOpConvertSToF: |
| case SpvOpConvertUToF: |
| case SpvOpUConvert: |
| case SpvOpSConvert: |
| case SpvOpFConvert: |
| case SpvOpQuantizeToF16: |
| case SpvOpSatConvertSToU: |
| case SpvOpSatConvertUToS: |
| case SpvOpBitcast: |
| case SpvOpSNegate: |
| case SpvOpFNegate: |
| case SpvOpIAdd: |
| case SpvOpFAdd: |
| case SpvOpISub: |
| case SpvOpFSub: |
| case SpvOpIMul: |
| case SpvOpFMul: |
| case SpvOpUDiv: |
| case SpvOpSDiv: |
| case SpvOpFDiv: |
| case SpvOpUMod: |
| case SpvOpSRem: |
| case SpvOpSMod: |
| case SpvOpFRem: |
| case SpvOpFMod: |
| case SpvOpVectorTimesScalar: |
| case SpvOpMatrixTimesScalar: |
| case SpvOpVectorTimesMatrix: |
| case SpvOpMatrixTimesVector: |
| case SpvOpMatrixTimesMatrix: |
| case SpvOpOuterProduct: |
| case SpvOpDot: |
| case SpvOpIAddCarry: |
| case SpvOpISubBorrow: |
| case SpvOpUMulExtended: |
| case SpvOpSMulExtended: |
| case SpvOpAny: |
| case SpvOpAll: |
| case SpvOpIsNan: |
| case SpvOpIsInf: |
| case SpvOpIsFinite: |
| case SpvOpIsNormal: |
| case SpvOpSignBitSet: |
| case SpvOpLessOrGreater: |
| case SpvOpOrdered: |
| case SpvOpUnordered: |
| case SpvOpLogicalEqual: |
| case SpvOpLogicalNotEqual: |
| case SpvOpLogicalOr: |
| case SpvOpLogicalAnd: |
| case SpvOpLogicalNot: |
| case SpvOpSelect: |
| case SpvOpIEqual: |
| case SpvOpINotEqual: |
| case SpvOpUGreaterThan: |
| case SpvOpSGreaterThan: |
| case SpvOpUGreaterThanEqual: |
| case SpvOpSGreaterThanEqual: |
| case SpvOpULessThan: |
| case SpvOpSLessThan: |
| case SpvOpULessThanEqual: |
| case SpvOpSLessThanEqual: |
| case SpvOpFOrdEqual: |
| case SpvOpFUnordEqual: |
| case SpvOpFOrdNotEqual: |
| case SpvOpFUnordNotEqual: |
| case SpvOpFOrdLessThan: |
| case SpvOpFUnordLessThan: |
| case SpvOpFOrdGreaterThan: |
| case SpvOpFUnordGreaterThan: |
| case SpvOpFOrdLessThanEqual: |
| case SpvOpFUnordLessThanEqual: |
| case SpvOpFOrdGreaterThanEqual: |
| case SpvOpFUnordGreaterThanEqual: |
| case SpvOpShiftRightLogical: |
| case SpvOpShiftRightArithmetic: |
| case SpvOpShiftLeftLogical: |
| case SpvOpBitwiseOr: |
| case SpvOpBitwiseXor: |
| case SpvOpBitwiseAnd: |
| case SpvOpNot: |
| case SpvOpBitFieldInsert: |
| case SpvOpBitFieldSExtract: |
| case SpvOpBitFieldUExtract: |
| case SpvOpBitReverse: |
| case SpvOpBitCount: |
| case SpvOpCopyLogical: |
| case SpvOpPtrEqual: |
| case SpvOpPtrNotEqual: |
| return true; |
| default: |
| return false; |
| } |
| } |
| |
| opt::Instruction* |
| TransformationPropagateInstructionDown::GetInstructionToPropagate( |
| opt::IRContext* ir_context, uint32_t block_id) { |
| auto* block = ir_context->cfg()->block(block_id); |
| assert(block && "|block_id| is invalid"); |
| |
| for (auto it = block->rbegin(); it != block->rend(); ++it) { |
| if (!it->result_id() || !it->type_id() || |
| !IsOpcodeSupported(it->opcode())) { |
| continue; |
| } |
| |
| auto all_users_from_different_blocks = |
| ir_context->get_def_use_mgr()->WhileEachUser( |
| &*it, [ir_context, block](opt::Instruction* user) { |
| return ir_context->get_instr_block(user) != block; |
| }); |
| |
| if (!all_users_from_different_blocks) { |
| // We can't propagate an instruction if it's used in the same block. |
| continue; |
| } |
| |
| return &*it; |
| } |
| |
| return nullptr; |
| } |
| |
| bool TransformationPropagateInstructionDown::IsApplicableToBlock( |
| opt::IRContext* ir_context, uint32_t block_id) { |
| // Check that |block_id| is valid. |
| const auto* block = fuzzerutil::MaybeFindBlock(ir_context, block_id); |
| if (!block) { |
| return false; |
| } |
| |
| const auto* dominator_analysis = |
| ir_context->GetDominatorAnalysis(block->GetParent()); |
| |
| // |block| must be reachable. |
| if (!dominator_analysis->IsReachable(block)) { |
| return false; |
| } |
| |
| // The block must have an instruction to propagate. |
| const auto* inst_to_propagate = |
| GetInstructionToPropagate(ir_context, block_id); |
| if (!inst_to_propagate) { |
| return false; |
| } |
| |
| // Check that |block| has successors. |
| auto successor_ids = GetAcceptableSuccessors(ir_context, block_id); |
| if (successor_ids.empty()) { |
| return false; |
| } |
| |
| // Check that |successor_block| doesn't have any OpPhi instructions that |
| // use |inst|. |
| for (auto successor_id : successor_ids) { |
| for (const auto& maybe_phi_inst : *ir_context->cfg()->block(successor_id)) { |
| if (maybe_phi_inst.opcode() != SpvOpPhi) { |
| // OpPhis can be intermixed with OpLine and OpNoLine. |
| continue; |
| } |
| |
| for (uint32_t i = 0; i < maybe_phi_inst.NumInOperands(); i += 2) { |
| if (maybe_phi_inst.GetSingleWordInOperand(i) == |
| inst_to_propagate->result_id()) { |
| return false; |
| } |
| } |
| } |
| } |
| |
| // Get the result id of the block we will insert OpPhi instruction into. |
| // This is either 0 or a result id of some merge block in the function. |
| auto phi_block_id = |
| GetOpPhiBlockId(ir_context, block_id, *inst_to_propagate, successor_ids); |
| |
| // Make sure we can adjust all users of the propagated instruction. |
| return ir_context->get_def_use_mgr()->WhileEachUse( |
| inst_to_propagate, |
| [ir_context, &successor_ids, dominator_analysis, phi_block_id]( |
| opt::Instruction* user, uint32_t index) { |
| const auto* user_block = ir_context->get_instr_block(user); |
| |
| if (!user_block) { |
| // |user| might be a global instruction (e.g. OpDecorate). |
| return true; |
| } |
| |
| // Check that at least one of the ids in |successor_ids| or a |
| // |phi_block_id| dominates |user|'s block (or its predecessor if the |
| // user is an OpPhi). We can't use fuzzerutil::IdIsAvailableAtUse since |
| // the id in question hasn't yet been created in the module. |
| auto block_id_to_dominate = user->opcode() == SpvOpPhi |
| ? user->GetSingleWordOperand(index + 1) |
| : user_block->id(); |
| |
| if (phi_block_id != 0 && |
| dominator_analysis->Dominates(phi_block_id, block_id_to_dominate)) { |
| return true; |
| } |
| |
| return std::any_of( |
| successor_ids.begin(), successor_ids.end(), |
| [dominator_analysis, block_id_to_dominate](uint32_t id) { |
| return dominator_analysis->Dominates(id, block_id_to_dominate); |
| }); |
| }); |
| } |
| |
| opt::Instruction* |
| TransformationPropagateInstructionDown::GetFirstInsertBeforeInstruction( |
| opt::IRContext* ir_context, uint32_t block_id, SpvOp opcode) { |
| auto* block = ir_context->cfg()->block(block_id); |
| |
| auto it = block->begin(); |
| |
| while (it != block->end() && |
| !fuzzerutil::CanInsertOpcodeBeforeInstruction(opcode, it)) { |
| ++it; |
| } |
| |
| return it == block->end() ? nullptr : &*it; |
| } |
| |
| std::unordered_set<uint32_t> |
| TransformationPropagateInstructionDown::GetAcceptableSuccessors( |
| opt::IRContext* ir_context, uint32_t block_id) { |
| const auto* block = ir_context->cfg()->block(block_id); |
| assert(block && "|block_id| is invalid"); |
| |
| const auto* inst = GetInstructionToPropagate(ir_context, block_id); |
| assert(inst && "The block must have an instruction to propagate"); |
| |
| std::unordered_set<uint32_t> result; |
| block->ForEachSuccessorLabel([ir_context, &result, |
| inst](uint32_t successor_id) { |
| if (result.count(successor_id)) { |
| return; |
| } |
| |
| auto* successor_block = ir_context->cfg()->block(successor_id); |
| |
| // We can't propagate |inst| into |successor_block| if the latter is not |
| // dominated by the |inst|'s dependencies. |
| if (!inst->WhileEachInId([ir_context, successor_block](const uint32_t* id) { |
| return fuzzerutil::IdIsAvailableBeforeInstruction( |
| ir_context, &*successor_block->begin(), *id); |
| })) { |
| return; |
| } |
| |
| // We don't propagate any "special" instructions (e.g. OpSelectionMerge |
| // etc), thus, insertion point must always exist if the module is valid. |
| assert(GetFirstInsertBeforeInstruction(ir_context, successor_id, |
| inst->opcode()) && |
| "There must exist an insertion point."); |
| |
| result.insert(successor_id); |
| }); |
| |
| return result; |
| } |
| |
| uint32_t TransformationPropagateInstructionDown::GetOpPhiBlockId( |
| opt::IRContext* ir_context, uint32_t block_id, |
| const opt::Instruction& inst_to_propagate, |
| const std::unordered_set<uint32_t>& successor_ids) { |
| const auto* block = ir_context->cfg()->block(block_id); |
| |
| // |block_id| must belong to some construct. |
| auto merge_block_id = |
| block->GetMergeInst() |
| ? block->GetMergeInst()->GetSingleWordInOperand(0) |
| : ir_context->GetStructuredCFGAnalysis()->MergeBlock(block_id); |
| if (!merge_block_id) { |
| return 0; |
| } |
| |
| const auto* dominator_analysis = |
| ir_context->GetDominatorAnalysis(block->GetParent()); |
| |
| // Check that |merge_block_id| is reachable in the CFG and |block_id| |
| // dominates |merge_block_id|. |
| if (!dominator_analysis->IsReachable(merge_block_id) || |
| !dominator_analysis->Dominates(block_id, merge_block_id)) { |
| return 0; |
| } |
| |
| // We can't insert an OpPhi into |merge_block_id| if it's an acceptable |
| // successor of |block_id|. |
| if (successor_ids.count(merge_block_id)) { |
| return 0; |
| } |
| |
| // All predecessors of the merge block must be dominated by at least one |
| // successor of the |block_id|. |
| assert(!ir_context->cfg()->preds(merge_block_id).empty() && |
| "Merge block must be reachable"); |
| for (auto predecessor_id : ir_context->cfg()->preds(merge_block_id)) { |
| if (std::none_of( |
| successor_ids.begin(), successor_ids.end(), |
| [dominator_analysis, predecessor_id](uint32_t successor_id) { |
| return dominator_analysis->Dominates(successor_id, |
| predecessor_id); |
| })) { |
| return 0; |
| } |
| } |
| |
| const auto* propagate_type = |
| ir_context->get_type_mgr()->GetType(inst_to_propagate.type_id()); |
| assert(propagate_type && "|inst_to_propagate| must have a valid type"); |
| |
| // VariablePointers capability implicitly declares |
| // VariablePointersStorageBuffer. We need those capabilities since otherwise |
| // OpPhi instructions cannot have operands of pointer types. |
| if (propagate_type->AsPointer() && |
| !ir_context->get_feature_mgr()->HasCapability( |
| SpvCapabilityVariablePointersStorageBuffer)) { |
| return 0; |
| } |
| |
| return merge_block_id; |
| } |
| |
| std::unordered_set<uint32_t> |
| TransformationPropagateInstructionDown::GetFreshIds() const { |
| std::unordered_set<uint32_t> result = {message_.phi_fresh_id()}; |
| for (const auto& pair : message_.successor_id_to_fresh_id()) { |
| result.insert(pair.second()); |
| } |
| return result; |
| } |
| |
| } // namespace fuzz |
| } // namespace spvtools |
