source/fuzz/transformation_wrap_region_in_selection.cpp

   1 // Copyright (c) 2020 Vasyl Teliman
   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_wrap_region_in_selection.h"
  16
  17 #include "source/fuzz/fuzzer_util.h"
  18
  19 namespace spvtools {
  20 namespace fuzz {
  21
  22 TransformationWrapRegionInSelection::TransformationWrapRegionInSelection(
  23     protobufs::TransformationWrapRegionInSelection message)
  24     : message_(std::move(message)) {}
  25
  26 TransformationWrapRegionInSelection::TransformationWrapRegionInSelection(
  27     uint32_t region_entry_block_id, uint32_t region_exit_block_id,
  28     bool branch_condition) {
  29   message_.set_region_entry_block_id(region_entry_block_id);
  30   message_.set_region_exit_block_id(region_exit_block_id);
  31   message_.set_branch_condition(branch_condition);
  32 }
  33
  34 bool TransformationWrapRegionInSelection::IsApplicable(
  35     opt::IRContext* ir_context,
  36     const TransformationContext& transformation_context) const {
  37   // Check that it is possible to outline a region of blocks without breaking
  38   // domination and structured control flow rules.
  39   if (!IsApplicableToBlockRange(ir_context, message_.region_entry_block_id(),
  40                                 message_.region_exit_block_id())) {
  41     return false;
  42   }
  43
  44   // There must exist an irrelevant boolean constant to be used as a condition
  45   // in the OpBranchConditional instruction.
  46   return fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
  47                                           message_.branch_condition(),
  48                                           true) != 0;
  49 }
  50
  51 void TransformationWrapRegionInSelection::Apply(
  52     opt::IRContext* ir_context,
  53     TransformationContext* transformation_context) const {
  54   auto* new_header_block =
  55       ir_context->cfg()->block(message_.region_entry_block_id());
  56   assert(new_header_block->terminator()->opcode() == spv::Op::OpBranch &&
  57          "This condition should have been checked in the IsApplicable");
  58
  59   const auto successor_id =
  60       new_header_block->terminator()->GetSingleWordInOperand(0);
  61
  62   // Change |entry_block|'s terminator to |OpBranchConditional|.
  63   new_header_block->terminator()->SetOpcode(spv::Op::OpBranchConditional);
  64   new_header_block->terminator()->SetInOperands(
  65       {{SPV_OPERAND_TYPE_ID,
  66         {fuzzerutil::MaybeGetBoolConstant(ir_context, *transformation_context,
  67                                           message_.branch_condition(), true)}},
  68        {SPV_OPERAND_TYPE_ID, {successor_id}},
  69        {SPV_OPERAND_TYPE_ID, {successor_id}}});
  70
  71   // Insert OpSelectionMerge before the terminator.
  72   new_header_block->terminator()->InsertBefore(MakeUnique<opt::Instruction>(
  73       ir_context, spv::Op::OpSelectionMerge, 0, 0,
  74       opt::Instruction::OperandList{
  75           {SPV_OPERAND_TYPE_ID, {message_.region_exit_block_id()}},
  76           {SPV_OPERAND_TYPE_SELECTION_CONTROL,
  77            {uint32_t(spv::SelectionControlMask::MaskNone)}}}));
  78
  79   // We've change the module so we must invalidate analyses.
  80   ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
  81 }
  82
  83 protobufs::Transformation TransformationWrapRegionInSelection::ToMessage()
  84     const {
  85   protobufs::Transformation result;
  86   *result.mutable_wrap_region_in_selection() = message_;
  87   return result;
  88 }
  89
  90 bool TransformationWrapRegionInSelection::IsApplicableToBlockRange(
  91     opt::IRContext* ir_context, uint32_t header_block_candidate_id,
  92     uint32_t merge_block_candidate_id) {
  93   // Check that |header_block_candidate_id| and |merge_block_candidate_id| are
  94   // valid.
  95   const auto* header_block_candidate =
  96       fuzzerutil::MaybeFindBlock(ir_context, header_block_candidate_id);
  97   if (!header_block_candidate) {
  98     return false;
  99   }
 100
 101   const auto* merge_block_candidate =
 102       fuzzerutil::MaybeFindBlock(ir_context, merge_block_candidate_id);
 103   if (!merge_block_candidate) {
 104     return false;
 105   }
 106
 107   // |header_block_candidate| and |merge_block_candidate| must be from the same
 108   // function.
 109   if (header_block_candidate->GetParent() !=
 110       merge_block_candidate->GetParent()) {
 111     return false;
 112   }
 113
 114   const auto* dominator_analysis =
 115       ir_context->GetDominatorAnalysis(header_block_candidate->GetParent());
 116   const auto* postdominator_analysis =
 117       ir_context->GetPostDominatorAnalysis(header_block_candidate->GetParent());
 118
 119   if (!dominator_analysis->StrictlyDominates(header_block_candidate,
 120                                              merge_block_candidate) ||
 121       !postdominator_analysis->StrictlyDominates(merge_block_candidate,
 122                                                  header_block_candidate)) {
 123     return false;
 124   }
 125
 126   // |header_block_candidate| can't be a header since we are about to make it
 127   // one.
 128   if (header_block_candidate->GetMergeInst()) {
 129     return false;
 130   }
 131
 132   // |header_block_candidate| must have an OpBranch terminator.
 133   if (header_block_candidate->terminator()->opcode() != spv::Op::OpBranch) {
 134     return false;
 135   }
 136
 137   // Every header block must have a unique merge block. Thus,
 138   // |merge_block_candidate| can't be a merge block of some other header.
 139   auto* structured_cfg = ir_context->GetStructuredCFGAnalysis();
 140   if (structured_cfg->IsMergeBlock(merge_block_candidate_id)) {
 141     return false;
 142   }
 143
 144   // |header_block_candidate|'s containing construct must also contain
 145   // |merge_block_candidate|.
 146   //
 147   // ContainingConstruct will return the id of a loop header for a block in the
 148   // loop's continue construct. Thus, we must also check the case when one of
 149   // the candidates is in continue construct and the other one is not.
 150   if (structured_cfg->ContainingConstruct(header_block_candidate_id) !=
 151           structured_cfg->ContainingConstruct(merge_block_candidate_id) ||
 152       structured_cfg->IsInContinueConstruct(header_block_candidate_id) !=
 153           structured_cfg->IsInContinueConstruct(merge_block_candidate_id)) {
 154     return false;
 155   }
 156
 157   return true;
 158 }
 159
 160 std::unordered_set<uint32_t> TransformationWrapRegionInSelection::GetFreshIds()
 161     const {
 162   return std::unordered_set<uint32_t>();
 163 }
 164
 165 }  // namespace fuzz
 166 }  // namespace spvtools