source/reduce/reducer.cpp

// Copyright (c) 2018 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/reduce/reducer.h"

#include <cassert>
#include <sstream>

#include "source/reduce/conditional_branch_to_simple_conditional_branch_opportunity_finder.h"
#include "source/reduce/merge_blocks_reduction_opportunity_finder.h"
#include "source/reduce/operand_to_const_reduction_opportunity_finder.h"
#include "source/reduce/operand_to_dominating_id_reduction_opportunity_finder.h"
#include "source/reduce/operand_to_undef_reduction_opportunity_finder.h"
#include "source/reduce/remove_block_reduction_opportunity_finder.h"
#include "source/reduce/remove_function_reduction_opportunity_finder.h"
#include "source/reduce/remove_selection_reduction_opportunity_finder.h"
#include "source/reduce/remove_unused_instruction_reduction_opportunity_finder.h"
#include "source/reduce/remove_unused_struct_member_reduction_opportunity_finder.h"
#include "source/reduce/simple_conditional_branch_to_branch_opportunity_finder.h"
#include "source/reduce/structured_construct_to_block_reduction_opportunity_finder.h"
#include "source/reduce/structured_loop_to_selection_reduction_opportunity_finder.h"
#include "source/spirv_reducer_options.h"

namespace spvtools {
namespace reduce {

Reducer::Reducer(spv_target_env target_env) : target_env_(target_env) {}

Reducer::~Reducer() = default;

void Reducer::SetMessageConsumer(MessageConsumer c) {
  for (auto& pass : passes_) {
    pass->SetMessageConsumer(c);
  }
  for (auto& pass : cleanup_passes_) {
    pass->SetMessageConsumer(c);
  }
  consumer_ = std::move(c);
}

void Reducer::SetInterestingnessFunction(
    Reducer::InterestingnessFunction interestingness_function) {
  interestingness_function_ = std::move(interestingness_function);
}

Reducer::ReductionResultStatus Reducer::Run(
    const std::vector<uint32_t>& binary_in, std::vector<uint32_t>* binary_out,
    spv_const_reducer_options options,
    spv_validator_options validator_options) {
  std::vector<uint32_t> current_binary(binary_in);

  spvtools::SpirvTools tools(target_env_);
  assert(tools.IsValid() && "Failed to create SPIRV-Tools interface");

  // Keeps track of how many reduction attempts have been tried.  Reduction
  // bails out if this reaches a given limit.
  uint32_t reductions_applied = 0;

  // Initial state should be valid.
  if (!tools.Validate(&current_binary[0], current_binary.size(),
                      validator_options)) {
    consumer_(SPV_MSG_INFO, nullptr, {},
              "Initial binary is invalid; stopping.");
    return Reducer::ReductionResultStatus::kInitialStateInvalid;
  }

  // Initial state should be interesting.
  if (!interestingness_function_(current_binary, reductions_applied)) {
    consumer_(SPV_MSG_INFO, nullptr, {},
              "Initial state was not interesting; stopping.");
    return Reducer::ReductionResultStatus::kInitialStateNotInteresting;
  }

  Reducer::ReductionResultStatus result =
      RunPasses(&passes_, options, validator_options, tools, &current_binary,
                &reductions_applied);

  if (result == Reducer::ReductionResultStatus::kComplete) {
    // Cleanup passes.
    result = RunPasses(&cleanup_passes_, options, validator_options, tools,
                       &current_binary, &reductions_applied);
  }

  if (result == Reducer::ReductionResultStatus::kComplete) {
    consumer_(SPV_MSG_INFO, nullptr, {}, "No more to reduce; stopping.");
  }

  // Even if the reduction has failed by this point (e.g. due to producing an
  // invalid binary), we still update the output binary for better debugging.
  *binary_out = std::move(current_binary);

  return result;
}

void Reducer::AddDefaultReductionPasses() {
  AddReductionPass(
      spvtools::MakeUnique<RemoveUnusedInstructionReductionOpportunityFinder>(
          false));
  AddReductionPass(
      spvtools::MakeUnique<OperandToUndefReductionOpportunityFinder>());
  AddReductionPass(
      spvtools::MakeUnique<OperandToConstReductionOpportunityFinder>());
  AddReductionPass(
      spvtools::MakeUnique<OperandToDominatingIdReductionOpportunityFinder>());
  AddReductionPass(spvtools::MakeUnique<
                   StructuredConstructToBlockReductionOpportunityFinder>());
  AddReductionPass(spvtools::MakeUnique<
                   StructuredLoopToSelectionReductionOpportunityFinder>());
  AddReductionPass(
      spvtools::MakeUnique<MergeBlocksReductionOpportunityFinder>());
  AddReductionPass(
      spvtools::MakeUnique<RemoveFunctionReductionOpportunityFinder>());
  AddReductionPass(
      spvtools::MakeUnique<RemoveBlockReductionOpportunityFinder>());
  AddReductionPass(
      spvtools::MakeUnique<RemoveSelectionReductionOpportunityFinder>());
  AddReductionPass(
      spvtools::MakeUnique<
          ConditionalBranchToSimpleConditionalBranchOpportunityFinder>());
  AddReductionPass(
      spvtools::MakeUnique<SimpleConditionalBranchToBranchOpportunityFinder>());
  AddReductionPass(spvtools::MakeUnique<
                   RemoveUnusedStructMemberReductionOpportunityFinder>());

  // Cleanup passes.

  AddCleanupReductionPass(
      spvtools::MakeUnique<RemoveUnusedInstructionReductionOpportunityFinder>(
          true));
}

void Reducer::AddReductionPass(
    std::unique_ptr<ReductionOpportunityFinder> finder) {
  passes_.push_back(
      spvtools::MakeUnique<ReductionPass>(target_env_, std::move(finder)));
}

void Reducer::AddCleanupReductionPass(
    std::unique_ptr<ReductionOpportunityFinder> finder) {
  cleanup_passes_.push_back(
      spvtools::MakeUnique<ReductionPass>(target_env_, std::move(finder)));
}

bool Reducer::ReachedStepLimit(uint32_t current_step,
                               spv_const_reducer_options options) {
  return current_step >= options->step_limit;
}

Reducer::ReductionResultStatus Reducer::RunPasses(
    std::vector<std::unique_ptr<ReductionPass>>* passes,
    spv_const_reducer_options options, spv_validator_options validator_options,
    const SpirvTools& tools, std::vector<uint32_t>* current_binary,
    uint32_t* const reductions_applied) {
  // Determines whether, on completing one round of reduction passes, it is
  // worthwhile trying a further round.
  bool another_round_worthwhile = true;

  // Apply round after round of reduction passes until we hit the reduction
  // step limit, or deem that another round is not going to be worthwhile.
  while (!ReachedStepLimit(*reductions_applied, options) &&
         another_round_worthwhile) {
    // At the start of a round of reduction passes, assume another round will
    // not be worthwhile unless we find evidence to the contrary.
    another_round_worthwhile = false;

    // Iterate through the available passes.
    for (auto& pass : *passes) {
      // If this pass hasn't reached its minimum granularity then it's
      // worth eventually doing another round of reductions, in order to
      // try this pass at a finer granularity.
      another_round_worthwhile |= !pass->ReachedMinimumGranularity();

      // Keep applying this pass at its current granularity until it stops
      // working or we hit the reduction step limit.
      consumer_(SPV_MSG_INFO, nullptr, {},
                ("Trying pass " + pass->GetName() + ".").c_str());
      do {
        auto maybe_result =
            pass->TryApplyReduction(*current_binary, options->target_function);
        if (maybe_result.empty()) {
          // For this round, the pass has no more opportunities (chunks) to
          // apply, so move on to the next pass.
          consumer_(
              SPV_MSG_INFO, nullptr, {},
              ("Pass " + pass->GetName() + " did not make a reduction step.")
                  .c_str());
          break;
        }
        bool interesting = false;
        std::stringstream stringstream;
        (*reductions_applied)++;
        stringstream << "Pass " << pass->GetName() << " made reduction step "
                     << *reductions_applied << ".";
        consumer_(SPV_MSG_INFO, nullptr, {}, (stringstream.str().c_str()));
        if (!tools.Validate(&maybe_result[0], maybe_result.size(),
                            validator_options)) {
          // The reduction step went wrong and an invalid binary was produced.
          // By design, this shouldn't happen; this is a safeguard to stop an
          // invalid binary from being regarded as interesting.
          consumer_(SPV_MSG_INFO, nullptr, {},
                    "Reduction step produced an invalid binary.");
          if (options->fail_on_validation_error) {
            // In this mode, we fail, so we update the current binary so it is
            // output for debugging.
            *current_binary = std::move(maybe_result);
            return Reducer::ReductionResultStatus::kStateInvalid;
          }
        } else if (interestingness_function_(maybe_result,
                                             *reductions_applied)) {
          // Success!  The binary produced by this reduction step is
          // interesting, so make it the binary of interest henceforth, and
          // note that it's worth doing another round of reduction passes.
          consumer_(SPV_MSG_INFO, nullptr, {}, "Reduction step succeeded.");
          *current_binary = std::move(maybe_result);
          interesting = true;
          another_round_worthwhile = true;
        }
        // We must call this before the next call to TryApplyReduction.
        pass->NotifyInteresting(interesting);
        // Bail out if the reduction step limit has been reached.
      } while (!ReachedStepLimit(*reductions_applied, options));
    }
  }

  // Report whether reduction completed, or bailed out early due to reaching
  // the step limit.
  if (ReachedStepLimit(*reductions_applied, options)) {
    consumer_(SPV_MSG_INFO, nullptr, {},
              "Reached reduction step limit; stopping.");
    return Reducer::ReductionResultStatus::kReachedStepLimit;
  }

  // The passes completed successfully, although we may still run more passes.
  return Reducer::ReductionResultStatus::kComplete;
}

}  // namespace reduce
}  // namespace spvtools