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
TransformationSplitBlock(const spvtools::fuzz::protobufs::TransformationSplitBlock & message)26 TransformationSplitBlock::TransformationSplitBlock(
27 const spvtools::fuzz::protobufs::TransformationSplitBlock& message)
28 : message_(message) {}
29
TransformationSplitBlock(const protobufs::InstructionDescriptor & instruction_to_split_before,uint32_t fresh_id)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
IsApplicable(opt::IRContext * context,const FactManager &) const37 bool TransformationSplitBlock::IsApplicable(
38 opt::IRContext* context, const FactManager& /*unused*/) const {
39 if (!fuzzerutil::IsFreshId(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(), 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 = context->get_instr_block(instruction_to_split_before);
50 assert(block_to_split &&
51 "We should not have managed to find the "
52 "instruction if it was not contained in a block.");
53
54 if (block_to_split->IsLoopHeader()) {
55 // We cannot split a loop header block: back-edges would become invalid.
56 return false;
57 }
58
59 auto split_before = fuzzerutil::GetIteratorForInstruction(
60 block_to_split, instruction_to_split_before);
61 assert(split_before != block_to_split->end() &&
62 "At this point we know the"
63 " block split point exists.");
64
65 if (split_before->PreviousNode() &&
66 split_before->PreviousNode()->opcode() == SpvOpSelectionMerge) {
67 // We cannot split directly after a selection merge: this would separate
68 // the merge from its associated branch or switch operation.
69 return false;
70 }
71 if (split_before->opcode() == SpvOpVariable) {
72 // We cannot split directly after a variable; variables in a function
73 // must be contiguous in the entry block.
74 return false;
75 }
76 // We cannot split before an OpPhi unless the OpPhi has exactly one
77 // associated incoming edge.
78 return !(split_before->opcode() == SpvOpPhi &&
79 split_before->NumInOperands() != 2);
80 }
81
Apply(opt::IRContext * context,FactManager * fact_manager) const82 void TransformationSplitBlock::Apply(opt::IRContext* context,
83 FactManager* fact_manager) const {
84 opt::Instruction* instruction_to_split_before =
85 FindInstruction(message_.instruction_to_split_before(), context);
86 opt::BasicBlock* block_to_split =
87 context->get_instr_block(instruction_to_split_before);
88 auto split_before = fuzzerutil::GetIteratorForInstruction(
89 block_to_split, instruction_to_split_before);
90 assert(split_before != block_to_split->end() &&
91 "If the transformation is applicable, we should have an "
92 "instruction to split on.");
93
94 // We need to make sure the module's id bound is large enough to add the
95 // fresh id.
96 fuzzerutil::UpdateModuleIdBound(context, message_.fresh_id());
97 // Split the block.
98 auto new_bb = block_to_split->SplitBasicBlock(context, message_.fresh_id(),
99 split_before);
100 // The split does not automatically add a branch between the two parts of
101 // the original block, so we add one.
102 block_to_split->AddInstruction(MakeUnique<opt::Instruction>(
103 context, SpvOpBranch, 0, 0,
104 std::initializer_list<opt::Operand>{opt::Operand(
105 spv_operand_type_t::SPV_OPERAND_TYPE_ID, {message_.fresh_id()})}));
106 // If we split before OpPhi instructions, we need to update their
107 // predecessor operand so that the block they used to be inside is now the
108 // predecessor.
109 new_bb->ForEachPhiInst([block_to_split](opt::Instruction* phi_inst) {
110 // The following assertion is a sanity check. It is guaranteed to hold
111 // if IsApplicable holds.
112 assert(phi_inst->NumInOperands() == 2 &&
113 "We can only split a block before an OpPhi if block has exactly "
114 "one predecessor.");
115 phi_inst->SetInOperand(1, {block_to_split->id()});
116 });
117
118 // If the block being split was dead, the new block arising from the split is
119 // also dead.
120 if (fact_manager->BlockIsDead(block_to_split->id())) {
121 fact_manager->AddFactBlockIsDead(message_.fresh_id());
122 }
123
124 // Invalidate all analyses
125 context->InvalidateAnalysesExceptFor(opt::IRContext::Analysis::kAnalysisNone);
126 }
127
ToMessage() const128 protobufs::Transformation TransformationSplitBlock::ToMessage() const {
129 protobufs::Transformation result;
130 *result.mutable_split_block() = message_;
131 return result;
132 }
133
134 } // namespace fuzz
135 } // namespace spvtools
136