// 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/fuzzer_pass_copy_objects.h"

#include "source/fuzz/transformation_copy_object.h"

namespace spvtools {
namespace fuzz {

FuzzerPassCopyObjects::FuzzerPassCopyObjects(
    opt::IRContext* ir_context, FactManager* fact_manager,
    FuzzerContext* fuzzer_context,
    protobufs::TransformationSequence* transformations)
    : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {}

FuzzerPassCopyObjects::~FuzzerPassCopyObjects() = default;

void FuzzerPassCopyObjects::Apply() {
  // Consider every block in every function.
  for (auto& function : *GetIRContext()->module()) {
    for (auto& block : function) {
      // We now consider every instruction in the block, randomly deciding
      // whether to add an object copy before the instruction.

      // In order to insert an object copy instruction, we need to be able to
      // identify the instruction a copy should be inserted before.  We do this
      // by tracking a base instruction, which must generate a result id, and an
      // offset (to allow us to identify instructions that do not generate
      // result ids).

      // The initial base instruction is the block label.
      uint32_t base = block.id();
      uint32_t offset = 0;
      // Consider every instruction in the block.
      for (auto inst_it = block.begin(); inst_it != block.end(); ++inst_it) {
        if (inst_it->HasResultId()) {
          // In the case that the instruction has a result id, we use the
          // instruction as its own base, with zero offset.
          base = inst_it->result_id();
          offset = 0;
        } else {
          // The instruction does not have a result id, so we need to identify
          // it via the latest instruction that did have a result id (base), and
          // an incremented offset.
          offset++;
        }

        // Check whether it is legitimate to insert a copy before this
        // instruction.
        if (!TransformationCopyObject::CanInsertCopyBefore(inst_it)) {
          continue;
        }

        // Randomly decide whether to try inserting an object copy here.
        if (!GetFuzzerContext()->ChoosePercentage(
                GetFuzzerContext()->GetChanceOfCopyingObject())) {
          continue;
        }

        // Populate list of potential instructions that can be copied.
        // TODO(afd) The following is (relatively) simple, but may end up being
        //  prohibitively inefficient, as it walks the whole dominator tree for
        //  every copy that is added.
        std::vector<opt::Instruction*> copyable_instructions;

        // Consider all global declarations
        for (auto& global : GetIRContext()->module()->types_values()) {
          if (TransformationCopyObject::IsCopyable(GetIRContext(), &global)) {
            copyable_instructions.push_back(&global);
          }
        }

        // Consider all previous instructions in this block
        for (auto prev_inst_it = block.begin(); prev_inst_it != inst_it;
             ++prev_inst_it) {
          if (TransformationCopyObject::IsCopyable(GetIRContext(),
                                                   &*prev_inst_it)) {
            copyable_instructions.push_back(&*prev_inst_it);
          }
        }

        // Walk the dominator tree to consider all instructions from dominating
        // blocks
        auto dominator_analysis =
            GetIRContext()->GetDominatorAnalysis(&function);
        for (auto next_dominator =
                 dominator_analysis->ImmediateDominator(&block);
             next_dominator != nullptr;
             next_dominator =
                 dominator_analysis->ImmediateDominator(next_dominator)) {
          for (auto& dominating_inst : *next_dominator) {
            if (TransformationCopyObject::IsCopyable(GetIRContext(),
                                                     &dominating_inst)) {
              copyable_instructions.push_back(&dominating_inst);
            }
          }
        }

        // At this point, |copyable_instructions| contains all the instructions
        // we might think of copying.

        if (!copyable_instructions.empty()) {
          // Choose a copyable instruction at random, and create and apply an
          // object copying transformation based on it.
          uint32_t index =
              GetFuzzerContext()->RandomIndex(copyable_instructions);
          TransformationCopyObject transformation(
              copyable_instructions[index]->result_id(), base, offset,
              GetFuzzerContext()->GetFreshId());
          assert(
              transformation.IsApplicable(GetIRContext(), *GetFactManager()) &&
              "This transformation should be applicable by construction.");
          transformation.Apply(GetIRContext(), GetFactManager());
          *GetTransformations()->add_transformation() =
              transformation.ToMessage();

          if (!inst_it->HasResultId()) {
            // We have inserted a new instruction before the current
            // instruction, and we are tracking the current id-less instruction
            // via an offset (offset) from a previous instruction (base) that
            // has an id. We increment |offset| to reflect the newly-inserted
            // instruction.
            //
            // This is slightly preferable to the alternative of setting |base|
            // to be the result id of the new instruction, since on replay we
            // might end up eliminating this copy but keeping a subsequent copy.
            offset++;
          }
        }
      }
    }
  }
}

}  // namespace fuzz
}  // namespace spvtools