| 1 |
// Copyright (c) 2019 Google LLC |
| 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_split_block.h" |
| 16 |
|
| 17 |
#include <utility> |
| 18 |
|
| 19 |
#include "source/fuzz/fuzzer_util.h" |
| 20 |
#include "source/fuzz/instruction_descriptor.h" |
| 21 |
#include "source/util/make_unique.h" |
| 22 |
|
| 23 |
namespace spvtools { |
| 24 |
namespace fuzz { |
| 25 |
|
| 26 |
TransformationSplitBlock::TransformationSplitBlock( |
| 27 |
const spvtools::fuzz::protobufs::TransformationSplitBlock& message) |
| 28 |
: message_(message) {} |
| 29 |
|
| 30 |
TransformationSplitBlock::TransformationSplitBlock( |
| 31 |
const protobufs::InstructionDescriptor& instruction_to_split_before, |
| 32 |
uint32_t fresh_id) { |
| 33 |
*message_.mutable_instruction_to_split_before() = instruction_to_split_before; |
| 34 |
message_.set_fresh_id(fresh_id); |
| 35 |
} |
| 36 |
|
| 37 |
bool TransformationSplitBlock::IsApplicable( |
| 38 |
opt::IRContext* ir_context, const TransformationContext& /*unused*/) const { |
| 39 |
if (!fuzzerutil::IsFreshId(ir_context, message_.fresh_id())) { |
| 40 |
// We require the id for the new block to be unused. |
| 41 |
return false; |
| 42 |
} |
| 43 |
auto instruction_to_split_before = |
| 44 |
FindInstruction(message_.instruction_to_split_before(), ir_context); |
| 45 |
if (!instruction_to_split_before) { |
| 46 |
// The instruction describing the block we should split does not exist. |
| 47 |
return false; |
| 48 |
} |
| 49 |
auto block_to_split = |
| 50 |
ir_context->get_instr_block(instruction_to_split_before); |
| 51 |
assert(block_to_split && |
| 52 |
"We should not have managed to find the " |
| 53 |
"instruction if it was not contained in a block."); |
| 54 |
|
| 55 |
if (block_to_split->IsLoopHeader()) { |
| 56 |
// We cannot split a loop header block: back-edges would become invalid. |
| 57 |
return false; |
| 58 |
} |
| 59 |
|
| 60 |
auto split_before = fuzzerutil::GetIteratorForInstruction( |
| 61 |
block_to_split, instruction_to_split_before); |
| 62 |
assert(split_before != block_to_split->end() && |
| 63 |
"At this point we know the" |
| 64 |
" block split point exists."); |
| 65 |
|
| 66 |
if (split_before->PreviousNode() && |
| 67 |
split_before->PreviousNode()->opcode() == SpvOpSelectionMerge) { |
| 68 |
// We cannot split directly after a selection merge: this would separate |
| 69 |
// the merge from its associated branch or switch operation. |
| 70 |
return false; |
| 71 |
} |
| 72 |
if (split_before->opcode() == SpvOpVariable) { |
| 73 |
// We cannot split directly after a variable; variables in a function |
| 74 |
// must be contiguous in the entry block. |
| 75 |
return false; |
| 76 |
} |
| 77 |
// We cannot split before an OpPhi unless the OpPhi has exactly one |
| 78 |
// associated incoming edge. |
| 79 |
if (split_before->opcode() == SpvOpPhi && |
| 80 |
split_before->NumInOperands() != 2) { |
| 81 |
return false; |
| 82 |
} |
| 83 |
|
| 84 |
// Splitting the block must not separate the definition of an OpSampledImage |
| 85 |
// from its use: the SPIR-V data rules require them to be in the same block. |
| 86 |
return !fuzzerutil:: |
| 87 |
SplittingBeforeInstructionSeparatesOpSampledImageDefinitionFromUse( |
| 88 |
block_to_split, instruction_to_split_before); |
| 89 |
} |
| 90 |
|
| 91 |
void TransformationSplitBlock::Apply( |
| 92 |
opt::IRContext* ir_context, |
| 93 |
TransformationContext* transformation_context) const { |
| 94 |
opt::Instruction* instruction_to_split_before = |
| 95 |
FindInstruction(message_.instruction_to_split_before(), ir_context); |
| 96 |
opt::BasicBlock* block_to_split = |
| 97 |
ir_context->get_instr_block(instruction_to_split_before); |
| 98 |
auto split_before = fuzzerutil::GetIteratorForInstruction( |
| 99 |
block_to_split, instruction_to_split_before); |
| 100 |
assert(split_before != block_to_split->end() && |
| 101 |
"If the transformation is applicable, we should have an " |
| 102 |
"instruction to split on."); |
| 103 |
|
| 104 |
// We need to make sure the module's id bound is large enough to add the |
| 105 |
// fresh id. |
| 106 |
fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id()); |
| 107 |
// Split the block. |
| 108 |
auto new_bb = block_to_split->SplitBasicBlock(ir_context, message_.fresh_id(), |
| 109 |
split_before); |
| 110 |
// The split does not automatically add a branch between the two parts of |
| 111 |
// the original block, so we add one. |
| 112 |
block_to_split->AddInstruction(MakeUnique<opt::Instruction>( |
| 113 |
ir_context, SpvOpBranch, 0, 0, |
| 114 |
std::initializer_list<opt::Operand>{opt::Operand( |
| 115 |
spv_operand_type_t::SPV_OPERAND_TYPE_ID, {message_.fresh_id()})})); |
| 116 |
// If we split before OpPhi instructions, we need to update their |
| 117 |
// predecessor operand so that the block they used to be inside is now the |
| 118 |
// predecessor. |
| 119 |
new_bb->ForEachPhiInst([block_to_split](opt::Instruction* phi_inst) { |
| 120 |
assert( |
| 121 |
phi_inst->NumInOperands() == 2 && |
| 122 |
"Precondition: a block can only be split before an OpPhi if the block" |
| 123 |
"has exactly one predecessor."); |
| 124 |
phi_inst->SetInOperand(1, {block_to_split->id()}); |
| 125 |
}); |
| 126 |
|
| 127 |
// Invalidate all analyses |
| 128 |
ir_context->InvalidateAnalysesExceptFor( |
| 129 |
opt::IRContext::Analysis::kAnalysisNone); |
| 130 |
|
| 131 |
// If the block being split was dead, the new block arising from the split is |
| 132 |
// also dead. |
| 133 |
if (transformation_context->GetFactManager()->BlockIsDead( |
| 134 |
block_to_split->id())) { |
| 135 |
transformation_context->GetFactManager()->AddFactBlockIsDead( |
| 136 |
message_.fresh_id()); |
| 137 |
} |
| 138 |
} |
| 139 |
|
| 140 |
protobufs::Transformation TransformationSplitBlock::ToMessage() const { |
| 141 |
protobufs::Transformation result; |
| 142 |
*result.mutable_split_block() = message_; |
| 143 |
return result; |
| 144 |
} |
| 145 |
|
| 146 |
std::unordered_set<uint32_t> TransformationSplitBlock::GetFreshIds() const { |
| 147 |
return {message_.fresh_id()}; |
| 148 |
} |
| 149 |
|
| 150 |
} // namespace fuzz |
| 151 |
} // namespace spvtools |