dg.h

/*
 *  Copyright (C) 2004-2024 Edward F. Valeev
 *
 *  This file is part of Libint compiler.
 *
 *  Libint compiler is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  Libint compiler is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Libint compiler.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
 
#ifndef _libint2_src_bin_libint_dg_h_
#define _libint2_src_bin_libint_dg_h_
 
#include <dgvertex.h>
#include <exception.h>
#include <global_macros.h>
#include <key.h>
#include <smart_ptr.h>
 
#include <algorithm>
#include <cassert>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <stdexcept>
#include <string>
#include <vector>
 
namespace libint2 {
 
//  class DGVertex;
class DGArc;
template <class T>
class DGArcRel;
template <class T>
class AlgebraicOperator;
class Strategy;
class Tactic;
class CodeContext;
class MemoryManager;
class ImplicitDimensions;
class CodeSymbols;
class GraphRegistry;
class InternalGraphRegistry;
 
class DirectedGraph : public std::enable_shared_from_this<DirectedGraph> {
 public:
  typedef DGVertex vertex;
  typedef DGArc arc;
  typedef std::shared_ptr<DGVertex> ver_ptr;
  typedef std::shared_ptr<DGArc> arc_ptr;
  typedef DGVertexKey key_type;
  typedef std::multimap<key_type, ver_ptr> VPtrAssociativeContainer;
  typedef std::list<ver_ptr> VPtrSequenceContainer;
 
  typedef VPtrSequenceContainer targets;
#if USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH
  typedef VPtrAssociativeContainer vertices;
#else
  typedef VPtrSequenceContainer vertices;
#endif
  typedef targets::iterator target_iter;
  typedef targets::const_iterator target_citer;
  typedef vertices::iterator ver_iter;
  typedef vertices::const_iterator ver_citer;
  // not possible: typedef vertex::Address address;
  typedef int address;
  // not possible: typedef vertex::Size size;
  typedef unsigned int size;
  typedef std::vector<address> addresses;
 
 private:
  static inline const ver_ptr& vertex_ptr(
      const VPtrAssociativeContainer::value_type& v) {
    return v.second;
  }
  static inline const ver_ptr& vertex_ptr(
      const VPtrSequenceContainer::value_type& v) {
    return v;
  }
  static inline ver_ptr& vertex_ptr(VPtrAssociativeContainer::value_type& v) {
    return v.second;
  }
  static inline ver_ptr& vertex_ptr(VPtrSequenceContainer::value_type& v) {
    return v;
  }
 
 public:
  DirectedGraph();
  ~DirectedGraph();
 
  unsigned int num_vertices() const { return stack_.size(); }
#if 0
    const vertices& all_vertices() const { return stack_; }
    const targets& all_targets() const { return targets_; }
#endif
  const std::shared_ptr<DGVertex>& find(
      const std::shared_ptr<DGVertex>& v) const {
    return vertex_is_on(v);
  }
 
  std::shared_ptr<DGVertex> append_vertex(const std::shared_ptr<DGVertex>& v);
 
  void append_target(const std::shared_ptr<DGVertex>&);
 
  template <class I, class RR>
  void append_target(const std::shared_ptr<I>& target) {
    target->make_a_target();
    recurse<I, RR>(target);
  }
 
  template <class RR>
  void apply_to_all() {
    typedef typename RR::TargetType TT;
    typedef vertices::iterator iter;
    for (iter v = stack_.begin(); v != stack_.end(); ++v) {
      ver_ptr& vptr = vertex_ptr(*v);
      if ((vptr)->num_exit_arcs() != 0) continue;
      std::shared_ptr<TT> tptr = std::dynamic_pointer_cast<TT, DGVertex>(v);
      if (tptr == 0) continue;
 
      std::shared_ptr<RR> rr0(new RR(tptr));
      const int num_children = rr0->num_children();
 
      for (int c = 0; c < num_children; c++) {
        std::shared_ptr<DGVertex> child = rr0->child(c);
        std::shared_ptr<DGArc> arc(new DGArcRel<RR>(tptr, child, rr0));
        tptr->add_exit_arc(arc);
 
        recurse<RR>(child);
      }
    }
  }
 
  void apply(const std::shared_ptr<Strategy>& strategy,
             const std::shared_ptr<Tactic>& tactic);
 
  typedef void (DGVertex::*DGVertexMethodPtr)();
  template <DGVertexMethodPtr method>
  void apply_at(const std::shared_ptr<DGVertex>& vertex) const {
    ((vertex.get())->*method)();
    typedef DGVertex::ArcSetType::const_iterator aciter;
    const aciter abegin = vertex->first_exit_arc();
    const aciter aend = vertex->plast_exit_arc();
    for (aciter a = abegin; a != aend; ++a) apply_at<method>((*a)->dest());
  }
 
  template <class Method>
  void foreach (Method& m) {
    typedef vertices::iterator iter;
    for (iter v = stack_.begin(); v != stack_.end(); ++v) {
      ver_ptr& vptr = vertex_ptr(*v);
      m(vptr);
    }
  }
 
  template <class Method>
  void foreach (Method& m) const {
    typedef vertices::const_iterator citer;
    for (citer v = stack_.begin(); v != stack_.end(); ++v) {
      const ver_ptr& vptr = vertex_ptr(*v);
      m(vptr);
    }
  }
  template <class Method>
  void rforeach(Method& m) {
    typedef vertices::reverse_iterator riter;
    for (riter v = stack_.rbegin(); v != stack_.rend(); ++v) {
      ver_ptr& vptr = vertex_ptr(*v);
      m(vptr);
    }
  }
 
  template <class Method>
  void rforeach(Method& m) const {
    typedef vertices::const_reverse_iterator criter;
    for (criter v = stack_.rbegin(); v != stack_.rend(); ++v) {
      const ver_ptr& vptr = vertex_ptr(*v);
      m(vptr);
    }
  }
 
  void optimize_rr_out(const std::shared_ptr<CodeContext>& context);
 
  void traverse();
 
  void update_func_names();
 
  void debug_print_traversal(std::ostream& os) const;
 
  void print_to_dot(bool symbols, std::ostream& os = std::cout) const;
 
  void generate_code(const std::shared_ptr<CodeContext>& context,
                     const std::shared_ptr<MemoryManager>& memman,
                     const std::shared_ptr<ImplicitDimensions>& dims,
                     const std::shared_ptr<CodeSymbols>& args,
                     const std::string& label, std::ostream& decl,
                     std::ostream& code);
 
  void reset();
 
  template <class RR>
  unsigned int num_children_on(const std::shared_ptr<RR>& rr) const {
    unsigned int nchildren = rr->num_children();
    unsigned int nchildren_on_stack = 0;
    for (unsigned int c = 0; c < nchildren; c++) {
      if (!vertex_is_on(rr->rr_child(c)))
        continue;
      else
        nchildren_on_stack++;
    }
 
    return nchildren_on_stack;
  }
 
  std::shared_ptr<GraphRegistry>& registry() { return registry_; }
  const std::shared_ptr<GraphRegistry>& registry() const { return registry_; }
 
  const std::string& label() const { return label_; }
  void set_label(const std::string& new_label) { label_ = new_label; }
 
  bool missing_prerequisites() const;
 
 private:
  vertices stack_;
  targets targets_;
  addresses target_accums_;
 
  // graph label, used for annotating internal work, e.g. graphviz plots
  std::string label_;
 
  typedef std::map<std::string, bool> FuncNameContainer;
  FuncNameContainer func_names_;
 
#if !USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH
  static const unsigned int default_size_ = 100;
#endif
 
  // maintains data about the graph which does not belong IN the graph
  std::shared_ptr<GraphRegistry> registry_;
  // maintains private data about the graph which does not belong IN the graph
  std::shared_ptr<InternalGraphRegistry> iregistry_;
 
  std::shared_ptr<InternalGraphRegistry>& iregistry() { return iregistry_; }
  const std::shared_ptr<InternalGraphRegistry>& iregistry() const {
    return iregistry_;
  }
 
  std::shared_ptr<DGVertex> add_vertex(const std::shared_ptr<DGVertex>&);
  void add_new_vertex(const std::shared_ptr<DGVertex>&);
  const std::shared_ptr<DGVertex>& vertex_is_on(
      const std::shared_ptr<DGVertex>& vertex) const;
  void del_vertex(vertices::iterator&);
  template <class I, class RR>
  void recurse(const std::shared_ptr<I>& vertex) {
    std::shared_ptr<DGVertex> dgvertex = add_vertex(vertex);
    if (dgvertex != vertex) return;
 
    std::shared_ptr<RR> rr0(new RR(vertex));
    const int num_children = rr0->num_children();
 
    for (int c = 0; c < num_children; c++) {
      std::shared_ptr<DGVertex> child = rr0->child(c);
      std::shared_ptr<DGArc> arc(new DGArcRel<RR>(vertex, child, rr0));
      vertex->add_exit_arc(arc);
 
      std::shared_ptr<I> child_cast =
          std::dynamic_pointer_cast<I, DGVertex>(child);
      if (child_cast == 0)
        throw std::runtime_error(
            "DirectedGraph::recurse(const std::shared_ptr<I>& vertex) -- "
            "dynamic cast failed, most probably this is a logic error!");
      recurse<I, RR>(child_cast);
    }
  }
 
  template <class RR>
  void recurse(const std::shared_ptr<DGVertex>& vertex) {
    std::shared_ptr<DGVertex> dgvertex = add_vertex(vertex);
    if (dgvertex != vertex) return;
 
    typedef typename RR::TargetType TT;
    std::shared_ptr<TT> tptr = std::dynamic_pointer_cast<TT, DGVertex>(vertex);
    if (tptr == 0) return;
 
    std::shared_ptr<RR> rr0(new RR(tptr));
    const int num_children = rr0->num_children();
 
    for (int c = 0; c < num_children; c++) {
      std::shared_ptr<DGVertex> child = rr0->child(c);
      std::shared_ptr<DGArc> arc(new DGArcRel<RR>(vertex, child, rr0));
      vertex->add_exit_arc(arc);
 
      recurse<RR>(child);
    }
  }
 
  void apply_to(const std::shared_ptr<DGVertex>& vertex,
                const std::shared_ptr<Strategy>& strategy,
                const std::shared_ptr<Tactic>& tactic);
  std::shared_ptr<DGVertex> insert_expr_at(
      const std::shared_ptr<DGVertex>& where,
      const std::shared_ptr<AlgebraicOperator<DGVertex> >& expr);
  void replace_rr_with_expr();
  void remove_trivial_arithmetics();
  void handle_trivial_nodes(const std::shared_ptr<CodeContext>& context);
  void remove_disconnected_vertices();
  void find_subtrees();
  void find_subtrees_from(const std::shared_ptr<DGVertex>& v);
  bool remove_vertex_at(const std::shared_ptr<DGVertex>& v1,
                        const std::shared_ptr<DGVertex>& v2);
 
  // Which vertex is the first to compute
  std::shared_ptr<DGVertex> first_to_compute_;
  // prepare_to_traverse must be called before actual traversal
  void prepare_to_traverse();
  // traverse_from(arc) build recurively the traversal order
  void traverse_from(const std::shared_ptr<DGArc>&);
  // schedule_computation(vertex) puts vertex first in the computation order
  void schedule_computation(const std::shared_ptr<DGVertex>&);
 
  // Compute addresses on stack assuming that quantities larger than
  // min_size_to_alloc to be allocated on stack
  void allocate_mem(const std::shared_ptr<MemoryManager>& memman,
                    const std::shared_ptr<ImplicitDimensions>& dims,
                    unsigned int min_size_to_alloc = 1);
  // Assign symbols to the vertices
  void assign_symbols(const std::shared_ptr<CodeContext>& context,
                      const std::shared_ptr<ImplicitDimensions>& dims);
  // If v is an AlgebraicOperator, assign (recursively) symbol to the operator.
  // All other must have been already assigned
  void assign_oper_symbol(const std::shared_ptr<CodeContext>& context,
                          std::shared_ptr<DGVertex>& v);
  // Print the code using symbols generated with assign_symbols()
  void print_def(const std::shared_ptr<CodeContext>& context, std::ostream& os,
                 const std::shared_ptr<ImplicitDimensions>& dims,
                 const std::shared_ptr<CodeSymbols>& args);
 
  bool cannot_enclose_in_outer_vloop() const;
};
 
//
// Nonmember utilities
//
 
inline const DirectedGraph::ver_ptr& vertex_ptr(
    const DirectedGraph::VPtrAssociativeContainer::value_type& v) {
  return v.second;
}
inline const DirectedGraph::ver_ptr& vertex_ptr(
    const DirectedGraph::VPtrSequenceContainer::value_type& v) {
  return v;
}
inline DirectedGraph::ver_ptr& vertex_ptr(
    DirectedGraph::VPtrAssociativeContainer::value_type& v) {
  return v.second;
}
inline DirectedGraph::ver_ptr& vertex_ptr(
    DirectedGraph::VPtrSequenceContainer::value_type& v) {
  return v;
}
 
#if USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH
inline DirectedGraph::key_type key(const DGVertex& v);
#endif
 
//
// Nonmember predicates
//
 
bool nonunrolled_targets(const DirectedGraph::targets& targets);
 
void extract_symbols(const std::shared_ptr<DirectedGraph>& dg);
 
// use these functors with DirectedGraph::foreach
struct PrerequisitesExtractor {
  std::deque<std::shared_ptr<DGVertex> > vertices;
  void operator()(const std::shared_ptr<DGVertex>& v);
};
struct VertexPrinter {
  VertexPrinter(std::ostream& ostr) : os(ostr) {}
  std::ostream& os;
  void operator()(const std::shared_ptr<DGVertex>& v);
};
 
};  // namespace libint2
 
#endif