source/fuzz/transformation_move_block_down.cpp

   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
  22 TransformationMoveBlockDown::TransformationMoveBlockDown(
  23     protobufs::TransformationMoveBlockDown message)
  24     : message_(std::move(message)) {}
  25
  26 TransformationMoveBlockDown::TransformationMoveBlockDown(uint32_t id) {
  27   message_.set_block_id(id);
  28 }
  29
  30 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
  74 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
 102 protobufs::Transformation TransformationMoveBlockDown::ToMessage() const {
 103   protobufs::Transformation result;
 104   *result.mutable_move_block_down() = message_;
 105   return result;
 106 }
 107
 108 std::unordered_set<uint32_t> TransformationMoveBlockDown::GetFreshIds() const {
 109   return std::unordered_set<uint32_t>();
 110 }
 111
 112 }  // namespace fuzz
 113 }  // namespace spvtools