source/fuzz/transformation_add_dead_block.cpp

// Copyright (c) 2019 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "source/fuzz/transformation_add_dead_block.h"

#include "source/fuzz/fuzzer_util.h"

namespace spvtools {
namespace fuzz {

TransformationAddDeadBlock::TransformationAddDeadBlock(
    const spvtools::fuzz::protobufs::TransformationAddDeadBlock& message)
    : message_(message) {}

TransformationAddDeadBlock::TransformationAddDeadBlock(uint32_t fresh_id,
                                                       uint32_t existing_block,
                                                       bool condition_value) {
  message_.set_fresh_id(fresh_id);
  message_.set_existing_block(existing_block);
  message_.set_condition_value(condition_value);
}

bool TransformationAddDeadBlock::IsApplicable(
    opt::IRContext* context,
    const spvtools::fuzz::FactManager& /*unused*/) const {
  // The new block's id must be fresh.
  if (!fuzzerutil::IsFreshId(context, message_.fresh_id())) {
    return false;
  }

  // First, we check that a constant with the same value as
  // |message_.condition_value| is present.
  if (!fuzzerutil::MaybeGetBoolConstantId(context,
                                          message_.condition_value())) {
    // The required constant is not present, so the transformation cannot be
    // applied.
    return false;
  }

  // The existing block must indeed exist.
  auto existing_block =
      fuzzerutil::MaybeFindBlock(context, message_.existing_block());
  if (!existing_block) {
    return false;
  }

  // It must not head a loop.
  if (existing_block->IsLoopHeader()) {
    return false;
  }

  // It must end with OpBranch.
  if (existing_block->terminator()->opcode() != SpvOpBranch) {
    return false;
  }

  // Its successor must not be a merge block nor continue target.
  auto successor_block_id =
      existing_block->terminator()->GetSingleWordInOperand(0);
  if (fuzzerutil::IsMergeOrContinue(context, successor_block_id)) {
    return false;
  }

  // The successor must not be a loop header (i.e., |message_.existing_block|
  // must not be a back-edge block.
  if (context->cfg()->block(successor_block_id)->IsLoopHeader()) {
    return false;
  }

  return true;
}

void TransformationAddDeadBlock::Apply(
    opt::IRContext* context, spvtools::fuzz::FactManager* fact_manager) const {
  // Update the module id bound so that it is at least the id of the new block.
  fuzzerutil::UpdateModuleIdBound(context, message_.fresh_id());

  // Get the existing block and its successor.
  auto existing_block = context->cfg()->block(message_.existing_block());
  auto successor_block_id =
      existing_block->terminator()->GetSingleWordInOperand(0);

  // Get the id of the boolean value that will be used as the branch condition.
  auto bool_id =
      fuzzerutil::MaybeGetBoolConstantId(context, message_.condition_value());

  // Make a new block that unconditionally branches to the original successor
  // block.
  auto enclosing_function = existing_block->GetParent();
  std::unique_ptr<opt::BasicBlock> new_block = MakeUnique<opt::BasicBlock>(
      MakeUnique<opt::Instruction>(context, SpvOpLabel, 0, message_.fresh_id(),
                                   opt::Instruction::OperandList()));
  new_block->AddInstruction(MakeUnique<opt::Instruction>(
      context, SpvOpBranch, 0, 0,
      opt::Instruction::OperandList(
          {{SPV_OPERAND_TYPE_ID, {successor_block_id}}})));

  // Turn the original block into a selection merge, with its original successor
  // as the merge block.
  existing_block->terminator()->InsertBefore(MakeUnique<opt::Instruction>(
      context, SpvOpSelectionMerge, 0, 0,
      opt::Instruction::OperandList(
          {{SPV_OPERAND_TYPE_ID, {successor_block_id}},
           {SPV_OPERAND_TYPE_SELECTION_CONTROL,
            {SpvSelectionControlMaskNone}}})));

  // Change the original block's terminator to be a conditional branch on the
  // given boolean, with the original successor and the new successor as branch
  // targets, and such that at runtime control will always transfer to the
  // original successor.
  existing_block->terminator()->SetOpcode(SpvOpBranchConditional);
  existing_block->terminator()->SetInOperands(
      {{SPV_OPERAND_TYPE_ID, {bool_id}},
       {SPV_OPERAND_TYPE_ID,
        {message_.condition_value() ? successor_block_id
                                    : message_.fresh_id()}},
       {SPV_OPERAND_TYPE_ID,
        {message_.condition_value() ? message_.fresh_id()
                                    : successor_block_id}}});

  // Add the new block to the enclosing function.
  new_block->SetParent(enclosing_function);
  enclosing_function->InsertBasicBlockAfter(std::move(new_block),
                                            existing_block);

  // Record the fact that the new block is dead.
  fact_manager->AddFactBlockIsDead(message_.fresh_id());

  // Fix up OpPhi instructions in the successor block, so that the values they
  // yield when control has transferred from the new block are the same as if
  // control had transferred from |message_.existing_block|.  This is guaranteed
  // to be valid since |message_.existing_block| dominates the new block by
  // construction.  Other transformations can change these phi operands to more
  // interesting values.
  context->cfg()
      ->block(successor_block_id)
      ->ForEachPhiInst([this](opt::Instruction* phi_inst) {
        // Copy the operand that provides the phi value for the first of any
        // existing predecessors.
        opt::Operand copy_of_existing_operand = phi_inst->GetInOperand(0);
        // Use this as the value associated with the new predecessor.
        phi_inst->AddOperand(std::move(copy_of_existing_operand));
        phi_inst->AddOperand({SPV_OPERAND_TYPE_ID, {message_.fresh_id()}});
      });

  // Do not rely on any existing analysis results since the control flow graph
  // of the module has changed.
  context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
}

protobufs::Transformation TransformationAddDeadBlock::ToMessage() const {
  protobufs::Transformation result;
  *result.mutable_add_dead_block() = message_;
  return result;
}

}  // namespace fuzz
}  // namespace spvtools