source/fuzz/fuzzer_pass_add_opphi_synonyms.cpp

// Copyright (c) 2020 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/fuzzer_pass_add_opphi_synonyms.h"

#include "source/fuzz/fuzzer_util.h"
#include "source/fuzz/transformation_add_opphi_synonym.h"

namespace spvtools {
namespace fuzz {

FuzzerPassAddOpPhiSynonyms::FuzzerPassAddOpPhiSynonyms(
    opt::IRContext* ir_context, TransformationContext* transformation_context,
    FuzzerContext* fuzzer_context,
    protobufs::TransformationSequence* transformations,
    bool ignore_inapplicable_transformations)
    : FuzzerPass(ir_context, transformation_context, fuzzer_context,
                 transformations, ignore_inapplicable_transformations) {}

void FuzzerPassAddOpPhiSynonyms::Apply() {
  // Get a list of synonymous ids with the same type that can be used in the
  // same OpPhi instruction.
  auto equivalence_classes = GetIdEquivalenceClasses();

  // Make a list of references, to avoid copying sets unnecessarily.
  std::vector<std::set<uint32_t>*> equivalence_class_pointers;
  for (auto& set : equivalence_classes) {
    equivalence_class_pointers.push_back(&set);
  }

  // Keep a list of transformations to apply at the end.
  std::vector<TransformationAddOpPhiSynonym> transformations_to_apply;

  for (auto& function : *GetIRContext()->module()) {
    for (auto& block : function) {
      // Randomly decide whether to consider this block.
      if (!GetFuzzerContext()->ChoosePercentage(
              GetFuzzerContext()->GetChanceOfAddingOpPhiSynonym())) {
        continue;
      }

      // The block must not be dead.
      if (GetTransformationContext()->GetFactManager()->BlockIsDead(
              block.id())) {
        continue;
      }

      // The block must have at least one predecessor.
      size_t num_preds = GetIRContext()->cfg()->preds(block.id()).size();
      if (num_preds == 0) {
        continue;
      }

      std::set<uint32_t>* chosen_equivalence_class = nullptr;

      if (num_preds > 1) {
        // If the block has more than one predecessor, prioritise sets with at
        // least 2 ids available at some predecessor.
        chosen_equivalence_class = MaybeFindSuitableEquivalenceClassRandomly(
            equivalence_class_pointers, block.id(), 2);
      }

      // If a set was not already chosen, choose one with at least one available
      // id.
      if (!chosen_equivalence_class) {
        chosen_equivalence_class = MaybeFindSuitableEquivalenceClassRandomly(
            equivalence_class_pointers, block.id(), 1);
      }

      // If no suitable set was found, we cannot apply the transformation to
      // this block.
      if (!chosen_equivalence_class) {
        continue;
      }

      // Initialise the map from predecessor labels to ids.
      std::map<uint32_t, uint32_t> preds_to_ids;

      // Keep track of the ids used and of the id of a predecessor with at least
      // two ids to choose from. This is to ensure that, if possible, at least
      // two distinct ids will be used.
      std::set<uint32_t> ids_chosen;
      uint32_t pred_with_alternatives = 0;

      // Choose an id for each predecessor.
      for (uint32_t pred_id : GetIRContext()->cfg()->preds(block.id())) {
        auto suitable_ids = GetSuitableIds(*chosen_equivalence_class, pred_id);
        assert(!suitable_ids.empty() &&
               "We must be able to find at least one suitable id because the "
               "equivalence class was chosen among suitable ones.");

        // If this predecessor has more than one id to choose from and it is the
        // first one of this kind that we found, remember its id.
        if (suitable_ids.size() > 1 && !pred_with_alternatives) {
          pred_with_alternatives = pred_id;
        }

        uint32_t chosen_id =
            suitable_ids[GetFuzzerContext()->RandomIndex(suitable_ids)];

        // Add this id to the set of ids chosen.
        ids_chosen.emplace(chosen_id);

        // Add the pair (predecessor, chosen id) to the map.
        preds_to_ids[pred_id] = chosen_id;
      }

      // If:
      // - the block has more than one predecessor
      // - at least one predecessor has more than one alternative
      // - the same id has been chosen by all the predecessors
      // then choose another one for the predecessor with more than one
      // alternative.
      if (num_preds > 1 && pred_with_alternatives != 0 &&
          ids_chosen.size() == 1) {
        auto suitable_ids =
            GetSuitableIds(*chosen_equivalence_class, pred_with_alternatives);
        uint32_t chosen_id =
            GetFuzzerContext()->RemoveAtRandomIndex(&suitable_ids);
        if (chosen_id == preds_to_ids[pred_with_alternatives]) {
          chosen_id = GetFuzzerContext()->RemoveAtRandomIndex(&suitable_ids);
        }

        preds_to_ids[pred_with_alternatives] = chosen_id;
      }

      // Add the transformation to the list of transformations to apply.
      transformations_to_apply.emplace_back(block.id(), preds_to_ids,
                                            GetFuzzerContext()->GetFreshId());
    }
  }

  // Apply the transformations.
  for (const auto& transformation : transformations_to_apply) {
    ApplyTransformation(transformation);
  }
}

std::vector<std::set<uint32_t>>
FuzzerPassAddOpPhiSynonyms::GetIdEquivalenceClasses() {
  std::vector<std::set<uint32_t>> id_equivalence_classes;

  // Keep track of all the ids that have already be assigned to a class.
  std::set<uint32_t> already_in_a_class;

  for (const auto& pair : GetIRContext()->get_def_use_mgr()->id_to_defs()) {
    // Exclude ids that have already been assigned to a class.
    if (already_in_a_class.count(pair.first)) {
      continue;
    }

    // Exclude irrelevant ids.
    if (GetTransformationContext()->GetFactManager()->IdIsIrrelevant(
            pair.first)) {
      continue;
    }

    // Exclude ids having a type that is not allowed by the transformation.
    if (!TransformationAddOpPhiSynonym::CheckTypeIsAllowed(
            GetIRContext(), pair.second->type_id())) {
      continue;
    }

    // Exclude OpFunction and OpUndef instructions, because:
    // - OpFunction does not yield a value;
    // - OpUndef yields an undefined value at each use, so it should never be a
    //   synonym of another id.
    if (pair.second->opcode() == SpvOpFunction ||
        pair.second->opcode() == SpvOpUndef) {
      continue;
    }

    // We need a new equivalence class for this id.
    std::set<uint32_t> new_equivalence_class;

    // Add this id to the class.
    new_equivalence_class.emplace(pair.first);
    already_in_a_class.emplace(pair.first);

    // Add all the synonyms with the same type to this class.
    for (auto synonym :
         GetTransformationContext()->GetFactManager()->GetSynonymsForId(
             pair.first)) {
      // The synonym must be a plain id - it cannot be an indexed access into a
      // composite.
      if (synonym->index_size() > 0) {
        continue;
      }

      // The synonym must not be irrelevant.
      if (GetTransformationContext()->GetFactManager()->IdIsIrrelevant(
              synonym->object())) {
        continue;
      }

      auto synonym_def =
          GetIRContext()->get_def_use_mgr()->GetDef(synonym->object());
      // The synonym must exist and have the same type as the id we are
      // considering.
      if (!synonym_def || synonym_def->type_id() != pair.second->type_id()) {
        continue;
      }

      // We can add this synonym to the new equivalence class.
      new_equivalence_class.emplace(synonym->object());
      already_in_a_class.emplace(synonym->object());
    }

    // Add the new equivalence class to the list of equivalence classes.
    id_equivalence_classes.emplace_back(std::move(new_equivalence_class));
  }

  return id_equivalence_classes;
}

bool FuzzerPassAddOpPhiSynonyms::EquivalenceClassIsSuitableForBlock(
    const std::set<uint32_t>& equivalence_class, uint32_t block_id,
    uint32_t distinct_ids_required) {
  bool at_least_one_id_for_each_pred = true;

  // Keep a set of the suitable ids found.
  std::set<uint32_t> suitable_ids_found;

  // Loop through all the predecessors of the block.
  for (auto pred_id : GetIRContext()->cfg()->preds(block_id)) {
    // Find the last instruction in the predecessor block.
    auto last_instruction =
        GetIRContext()->get_instr_block(pred_id)->terminator();

    // Initially assume that there is not a suitable id for this predecessor.
    bool at_least_one_suitable_id_found = false;
    for (uint32_t id : equivalence_class) {
      if (fuzzerutil::IdIsAvailableBeforeInstruction(GetIRContext(),
                                                     last_instruction, id)) {
        // We have found a suitable id.
        at_least_one_suitable_id_found = true;
        suitable_ids_found.emplace(id);

        // If we have already found enough distinct suitable ids, we don't need
        // to check the remaining ones for this predecessor.
        if (suitable_ids_found.size() >= distinct_ids_required) {
          break;
        }
      }
    }
    // If no suitable id was found for this predecessor, this equivalence class
    // is not suitable and we don't need to check the other predecessors.
    if (!at_least_one_suitable_id_found) {
      at_least_one_id_for_each_pred = false;
      break;
    }
  }

  // The equivalence class is suitable if at least one suitable id was found for
  // each predecessor and we have found at least |distinct_ids_required|
  // distinct suitable ids in general.
  return at_least_one_id_for_each_pred &&
         suitable_ids_found.size() >= distinct_ids_required;
}

std::vector<uint32_t> FuzzerPassAddOpPhiSynonyms::GetSuitableIds(
    const std::set<uint32_t>& ids, uint32_t pred_id) {
  // Initialise an empty vector of suitable ids.
  std::vector<uint32_t> suitable_ids;

  // Get the predecessor block.
  auto predecessor = fuzzerutil::MaybeFindBlock(GetIRContext(), pred_id);

  // Loop through the ids to find the suitable ones.
  for (uint32_t id : ids) {
    if (fuzzerutil::IdIsAvailableBeforeInstruction(
            GetIRContext(), predecessor->terminator(), id)) {
      suitable_ids.push_back(id);
    }
  }

  return suitable_ids;
}

std::set<uint32_t>*
FuzzerPassAddOpPhiSynonyms::MaybeFindSuitableEquivalenceClassRandomly(
    const std::vector<std::set<uint32_t>*>& candidates, uint32_t block_id,
    uint32_t distinct_ids_required) {
  auto remaining_candidates = candidates;
  while (!remaining_candidates.empty()) {
    // Choose one set randomly and return it if it is suitable.
    auto chosen =
        GetFuzzerContext()->RemoveAtRandomIndex(&remaining_candidates);
    if (EquivalenceClassIsSuitableForBlock(*chosen, block_id,
                                           distinct_ids_required)) {
      return chosen;
    }
  }

  // No suitable sets were found.
  return nullptr;
}

}  // namespace fuzz
}  // namespace spvtools