text: // 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(
      protobufs::TransformationAddDeadBlock message)
      : message_(std::move(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* ir_context,
      const TransformationContext& transformation_context) const {
    // The new block's id must be fresh.
    if (!fuzzerutil::IsFreshId(ir_context, message_.fresh_id())) {
      return false;
    }
  
    // First, we check that a constant with the same value as
    // |message_.condition_value| is present.
    if (!fuzzerutil::MaybeGetBoolConstant(ir_context, transformation_context,
                                          message_.condition_value(), false)) {
      // 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(ir_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(ir_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 (ir_context->cfg()->block(successor_block_id)->IsLoopHeader()) {
      return false;
    }
  
    // |existing_block| must be reachable.
    opt::DominatorAnalysis* dominator_analysis =
        ir_context->GetDominatorAnalysis(existing_block->GetParent());
    if (!dominator_analysis->IsReachable(existing_block->id())) {
      return false;
    }
  
    assert(existing_block->id() != successor_block_id &&
           "|existing_block| must be different from |successor_block_id|");
  
    // Even though we know |successor_block_id| is not a merge block, it might
    // still have multiple predecessors because divergent control flow is allowed
    // to converge early (before the merge block). In this case, when we create
    // the selection construct, its header |existing_block| will not dominate the
    // merge block |successor_block_id|, which is invalid. Thus, |existing_block|
    // must dominate |successor_block_id|.
    if (!dominator_analysis->Dominates(existing_block->id(),
                                       successor_block_id)) {
      return false;
    }
  
    return true;
  }
  
  void TransformationAddDeadBlock::Apply(
      opt::IRContext* ir_context,
      TransformationContext* transformation_context) const {
    // Update the module id bound so that it is at least the id of the new block.
    fuzzerutil::UpdateModuleIdBound(ir_context, message_.fresh_id());
  
    // Get the existing block and its successor.
    auto existing_block = ir_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::MaybeGetBoolConstant(
        ir_context, *transformation_context, message_.condition_value(), false);
  
    // 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>(
            ir_context, SpvOpLabel, 0, message_.fresh_id(),
            opt::Instruction::OperandList()));
    new_block->AddInstruction(MakeUnique<opt::Instruction>(
        ir_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>(
        ir_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.
    enclosing_function->InsertBasicBlockAfter(std::move(new_block),
                                              existing_block);
  
    // 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.
    ir_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.
    ir_context->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
  
    // Record the fact that the new block is dead.
    transformation_context->GetFactManager()->AddFactBlockIsDead(
        message_.fresh_id());
  }
  
  protobufs::Transformation TransformationAddDeadBlock::ToMessage() const {
    protobufs::Transformation result;
    *result.mutable_add_dead_block() = message_;
    return result;
  }
  
  std::unordered_set<uint32_t> TransformationAddDeadBlock::GetFreshIds() const {
    return {message_.fresh_id()};
  }
  
  }  // namespace fuzz
  }  // namespace spvtools
  