dg.h

/*
 *  Copyright (C) 2004-2021 Edward F. Valeev
 *
 *  This file is part of Libint.
 *
 *  Libint 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 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.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
 
#ifndef _libint2_src_bin_libint_dg_h_
#define _libint2_src_bin_libint_dg_h_
 
#include <iostream>
#include <string>
#include <list>
#include <map>
#include <vector>
#include <deque>
#include <algorithm>
#include <stdexcept>
#include <cassert>
 
#include <global_macros.h>
#include <exception.h>
#include <smart_ptr.h>
#include <key.h>
#include <dgvertex.h>
 
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 EnableSafePtrFromThis<DirectedGraph> {
  public:
    typedef DGVertex vertex;
    typedef DGArc arc;
    typedef SafePtr<DGVertex> ver_ptr;
    typedef SafePtr<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 SafePtr<DGVertex>& find(const SafePtr<DGVertex>& v) const { return vertex_is_on(v); }
 
    SafePtr<DGVertex> append_vertex(const SafePtr<DGVertex>& v);
 
    void append_target(const SafePtr<DGVertex>&);
 
    template <class I, class RR> void append_target(const SafePtr<I>& target) {
      target->make_a_target();
      recurse<I,RR>(target);
    }
 
    template <class RR> void apply_to_all() {
      typedef typename RR::TargetType TT;
      typedef vertices::const_iterator citer;
      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;
        SafePtr<TT> tptr = dynamic_pointer_cast<TT,DGVertex>(v);
        if (tptr == 0)
          continue;
 
        SafePtr<RR> rr0(new RR(tptr));
        const int num_children = rr0->num_children();
 
        for(int c=0; c<num_children; c++) {
 
          SafePtr<DGVertex> child = rr0->child(c);
          SafePtr<DGArc> arc(new DGArcRel<RR>(tptr,child,rr0));
          tptr->add_exit_arc(arc);
 
          recurse<RR>(child);
 
        }
      }
    }
 
    void apply(const SafePtr<Strategy>& strategy,
        const SafePtr<Tactic>& tactic);
 
    typedef void (DGVertex::* DGVertexMethodPtr)();
    template <DGVertexMethodPtr method>
    void apply_at(const SafePtr<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::const_iterator citer;
      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;
      typedef vertices::iterator iter;
      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::const_reverse_iterator criter;
      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;
      typedef vertices::reverse_iterator riter;
      for(criter v=stack_.rbegin(); v!=stack_.rend(); ++v) {
        const ver_ptr& vptr = vertex_ptr(*v);
        m(vptr);
      }
    }
 
    void optimize_rr_out(const SafePtr<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 SafePtr<CodeContext>& context, const SafePtr<MemoryManager>& memman,
        const SafePtr<ImplicitDimensions>& dims, const SafePtr<CodeSymbols>& args,
        const std::string& label,
        std::ostream& decl, std::ostream& code);
 
    void reset();
 
    template <class RR>
    unsigned int
    num_children_on(const SafePtr<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;
    }
 
    SafePtr<GraphRegistry>& registry() { return registry_; }
    const SafePtr<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
    SafePtr<GraphRegistry> registry_;
    // maintains private data about the graph which does not belong IN the graph
    SafePtr<InternalGraphRegistry> iregistry_;
 
    SafePtr<InternalGraphRegistry>& iregistry() { return iregistry_; }
    const SafePtr<InternalGraphRegistry>& iregistry() const { return iregistry_; }
 
    SafePtr<DGVertex> add_vertex(const SafePtr<DGVertex>&);
    void add_new_vertex(const SafePtr<DGVertex>&);
    const SafePtr<DGVertex>& vertex_is_on(const SafePtr<DGVertex>& vertex) const;
    void del_vertex(vertices::iterator&);
    template <class I, class RR> void recurse(const SafePtr<I>& vertex)  {
      SafePtr<DGVertex> dgvertex = add_vertex(vertex);
      if (dgvertex != vertex)
        return;
 
      SafePtr<RR> rr0(new RR(vertex));
      const int num_children = rr0->num_children();
 
      for(int c=0; c<num_children; c++) {
 
        SafePtr<DGVertex> child = rr0->child(c);
        SafePtr<DGArc> arc(new DGArcRel<RR>(vertex,child,rr0));
        vertex->add_exit_arc(arc);
 
        SafePtr<I> child_cast = dynamic_pointer_cast<I,DGVertex>(child);
        if (child_cast == 0)
          throw std::runtime_error("DirectedGraph::recurse(const SafePtr<I>& vertex) -- dynamic cast failed, most probably this is a logic error!");
        recurse<I,RR>(child_cast);
 
      }
    }
 
    template <class RR> void recurse(const SafePtr<DGVertex>& vertex)  {
      SafePtr<DGVertex> dgvertex = add_vertex(vertex);
      if (dgvertex != vertex)
        return;
 
      typedef typename RR::TargetType TT;
      SafePtr<TT> tptr = dynamic_pointer_cast<TT,DGVertex>(vertex);
      if (tptr == 0)
        return;
 
      SafePtr<RR> rr0(new RR(tptr));
      const int num_children = rr0->num_children();
 
      for(int c=0; c<num_children; c++) {
 
        SafePtr<DGVertex> child = rr0->child(c);
        SafePtr<DGArc> arc(new DGArcRel<RR>(vertex,child,rr0));
        vertex->add_exit_arc(arc);
 
        recurse<RR>(child);
      }
    }
 
    void apply_to(const SafePtr<DGVertex>& vertex,
        const SafePtr<Strategy>& strategy,
        const SafePtr<Tactic>& tactic);
    SafePtr<DGVertex> insert_expr_at(const SafePtr<DGVertex>& where, const SafePtr< AlgebraicOperator<DGVertex> >& expr);
    void replace_rr_with_expr();
    void remove_trivial_arithmetics();
    void handle_trivial_nodes(const SafePtr<CodeContext>& context);
    void remove_disconnected_vertices();
    void find_subtrees();
    void find_subtrees_from(const SafePtr<DGVertex>& v);
    bool remove_vertex_at(const SafePtr<DGVertex>& v1, const SafePtr<DGVertex>& v2);
 
    // Which vertex is the first to compute
    SafePtr<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 SafePtr<DGArc>&);
    // schedule_computation(vertex) puts vertex first in the computation order
    void schedule_computation(const SafePtr<DGVertex>&);
 
    // Compute addresses on stack assuming that quantities larger than min_size_to_alloc to be allocated on stack
    void allocate_mem(const SafePtr<MemoryManager>& memman,
        const SafePtr<ImplicitDimensions>& dims,
        unsigned int min_size_to_alloc = 1);
    // Assign symbols to the vertices
    void assign_symbols(const SafePtr<CodeContext>& context, const SafePtr<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 SafePtr<CodeContext>& context, SafePtr<DGVertex>& v);
    // Print the code using symbols generated with assign_symbols()
    void print_def(const SafePtr<CodeContext>& context, std::ostream& os,
        const SafePtr<ImplicitDimensions>& dims,
        const SafePtr<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 SafePtr<DirectedGraph>& dg);
 
  // use these functors with DirectedGraph::foreach
  struct PrerequisitesExtractor {
    std::deque< SafePtr<DGVertex> > vertices;
    void operator()(const SafePtr<DGVertex>& v);
  };
  struct VertexPrinter {
    VertexPrinter(std::ostream& ostr) : os(ostr) {}
    std::ostream& os;
    void operator()(const SafePtr<DGVertex>& v);
  };
 
};
 
 
#endif