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_add_dead_break.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18 #include "source/fuzz/transformation_context.h"
19 #include "source/opt/basic_block.h"
20 #include "source/opt/ir_context.h"
21 #include "source/opt/struct_cfg_analysis.h"
22
23 namespace spvtools {
24 namespace fuzz {
25
TransformationAddDeadBreak(protobufs::TransformationAddDeadBreak message)26 TransformationAddDeadBreak::TransformationAddDeadBreak(
27 protobufs::TransformationAddDeadBreak message)
28 : message_(std::move(message)) {}
29
TransformationAddDeadBreak(uint32_t from_block,uint32_t to_block,bool break_condition_value,std::vector<uint32_t> phi_id)30 TransformationAddDeadBreak::TransformationAddDeadBreak(
31 uint32_t from_block, uint32_t to_block, bool break_condition_value,
32 std::vector<uint32_t> phi_id) {
33 message_.set_from_block(from_block);
34 message_.set_to_block(to_block);
35 message_.set_break_condition_value(break_condition_value);
36 for (auto id : phi_id) {
37 message_.add_phi_id(id);
38 }
39 }
40
AddingBreakRespectsStructuredControlFlow(opt::IRContext * ir_context,opt::BasicBlock * bb_from) const41 bool TransformationAddDeadBreak::AddingBreakRespectsStructuredControlFlow(
42 opt::IRContext* ir_context, opt::BasicBlock* bb_from) const {
43 // Look at the structured control flow associated with |from_block| and
44 // check whether it is contained in an appropriate construct with merge id
45 // |to_block| such that a break from |from_block| to |to_block| is legal.
46
47 // There are three legal cases to consider:
48 // (1) |from_block| is a loop header and |to_block| is its merge
49 // (2) |from_block| is a non-header node of a construct, and |to_block|
50 // is the merge for that construct
51 // (3) |from_block| is a non-header node of a selection construct, and
52 // |to_block| is the merge for the innermost loop containing
53 // |from_block|
54 //
55 // TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/2653) It may be
56 // possible to be more aggressive in breaking from switch constructs.
57 //
58 // The reason we need to distinguish between cases (1) and (2) is that the
59 // structured CFG analysis does not deem a header to be part of the construct
60 // that it heads.
61
62 // Consider case (1)
63 if (bb_from->IsLoopHeader()) {
64 // Case (1) holds if |to_block| is the merge block for the loop;
65 // otherwise no case holds
66 return bb_from->MergeBlockId() == message_.to_block();
67 }
68
69 // Both cases (2) and (3) require that |from_block| is inside some
70 // structured control flow construct.
71
72 auto containing_construct =
73 ir_context->GetStructuredCFGAnalysis()->ContainingConstruct(
74 message_.from_block());
75 if (!containing_construct) {
76 // |from_block| is not in a construct from which we can break.
77 return false;
78 }
79
80 // Consider case (2)
81 if (message_.to_block() ==
82 ir_context->cfg()->block(containing_construct)->MergeBlockId()) {
83 // This looks like an instance of case (2).
84 // However, the structured CFG analysis regards the continue construct of a
85 // loop as part of the loop, but it is not legal to jump from a loop's
86 // continue construct to the loop's merge (except from the back-edge block),
87 // so we need to check for this case.
88 return !fuzzerutil::BlockIsInLoopContinueConstruct(
89 ir_context, message_.from_block(), containing_construct) ||
90 fuzzerutil::BlockIsBackEdge(ir_context, message_.from_block(),
91 containing_construct);
92 }
93
94 // Case (3) holds if and only if |to_block| is the merge block for this
95 // innermost loop that contains |from_block|
96 auto containing_loop_header =
97 ir_context->GetStructuredCFGAnalysis()->ContainingLoop(
98 message_.from_block());
99 if (containing_loop_header &&
100 message_.to_block() ==
101 ir_context->cfg()->block(containing_loop_header)->MergeBlockId()) {
102 return !fuzzerutil::BlockIsInLoopContinueConstruct(
103 ir_context, message_.from_block(), containing_loop_header) ||
104 fuzzerutil::BlockIsBackEdge(ir_context, message_.from_block(),
105 containing_loop_header);
106 }
107 return false;
108 }
109
IsApplicable(opt::IRContext * ir_context,const TransformationContext & transformation_context) const110 bool TransformationAddDeadBreak::IsApplicable(
111 opt::IRContext* ir_context,
112 const TransformationContext& transformation_context) const {
113 // First, we check that a constant with the same value as
114 // |message_.break_condition_value| is present.
115 const auto bool_id =
116 fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
117 message_.break_condition_value(), false);
118 if (!bool_id) {
119 // The required constant is not present, so the transformation cannot be
120 // applied.
121 return false;
122 }
123
124 // Check that |message_.from_block| and |message_.to_block| really are block
125 // ids
126 opt::BasicBlock* bb_from =
127 fuzzerutil::MaybeFindBlock(ir_context, message_.from_block());
128 if (bb_from == nullptr) {
129 return false;
130 }
131 opt::BasicBlock* bb_to =
132 fuzzerutil::MaybeFindBlock(ir_context, message_.to_block());
133 if (bb_to == nullptr) {
134 return false;
135 }
136
137 if (!ir_context->IsReachable(*bb_to)) {
138 // If the target of the break is unreachable, we conservatively do not
139 // allow adding a dead break, to avoid the compilations that arise due to
140 // the lack of sensible dominance information for unreachable blocks.
141 return false;
142 }
143
144 // Check that |message_.from_block| ends with an unconditional branch.
145 if (bb_from->terminator()->opcode() != SpvOpBranch) {
146 // The block associated with the id does not end with an unconditional
147 // branch.
148 return false;
149 }
150
151 assert(bb_from != nullptr &&
152 "We should have found a block if this line of code is reached.");
153 assert(
154 bb_from->id() == message_.from_block() &&
155 "The id of the block we found should match the source id for the break.");
156 assert(bb_to != nullptr &&
157 "We should have found a block if this line of code is reached.");
158 assert(
159 bb_to->id() == message_.to_block() &&
160 "The id of the block we found should match the target id for the break.");
161
162 // Check whether the data passed to extend OpPhi instructions is appropriate.
163 if (!fuzzerutil::PhiIdsOkForNewEdge(ir_context, bb_from, bb_to,
164 message_.phi_id())) {
165 return false;
166 }
167
168 // Check that adding the break would respect the rules of structured
169 // control flow.
170 if (!AddingBreakRespectsStructuredControlFlow(ir_context, bb_from)) {
171 return false;
172 }
173
174 // Adding the dead break is only valid if SPIR-V rules related to dominance
175 // hold.
176 return fuzzerutil::NewTerminatorPreservesDominationRules(
177 ir_context, message_.from_block(),
178 fuzzerutil::CreateUnreachableEdgeInstruction(
179 ir_context, message_.from_block(), message_.to_block(), bool_id));
180 }
181
Apply(opt::IRContext * ir_context,TransformationContext * transformation_context) const182 void TransformationAddDeadBreak::Apply(
183 opt::IRContext* ir_context,
184 TransformationContext* transformation_context) const {
185 fuzzerutil::AddUnreachableEdgeAndUpdateOpPhis(
186 ir_context, ir_context->cfg()->block(message_.from_block()),
187 ir_context->cfg()->block(message_.to_block()),
188 fuzzerutil::MaybeGetBoolConstant(ir_context, *transformation_context,
189 message_.break_condition_value(), false),
190 message_.phi_id());
191
192 // Invalidate all analyses
193 ir_context->InvalidateAnalysesExceptFor(
194 opt::IRContext::Analysis::kAnalysisNone);
195 }
196
ToMessage() const197 protobufs::Transformation TransformationAddDeadBreak::ToMessage() const {
198 protobufs::Transformation result;
199 *result.mutable_add_dead_break() = message_;
200 return result;
201 }
202
GetFreshIds() const203 std::unordered_set<uint32_t> TransformationAddDeadBreak::GetFreshIds() const {
204 return std::unordered_set<uint32_t>();
205 }
206
207 } // namespace fuzz
208 } // namespace spvtools
209