Debian Codegraph @

third_party/spirv-tools/source/fuzz/transformation_add_dead_continue.cpp

raw
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_continue.h"
16
17 #include "source/fuzz/fuzzer_util.h"
18
19 namespace spvtools {
20 namespace fuzz {
21
22 TransformationAddDeadContinue::TransformationAddDeadContinue(
23 const spvtools::fuzz::protobufs::TransformationAddDeadContinue& message)
24 : message_(message) {}
25
26 TransformationAddDeadContinue::TransformationAddDeadContinue(
27 uint32_t from_block, bool continue_condition_value,
28 std::vector<uint32_t> phi_id) {
29 message_.set_from_block(from_block);
30 message_.set_continue_condition_value(continue_condition_value);
31 for (auto id : phi_id) {
32 message_.add_phi_id(id);
33 }
34 }
35
36 bool TransformationAddDeadContinue::IsApplicable(
37 opt::IRContext* ir_context,
38 const TransformationContext& transformation_context) const {
39 // First, we check that a constant with the same value as
40 // |message_.continue_condition_value| is present.
41 if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
42 message_.continue_condition_value(),
43 false)) {
44 // The required constant is not present, so the transformation cannot be
45 // applied.
46 return false;
47 }
48
49 // Check that |message_.from_block| really is a block id.
50 opt::BasicBlock* bb_from =
51 fuzzerutil::MaybeFindBlock(ir_context, message_.from_block());
52 if (bb_from == nullptr) {
53 return false;
54 }
55
56 // Check that |message_.from_block| ends with an unconditional branch.
57 if (bb_from->terminator()->opcode() != SpvOpBranch) {
58 // The block associated with the id does not end with an unconditional
59 // branch.
60 return false;
61 }
62
63 assert(bb_from != nullptr &&
64 "We should have found a block if this line of code is reached.");
65 assert(
66 bb_from->id() == message_.from_block() &&
67 "The id of the block we found should match the source id for the break.");
68
69 // Get the header for the innermost loop containing |message_.from_block|.
70 // Because the structured CFG analysis does not regard a loop header as part
71 // of the loop it heads, we check first whether bb_from is a loop header
72 // before using the structured CFG analysis.
73 auto loop_header =
74 bb_from->IsLoopHeader()
75 ? message_.from_block()
76 : ir_context->GetStructuredCFGAnalysis()->ContainingLoop(
77 message_.from_block());
78 if (!loop_header) {
79 return false;
80 }
81
82 auto continue_block =
83 ir_context->cfg()->block(loop_header)->ContinueBlockId();
84
85 if (!fuzzerutil::BlockIsReachableInItsFunction(
86 ir_context, ir_context->cfg()->block(continue_block))) {
87 // If the loop's continue block is unreachable, we conservatively do not
88 // allow adding a dead continue, to avoid the compilations that arise due to
89 // the lack of sensible dominance information for unreachable blocks.
90 return false;
91 }
92
93 if (fuzzerutil::BlockIsInLoopContinueConstruct(
94 ir_context, message_.from_block(), loop_header)) {
95 // We cannot jump to the continue target from the continue construct.
96 return false;
97 }
98
99 if (ir_context->GetStructuredCFGAnalysis()->IsMergeBlock(continue_block)) {
100 // A branch straight to the continue target that is also a merge block might
101 // break the property that a construct header must dominate its merge block
102 // (if the merge block is reachable).
103 return false;
104 }
105
106 // Check whether the data passed to extend OpPhi instructions is appropriate.
107 if (!fuzzerutil::PhiIdsOkForNewEdge(ir_context, bb_from,
108 ir_context->cfg()->block(continue_block),
109 message_.phi_id())) {
110 return false;
111 }
112
113 // Adding the dead break is only valid if SPIR-V rules related to dominance
114 // hold. Rather than checking these rules explicitly, we defer to the
115 // validator. We make a clone of the module, apply the transformation to the
116 // clone, and check whether the transformed clone is valid.
117 //
118 // In principle some of the above checks could be removed, with more reliance
119 // being placed on the validator. This should be revisited if we are sure
120 // the validator is complete with respect to checking structured control flow
121 // rules.
122 auto cloned_context = fuzzerutil::CloneIRContext(ir_context);
123 ApplyImpl(cloned_context.get(), transformation_context);
124 return fuzzerutil::IsValid(cloned_context.get(),
125 transformation_context.GetValidatorOptions(),
126 fuzzerutil::kSilentMessageConsumer);
127 }
128
129 void TransformationAddDeadContinue::Apply(
130 opt::IRContext* ir_context,
131 TransformationContext* transformation_context) const {
132 ApplyImpl(ir_context, *transformation_context);
133 // Invalidate all analyses
134 ir_context->InvalidateAnalysesExceptFor(
135 opt::IRContext::Analysis::kAnalysisNone);
136 }
137
138 protobufs::Transformation TransformationAddDeadContinue::ToMessage() const {
139 protobufs::Transformation result;
140 *result.mutable_add_dead_continue() = message_;
141 return result;
142 }
143
144 void TransformationAddDeadContinue::ApplyImpl(
145 spvtools::opt::IRContext* ir_context,
146 const TransformationContext& transformation_context) const {
147 auto bb_from = ir_context->cfg()->block(message_.from_block());
148 auto continue_block =
149 bb_from->IsLoopHeader()
150 ? bb_from->ContinueBlockId()
151 : ir_context->GetStructuredCFGAnalysis()->LoopContinueBlock(
152 message_.from_block());
153 assert(continue_block && "message_.from_block must be in a loop.");
154 fuzzerutil::AddUnreachableEdgeAndUpdateOpPhis(
155 ir_context, bb_from, ir_context->cfg()->block(continue_block),
156 fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
157 message_.continue_condition_value(),
158 false),
159 message_.phi_id());
160 }
161
162 std::unordered_set<uint32_t> TransformationAddDeadContinue::GetFreshIds()
163 const {
164 return std::unordered_set<uint32_t>();
165 }
166
167 } // namespace fuzz
168 } // namespace spvtools