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_move_block_down.h"
16
17 #include "source/opt/basic_block.h"
18
19 namespace spvtools {
20 namespace fuzz {
21
TransformationMoveBlockDown(const spvtools::fuzz::protobufs::TransformationMoveBlockDown & message)22 TransformationMoveBlockDown::TransformationMoveBlockDown(
23 const spvtools::fuzz::protobufs::TransformationMoveBlockDown& message)
24 : message_(message) {}
25
TransformationMoveBlockDown(uint32_t id)26 TransformationMoveBlockDown::TransformationMoveBlockDown(uint32_t id) {
27 message_.set_block_id(id);
28 }
29
IsApplicable(opt::IRContext * ir_context,const TransformationContext &) const30 bool TransformationMoveBlockDown::IsApplicable(
31 opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
32 // Go through every block in every function, looking for a block whose id
33 // matches that of the block we want to consider moving down.
34 for (auto& function : *ir_context->module()) {
35 for (auto block_it = function.begin(); block_it != function.end();
36 ++block_it) {
37 if (block_it->id() == message_.block_id()) {
38 // We have found a match.
39 if (block_it == function.begin()) {
40 // The block is the first one appearing in the function. We are not
41 // allowed to move this block down.
42 return false;
43 }
44 // Record the block we would like to consider moving down.
45 opt::BasicBlock* block_matching_id = &*block_it;
46 if (!ir_context->GetDominatorAnalysis(&function)->IsReachable(
47 block_matching_id)) {
48 // The block is not reachable. We are not allowed to move it down.
49 return false;
50 }
51 // Now see whether there is some block following that block in program
52 // order.
53 ++block_it;
54 if (block_it == function.end()) {
55 // There is no such block; i.e., the block we are considering moving
56 // is the last one in the function. The transformation thus does not
57 // apply.
58 return false;
59 }
60 opt::BasicBlock* next_block_in_program_order = &*block_it;
61 // We can move the block of interest down if and only if it does not
62 // dominate the block that comes next.
63 return !ir_context->GetDominatorAnalysis(&function)->Dominates(
64 block_matching_id, next_block_in_program_order);
65 }
66 }
67 }
68
69 // We did not find a matching block, so the transformation is not applicable:
70 // there is no relevant block to move.
71 return false;
72 }
73
Apply(opt::IRContext * ir_context,TransformationContext *) const74 void TransformationMoveBlockDown::Apply(
75 opt::IRContext* ir_context, TransformationContext* /*unused*/) const {
76 // Go through every block in every function, looking for a block whose id
77 // matches that of the block we want to move down.
78 for (auto& function : *ir_context->module()) {
79 for (auto block_it = function.begin(); block_it != function.end();
80 ++block_it) {
81 if (block_it->id() == message_.block_id()) {
82 ++block_it;
83 assert(block_it != function.end() &&
84 "To be able to move a block down, it needs to have a "
85 "program-order successor.");
86 function.MoveBasicBlockToAfter(message_.block_id(), &*block_it);
87 // For performance, it is vital to keep the dominator analysis valid
88 // (which due to https://github.com/KhronosGroup/SPIRV-Tools/issues/2889
89 // requires keeping the CFG analysis valid).
90 ir_context->InvalidateAnalysesExceptFor(
91 opt::IRContext::Analysis::kAnalysisDefUse |
92 opt::IRContext::Analysis::kAnalysisCFG |
93 opt::IRContext::Analysis::kAnalysisDominatorAnalysis);
94
95 return;
96 }
97 }
98 }
99 assert(false && "No block was found to move down.");
100 }
101
ToMessage() const102 protobufs::Transformation TransformationMoveBlockDown::ToMessage() const {
103 protobufs::Transformation result;
104 *result.mutable_move_block_down() = message_;
105 return result;
106 }
107
GetFreshIds() const108 std::unordered_set<uint32_t> TransformationMoveBlockDown::GetFreshIds() const {
109 return std::unordered_set<uint32_t>();
110 }
111
112 } // namespace fuzz
113 } // namespace spvtools
114