1// Copyright (c) 2020 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/fuzzer_pass_flatten_conditional_branches.h"
16
17#include "source/fuzz/comparator_deep_blocks_first.h"
18#include "source/fuzz/instruction_descriptor.h"
19#include "source/fuzz/transformation_flatten_conditional_branch.h"
20
21namespace spvtools {
22namespace fuzz {
23
24// A fuzzer pass that randomly selects conditional branches to flatten and
25// flattens them, if possible.
26FuzzerPassFlattenConditionalBranches::FuzzerPassFlattenConditionalBranches(
27    opt::IRContext* ir_context, TransformationContext* transformation_context,
28    FuzzerContext* fuzzer_context,
29    protobufs::TransformationSequence* transformations,
30    bool ignore_inapplicable_transformations)
31    : FuzzerPass(ir_context, transformation_context, fuzzer_context,
32                 transformations, ignore_inapplicable_transformations) {}
33
34void FuzzerPassFlattenConditionalBranches::Apply() {
35  for (auto& function : *GetIRContext()->module()) {
36    // Get all the selection headers that we want to flatten. We need to collect
37    // all of them first, because, since we are changing the structure of the
38    // module, it's not safe to modify them while iterating.
39    std::vector<opt::BasicBlock*> selection_headers;
40
41    for (auto& block : function) {
42      // Randomly decide whether to consider this block.
43      if (!GetFuzzerContext()->ChoosePercentage(
44              GetFuzzerContext()->GetChanceOfFlatteningConditionalBranch())) {
45        continue;
46      }
47
48      // Only consider this block if it is the header of a conditional, with a
49      // non-irrelevant condition.
50      if (block.GetMergeInst() &&
51          block.GetMergeInst()->opcode() == spv::Op::OpSelectionMerge &&
52          block.terminator()->opcode() == spv::Op::OpBranchConditional &&
53          !GetTransformationContext()->GetFactManager()->IdIsIrrelevant(
54              block.terminator()->GetSingleWordInOperand(0))) {
55        selection_headers.emplace_back(&block);
56      }
57    }
58
59    // Sort the headers so that those that are more deeply nested are considered
60    // first, possibly enabling outer conditionals to be flattened.
61    std::sort(selection_headers.begin(), selection_headers.end(),
62              ComparatorDeepBlocksFirst(GetIRContext()));
63
64    // Apply the transformation to the headers which can be flattened.
65    for (auto header : selection_headers) {
66      // Make a set to keep track of the instructions that need fresh ids.
67      std::set<opt::Instruction*> instructions_that_need_ids;
68
69      // Do not consider this header if the conditional cannot be flattened.
70      if (!TransformationFlattenConditionalBranch::
71              GetProblematicInstructionsIfConditionalCanBeFlattened(
72                  GetIRContext(), header, *GetTransformationContext(),
73                  &instructions_that_need_ids)) {
74        continue;
75      }
76
77      uint32_t convergence_block_id =
78          TransformationFlattenConditionalBranch::FindConvergenceBlock(
79              GetIRContext(), *header);
80
81      // If the SPIR-V version is restricted so that OpSelect can only work on
82      // scalar, pointer and vector types then we cannot apply this
83      // transformation to a header whose convergence block features OpPhi
84      // instructions on different types, as we cannot convert such instructions
85      // to OpSelect instructions.
86      if (TransformationFlattenConditionalBranch::
87              OpSelectArgumentsAreRestricted(GetIRContext())) {
88        if (!GetIRContext()
89                 ->cfg()
90                 ->block(convergence_block_id)
91                 ->WhileEachPhiInst(
92                     [this](opt::Instruction* phi_instruction) -> bool {
93                       switch (GetIRContext()
94                                   ->get_def_use_mgr()
95                                   ->GetDef(phi_instruction->type_id())
96                                   ->opcode()) {
97                         case spv::Op::OpTypeBool:
98                         case spv::Op::OpTypeInt:
99                         case spv::Op::OpTypeFloat:
100                         case spv::Op::OpTypePointer:
101                         case spv::Op::OpTypeVector:
102                           return true;
103                         default:
104                           return false;
105                       }
106                     })) {
107          // An OpPhi is performed on a type not supported by OpSelect; we
108          // cannot flatten this selection.
109          continue;
110        }
111      }
112
113      // If the construct's convergence block features OpPhi instructions with
114      // vector result types then we may be *forced*, by the SPIR-V version, to
115      // turn these into component-wise OpSelect instructions, or we might wish
116      // to do so anyway.  The following booleans capture whether we will opt
117      // to use a component-wise select even if we don't have to.
118      bool use_component_wise_2d_select_even_if_optional =
119          GetFuzzerContext()->ChooseEven();
120      bool use_component_wise_3d_select_even_if_optional =
121          GetFuzzerContext()->ChooseEven();
122      bool use_component_wise_4d_select_even_if_optional =
123          GetFuzzerContext()->ChooseEven();
124
125      // If we do need to perform any component-wise selections, we will need a
126      // fresh id for a boolean vector representing the selection's condition
127      // repeated N times, where N is the vector dimension.
128      uint32_t fresh_id_for_bvec2_selector = 0;
129      uint32_t fresh_id_for_bvec3_selector = 0;
130      uint32_t fresh_id_for_bvec4_selector = 0;
131
132      GetIRContext()
133          ->cfg()
134          ->block(convergence_block_id)
135          ->ForEachPhiInst([this, &fresh_id_for_bvec2_selector,
136                            &fresh_id_for_bvec3_selector,
137                            &fresh_id_for_bvec4_selector,
138                            use_component_wise_2d_select_even_if_optional,
139                            use_component_wise_3d_select_even_if_optional,
140                            use_component_wise_4d_select_even_if_optional](
141                               opt::Instruction* phi_instruction) {
142            opt::Instruction* type_instruction =
143                GetIRContext()->get_def_use_mgr()->GetDef(
144                    phi_instruction->type_id());
145            switch (type_instruction->opcode()) {
146              case spv::Op::OpTypeVector: {
147                uint32_t dimension =
148                    type_instruction->GetSingleWordInOperand(1);
149                switch (dimension) {
150                  case 2:
151                    PrepareForOpPhiOnVectors(
152                        dimension,
153                        use_component_wise_2d_select_even_if_optional,
154                        &fresh_id_for_bvec2_selector);
155                    break;
156                  case 3:
157                    PrepareForOpPhiOnVectors(
158                        dimension,
159                        use_component_wise_3d_select_even_if_optional,
160                        &fresh_id_for_bvec3_selector);
161                    break;
162                  case 4:
163                    PrepareForOpPhiOnVectors(
164                        dimension,
165                        use_component_wise_4d_select_even_if_optional,
166                        &fresh_id_for_bvec4_selector);
167                    break;
168                  default:
169                    assert(false && "Invalid vector dimension.");
170                }
171                break;
172              }
173              default:
174                break;
175            }
176          });
177
178      // Some instructions will require to be enclosed inside conditionals
179      // because they have side effects (for example, loads and stores). Some of
180      // this have no result id, so we require instruction descriptors to
181      // identify them. Each of them is associated with the necessary ids for it
182      // via a SideEffectWrapperInfo message.
183      std::vector<protobufs::SideEffectWrapperInfo> wrappers_info;
184
185      for (auto instruction : instructions_that_need_ids) {
186        protobufs::SideEffectWrapperInfo wrapper_info;
187        *wrapper_info.mutable_instruction() =
188            MakeInstructionDescriptor(GetIRContext(), instruction);
189        wrapper_info.set_merge_block_id(GetFuzzerContext()->GetFreshId());
190        wrapper_info.set_execute_block_id(GetFuzzerContext()->GetFreshId());
191
192        // If the instruction has a non-void result id, we need to define more
193        // fresh ids and provide an id of the suitable type whose value can be
194        // copied in order to create a placeholder id.
195        if (TransformationFlattenConditionalBranch::InstructionNeedsPlaceholder(
196                GetIRContext(), *instruction)) {
197          wrapper_info.set_actual_result_id(GetFuzzerContext()->GetFreshId());
198          wrapper_info.set_alternative_block_id(
199              GetFuzzerContext()->GetFreshId());
200          wrapper_info.set_placeholder_result_id(
201              GetFuzzerContext()->GetFreshId());
202
203          // The id will be a zero constant if the type allows it, and an
204          // OpUndef otherwise. We want to avoid using OpUndef, if possible, to
205          // avoid undefined behaviour in the module as much as possible.
206          if (fuzzerutil::CanCreateConstant(GetIRContext(),
207                                            instruction->type_id())) {
208            wrapper_info.set_value_to_copy_id(
209                FindOrCreateZeroConstant(instruction->type_id(), true));
210          } else {
211            wrapper_info.set_value_to_copy_id(
212                FindOrCreateGlobalUndef(instruction->type_id()));
213          }
214        }
215
216        wrappers_info.push_back(std::move(wrapper_info));
217      }
218
219      // Apply the transformation, evenly choosing whether to lay out the true
220      // branch or the false branch first.
221      ApplyTransformation(TransformationFlattenConditionalBranch(
222          header->id(), GetFuzzerContext()->ChooseEven(),
223          fresh_id_for_bvec2_selector, fresh_id_for_bvec3_selector,
224          fresh_id_for_bvec4_selector, wrappers_info));
225    }
226  }
227}
228
229void FuzzerPassFlattenConditionalBranches::PrepareForOpPhiOnVectors(
230    uint32_t vector_dimension, bool use_vector_select_if_optional,
231    uint32_t* fresh_id_for_bvec_selector) {
232  if (*fresh_id_for_bvec_selector != 0) {
233    // We already have a fresh id for a component-wise OpSelect of this
234    // dimension
235    return;
236  }
237  if (TransformationFlattenConditionalBranch::OpSelectArgumentsAreRestricted(
238          GetIRContext()) ||
239      use_vector_select_if_optional) {
240    // We either have to, or have chosen to, perform a component-wise select, so
241    // we ensure that the right boolean vector type is available, and grab a
242    // fresh id.
243    FindOrCreateVectorType(FindOrCreateBoolType(), vector_dimension);
244    *fresh_id_for_bvec_selector = GetFuzzerContext()->GetFreshId();
245  }
246}
247
248}  // namespace fuzz
249}  // namespace spvtools
250