llvm/llvm/include/llvm/CodeGen/PBQP/ReductionRules.h

//===- ReductionRules.h - Reduction Rules -----------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Reduction Rules.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
#define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H

#include "Graph.h"
#include "Math.h"
#include "Solution.h"
#include <cassert>
#include <limits>

namespace llvm {
namespace PBQP {

  /// Reduce a node of degree one.
  ///
  /// Propagate costs from the given node, which must be of degree one, to its
  /// neighbor. Notify the problem domain.
  template <typename GraphT>
  void applyR1(GraphT &G, typename GraphT::NodeId NId) { … }

  template <typename GraphT>
  void applyR2(GraphT &G, typename GraphT::NodeId NId) { … }

#ifndef NDEBUG
  // Does this Cost vector have any register options ?
  template <typename VectorT>
  bool hasRegisterOptions(const VectorT &V) {
    unsigned VL = V.getLength();

    // An empty or spill only cost vector does not provide any register option.
    if (VL <= 1)
      return false;

    // If there are registers in the cost vector, but all of them have infinite
    // costs, then ... there is no available register.
    for (unsigned i = 1; i < VL; ++i)
      if (V[i] != std::numeric_limits<PBQP::PBQPNum>::infinity())
        return true;

    return false;
  }
#endif

  // Find a solution to a fully reduced graph by backpropagation.
  //
  // Given a graph and a reduction order, pop each node from the reduction
  // order and greedily compute a minimum solution based on the node costs, and
  // the dependent costs due to previously solved nodes.
  //
  // Note - This does not return the graph to its original (pre-reduction)
  //        state: the existing solvers destructively alter the node and edge
  //        costs. Given that, the backpropagate function doesn't attempt to
  //        replace the edges either, but leaves the graph in its reduced
  //        state.
  template <typename GraphT, typename StackT>
  Solution backpropagate(GraphT& G, StackT stack) { … }

} // end namespace PBQP
} // end namespace llvm

#endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H