LIBINT  2.6.0
dg.h
1 /*
2  * Copyright (C) 2004-2019 Edward F. Valeev
3  *
4  * This file is part of Libint.
5  *
6  * Libint is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * Libint is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with Libint. If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 #ifndef _libint2_src_bin_libint_dg_h_
22 #define _libint2_src_bin_libint_dg_h_
23 
24 #include <iostream>
25 #include <string>
26 #include <list>
27 #include <map>
28 #include <vector>
29 #include <deque>
30 #include <algorithm>
31 #include <stdexcept>
32 #include <cassert>
33 
34 #include <global_macros.h>
35 #include <exception.h>
36 #include <smart_ptr.h>
37 #include <key.h>
38 #include <dgvertex.h>
39 
40 namespace libint2 {
41 
42 // class DGVertex;
43  class DGArc;
44  template <class T> class DGArcRel;
45  template <class T> class AlgebraicOperator;
46  class Strategy;
47  class Tactic;
48  class CodeContext;
49  class MemoryManager;
50  class ImplicitDimensions;
51  class CodeSymbols;
52  class GraphRegistry;
54 
63  class DirectedGraph : public EnableSafePtrFromThis<DirectedGraph> {
64  public:
65  typedef DGVertex vertex;
66  typedef DGArc arc;
67  typedef SafePtr<DGVertex> ver_ptr;
68  typedef SafePtr<DGArc> arc_ptr;
69  typedef DGVertexKey key_type;
70  typedef std::multimap<key_type,ver_ptr> VPtrAssociativeContainer;
71  typedef std::list<ver_ptr> VPtrSequenceContainer;
72 
73  typedef VPtrSequenceContainer targets;
74 #if USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH
75  typedef VPtrAssociativeContainer vertices;
76 #else
77  typedef VPtrSequenceContainer vertices;
78 #endif
79  typedef targets::iterator target_iter;
80  typedef targets::const_iterator target_citer;
81  typedef vertices::iterator ver_iter;
82  typedef vertices::const_iterator ver_citer;
83  //not possible: typedef vertex::Address address;
84  typedef int address;
85  //not possible: typedef vertex::Size size;
86  typedef unsigned int size;
87  typedef std::vector<address> addresses;
88 
89  private:
91  static inline const ver_ptr& vertex_ptr(const VPtrAssociativeContainer::value_type& v) {
92  return v.second;
93  }
94  static inline const ver_ptr& vertex_ptr(const VPtrSequenceContainer::value_type& v) {
95  return v;
96  }
98  static inline ver_ptr& vertex_ptr(VPtrAssociativeContainer::value_type& v) {
99  return v.second;
100  }
101  static inline ver_ptr& vertex_ptr(VPtrSequenceContainer::value_type& v) {
102  return v;
103  }
104 
105  public:
106 
109  DirectedGraph();
110  ~DirectedGraph();
111 
113  unsigned int num_vertices() const { return stack_.size(); }
114 #if 0
115  const vertices& all_vertices() const { return stack_; }
118  const targets& all_targets() const { return targets_; }
119 #endif
120  const SafePtr<DGVertex>& find(const SafePtr<DGVertex>& v) const { return vertex_is_on(v); }
123 
127  SafePtr<DGVertex> append_vertex(const SafePtr<DGVertex>& v);
128 
131  void append_target(const SafePtr<DGVertex>&);
132 
145  template <class I, class RR> void append_target(const SafePtr<I>& target) {
146  target->make_a_target();
147  recurse<I,RR>(target);
148  }
149 
160  template <class RR> void apply_to_all() {
161  typedef typename RR::TargetType TT;
162  typedef vertices::const_iterator citer;
163  typedef vertices::iterator iter;
164  for(iter v=stack_.begin(); v!=stack_.end(); ++v) {
165  ver_ptr& vptr = vertex_ptr(*v);
166  if ((vptr)->num_exit_arcs() != 0)
167  continue;
168  SafePtr<TT> tptr = dynamic_pointer_cast<TT,DGVertex>(v);
169  if (tptr == 0)
170  continue;
171 
172  SafePtr<RR> rr0(new RR(tptr));
173  const int num_children = rr0->num_children();
174 
175  for(int c=0; c<num_children; c++) {
176 
177  SafePtr<DGVertex> child = rr0->child(c);
178  SafePtr<DGArc> arc(new DGArcRel<RR>(tptr,child,rr0));
179  tptr->add_exit_arc(arc);
180 
181  recurse<RR>(child);
182 
183  }
184  }
185  }
186 
193  void apply(const SafePtr<Strategy>& strategy,
194  const SafePtr<Tactic>& tactic);
195 
196  typedef void (DGVertex::* DGVertexMethodPtr)();
199  template <DGVertexMethodPtr method>
200  void apply_at(const SafePtr<DGVertex>& vertex) const {
201  ((vertex.get())->*method)();
202  typedef DGVertex::ArcSetType::const_iterator aciter;
203  const aciter abegin = vertex->first_exit_arc();
204  const aciter aend = vertex->plast_exit_arc();
205  for(aciter a=abegin; a!=aend; ++a)
206  apply_at<method>((*a)->dest());
207  }
208 
210  template <class Method>
211  void foreach(Method& m) {
212  typedef vertices::const_iterator citer;
213  typedef vertices::iterator iter;
214  for(iter v=stack_.begin(); v!=stack_.end(); ++v) {
215  ver_ptr& vptr = vertex_ptr(*v);
216  m(vptr);
217  }
218  }
219 
221  template <class Method>
222  void foreach(Method& m) const {
223  typedef vertices::const_iterator citer;
224  typedef vertices::iterator iter;
225  for(citer v=stack_.begin(); v!=stack_.end(); ++v) {
226  const ver_ptr& vptr = vertex_ptr(*v);
227  m(vptr);
228  }
229  }
231  template <class Method>
232  void rforeach(Method& m) {
233  typedef vertices::const_reverse_iterator criter;
234  typedef vertices::reverse_iterator riter;
235  for(riter v=stack_.rbegin(); v!=stack_.rend(); ++v) {
236  ver_ptr& vptr = vertex_ptr(*v);
237  m(vptr);
238  }
239  }
240 
242  template <class Method>
243  void rforeach(Method& m) const {
244  typedef vertices::const_reverse_iterator criter;
245  typedef vertices::reverse_iterator riter;
246  for(criter v=stack_.rbegin(); v!=stack_.rend(); ++v) {
247  const ver_ptr& vptr = vertex_ptr(*v);
248  m(vptr);
249  }
250  }
251 
256  void optimize_rr_out(const SafePtr<CodeContext>& context);
257 
261  void traverse();
262 
265  void update_func_names();
266 
268  void debug_print_traversal(std::ostream& os) const;
269 
275  void print_to_dot(bool symbols, std::ostream& os = std::cout) const;
276 
285  void generate_code(const SafePtr<CodeContext>& context, const SafePtr<MemoryManager>& memman,
286  const SafePtr<ImplicitDimensions>& dims, const SafePtr<CodeSymbols>& args,
287  const std::string& label,
288  std::ostream& decl, std::ostream& code);
289 
293  void reset();
294 
298  template <class RR>
299  unsigned int
300  num_children_on(const SafePtr<RR>& rr) const {
301  unsigned int nchildren = rr->num_children();
302  unsigned int nchildren_on_stack = 0;
303  for(unsigned int c=0; c<nchildren; c++) {
304  if (!vertex_is_on(rr->rr_child(c)))
305  continue;
306  else
307  nchildren_on_stack++;
308  }
309 
310  return nchildren_on_stack;
311  }
312 
314  SafePtr<GraphRegistry>& registry() { return registry_; }
315  const SafePtr<GraphRegistry>& registry() const { return registry_; }
316 
318  const std::string& label() const { return label_; }
320  void set_label(const std::string& new_label) { label_ = new_label; }
321 
323  bool missing_prerequisites() const;
324 
325  private:
326 
328  vertices stack_;
330  targets targets_;
332  addresses target_accums_;
333 
334  // graph label, used for annotating internal work, e.g. graphviz plots
335  std::string label_;
336 
337  typedef std::map<std::string,bool> FuncNameContainer;
341  FuncNameContainer func_names_;
342 
343 #if !USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH
344  static const unsigned int default_size_ = 100;
345 #endif
346 
347  // maintains data about the graph which does not belong IN the graph
348  SafePtr<GraphRegistry> registry_;
349  // maintains private data about the graph which does not belong IN the graph
350  SafePtr<InternalGraphRegistry> iregistry_;
351 
353  SafePtr<InternalGraphRegistry>& iregistry() { return iregistry_; }
354  const SafePtr<InternalGraphRegistry>& iregistry() const { return iregistry_; }
355 
358  SafePtr<DGVertex> add_vertex(const SafePtr<DGVertex>&);
360  void add_new_vertex(const SafePtr<DGVertex>&);
362  const SafePtr<DGVertex>& vertex_is_on(const SafePtr<DGVertex>& vertex) const;
364  void del_vertex(vertices::iterator&);
368  template <class I, class RR> void recurse(const SafePtr<I>& vertex) {
369  SafePtr<DGVertex> dgvertex = add_vertex(vertex);
370  if (dgvertex != vertex)
371  return;
372 
373  SafePtr<RR> rr0(new RR(vertex));
374  const int num_children = rr0->num_children();
375 
376  for(int c=0; c<num_children; c++) {
377 
378  SafePtr<DGVertex> child = rr0->child(c);
379  SafePtr<DGArc> arc(new DGArcRel<RR>(vertex,child,rr0));
380  vertex->add_exit_arc(arc);
381 
382  SafePtr<I> child_cast = dynamic_pointer_cast<I,DGVertex>(child);
383  if (child_cast == 0)
384  throw std::runtime_error("DirectedGraph::recurse(const SafePtr<I>& vertex) -- dynamic cast failed, most probably this is a logic error!");
385  recurse<I,RR>(child_cast);
386 
387  }
388  }
389 
393  template <class RR> void recurse(const SafePtr<DGVertex>& vertex) {
394  SafePtr<DGVertex> dgvertex = add_vertex(vertex);
395  if (dgvertex != vertex)
396  return;
397 
398  typedef typename RR::TargetType TT;
399  SafePtr<TT> tptr = dynamic_pointer_cast<TT,DGVertex>(vertex);
400  if (tptr == 0)
401  return;
402 
403  SafePtr<RR> rr0(new RR(tptr));
404  const int num_children = rr0->num_children();
405 
406  for(int c=0; c<num_children; c++) {
407 
408  SafePtr<DGVertex> child = rr0->child(c);
409  SafePtr<DGArc> arc(new DGArcRel<RR>(vertex,child,rr0));
410  vertex->add_exit_arc(arc);
411 
412  recurse<RR>(child);
413  }
414  }
415 
419  void apply_to(const SafePtr<DGVertex>& vertex,
420  const SafePtr<Strategy>& strategy,
421  const SafePtr<Tactic>& tactic);
423  SafePtr<DGVertex> insert_expr_at(const SafePtr<DGVertex>& where, const SafePtr< AlgebraicOperator<DGVertex> >& expr);
425  void replace_rr_with_expr();
427  void remove_trivial_arithmetics();
431  void handle_trivial_nodes(const SafePtr<CodeContext>& context);
433  void remove_disconnected_vertices();
437  void find_subtrees();
440  void find_subtrees_from(const SafePtr<DGVertex>& v);
445  bool remove_vertex_at(const SafePtr<DGVertex>& v1, const SafePtr<DGVertex>& v2);
446 
447  // Which vertex is the first to compute
448  SafePtr<DGVertex> first_to_compute_;
449  // prepare_to_traverse must be called before actual traversal
450  void prepare_to_traverse();
451  // traverse_from(arc) build recurively the traversal order
452  void traverse_from(const SafePtr<DGArc>&);
453  // schedule_computation(vertex) puts vertex first in the computation order
454  void schedule_computation(const SafePtr<DGVertex>&);
455 
456  // Compute addresses on stack assuming that quantities larger than min_size_to_alloc to be allocated on stack
457  void allocate_mem(const SafePtr<MemoryManager>& memman,
458  const SafePtr<ImplicitDimensions>& dims,
459  unsigned int min_size_to_alloc = 1);
460  // Assign symbols to the vertices
461  void assign_symbols(const SafePtr<CodeContext>& context, const SafePtr<ImplicitDimensions>& dims);
462  // If v is an AlgebraicOperator, assign (recursively) symbol to the operator. All other must have been already assigned
463  void assign_oper_symbol(const SafePtr<CodeContext>& context, SafePtr<DGVertex>& v);
464  // Print the code using symbols generated with assign_symbols()
465  void print_def(const SafePtr<CodeContext>& context, std::ostream& os,
466  const SafePtr<ImplicitDimensions>& dims,
467  const SafePtr<CodeSymbols>& args);
468 
473  bool cannot_enclose_in_outer_vloop() const;
474 
475  };
476 
477  //
478  // Nonmember utilities
479  //
480 
482  inline const DirectedGraph::ver_ptr& vertex_ptr(const DirectedGraph::VPtrAssociativeContainer::value_type& v) {
483  return v.second;
484  }
485  inline const DirectedGraph::ver_ptr& vertex_ptr(const DirectedGraph::VPtrSequenceContainer::value_type& v) {
486  return v;
487  }
489  inline DirectedGraph::ver_ptr& vertex_ptr(DirectedGraph::VPtrAssociativeContainer::value_type& v) {
490  return v.second;
491  }
492  inline DirectedGraph::ver_ptr& vertex_ptr(DirectedGraph::VPtrSequenceContainer::value_type& v) {
493  return v;
494  }
495 
496 #if USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH
497  inline DirectedGraph::key_type key(const DGVertex& v);
498 #endif
499 
500  //
501  // Nonmember predicates
502  //
503 
505  bool nonunrolled_targets(const DirectedGraph::targets& targets);
506 
508  void extract_symbols(const SafePtr<DirectedGraph>& dg);
509 
510  // use these functors with DirectedGraph::foreach
512  std::deque< SafePtr<DGVertex> > vertices;
513  void operator()(const SafePtr<DGVertex>& v);
514  };
515  struct VertexPrinter {
516  VertexPrinter(std::ostream& ostr) : os(ostr) {}
517  std::ostream& os;
518  void operator()(const SafePtr<DGVertex>& v);
519  };
520 
521 };
522 
523 
524 #endif
bool nonunrolled_targets(const DirectedGraph::targets &targets)
return true if there are non-unrolled targets
Definition: dg.cc:2343
unsigned int num_vertices() const
Returns the number of vertices.
Definition: dg.h:113
void set_label(const std::string &new_label)
sets label to new_label
Definition: dg.h:320
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)
Generates code for the current computation using context.
Definition: dg.cc:1047
bool missing_prerequisites() const
return true if there are vertices with 0 children but not pre-computed
Definition: dg.cc:2310
Type/Instance combination serves as a key to quickly compare 2 polymorphic Singletons.
Definition: key.h:33
void append_target(const SafePtr< DGVertex > &)
non-template append_target appends the vertex to the graph as a target
Definition: dg.cc:75
SafePtr< DGVertex > append_vertex(const SafePtr< DGVertex > &v)
appends v to the graph.
Definition: dg.cc:83
void rforeach(Method &m)
calls Method(v) for each v, iterating in reverse direction
Definition: dg.h:232
CodeContext provides context for generating code.
Definition: context.h:34
Defaults definitions for various parameters assumed by Libint.
Definition: algebra.cc:24
void extract_symbols(const SafePtr< DirectedGraph > &dg)
extracts external symbols and RRs from the graph
Definition: dg.cc:2357
ArcSetType::const_iterator plast_exit_arc() const
returns children::end()
Definition: dgvertex.h:117
void print_to_dot(bool symbols, std::ostream &os=std::cout) const
Prints out the graph in format understood by program "dot" of package "graphviz".
Definition: dg.cc:405
This is a vertex of a Directed Graph (DG)
Definition: dgvertex.h:43
DirectedGraph()
Creates an empty DAG.
Definition: dg.cc:59
Internal registry of information.
Definition: graph_registry.h:89
Strategy specifies how to apply recurrence relations.
Definition: strategy.h:42
void apply_at(const SafePtr< DGVertex > &vertex) const
apply_at<method>(vertex) calls method() on vertex and all of its descendants
Definition: dg.h:200
void update_func_names()
update func_names_
Definition: dg.cc:2180
void traverse()
after all apply's have been called, traverse() construct a heuristic order of traversal for the graph...
Definition: dg.cc:266
const std::string & label() const
return the graph label
Definition: dg.h:318
void apply(const SafePtr< Strategy > &strategy, const SafePtr< Tactic > &tactic)
after all append_target's have been called, apply(strategy,tactic) constructs a graph.
Definition: dg.cc:451
AlgebraicOperator is an algebraic operator that acts on objects of type T.
Definition: algebra.h:48
Class MemoryManager handles allocation and deallocation of raw memory (stack) provided at runtime of ...
Definition: src/bin/libint/memory.h:147
Definition: dg.h:515
void rforeach(Method &m) const
calls Method(v) for each v, iterating in reverse direction
Definition: dg.h:243
unsigned int num_children_on(const SafePtr< RR > &rr) const
num_children_on(rr) returns the number of children of rr which are already on this graph.
Definition: dg.h:300
Tactic is used to choose the optimal (in some sense) recurrence relation to reduce a vertex.
Definition: tactic.h:42
SafePtr< GraphRegistry > & registry()
Returns the registry.
Definition: dg.h:314
Class DGArc describes arcs in a directed graph.
Definition: dgarc.h:34
void append_target(const SafePtr< I > &target)
append_target appends I to the graph as a target vertex and applies RR to it.
Definition: dg.h:145
const DirectedGraph::ver_ptr & vertex_ptr(const DirectedGraph::VPtrAssociativeContainer::value_type &v)
converts what is stored in the container to a smart ptr to the vertex
Definition: dg.h:482
ImplicitDimensions describes basis functions or other "degrees of freedom" not actively engaged in a ...
Definition: dims.h:44
Class CodeSymbols specifies a set of symbols used in a code.
Definition: code.h:34
void debug_print_traversal(std::ostream &os) const
Prints out call sequence.
Definition: dg.cc:358
const SafePtr< DGVertex > & find(const SafePtr< DGVertex > &v) const
Find vertex v or it's equivalent on the graph.
Definition: dg.h:122
const vertices & all_vertices() const
Returns all vertices.
Definition: dg.h:116
Externally accessible registry of information about a graph.
Definition: graph_registry.h:36
Class DGArcRel describes arcs in a directed graph which is represented by a relationship ArcRel.
Definition: dg.h:44
DirectedGraph is an implementation of a directed graph composed of vertices represented by DGVertex o...
Definition: dg.h:63
const targets & all_targets() const
Returns all targets.
Definition: dg.h:118
void reset()
Resets the graph and all vertices.
Definition: dg.cc:433
void apply_to_all()
apply_to_all applies RR to all vertices already on the graph.
Definition: dg.h:160
ArcSetType::const_iterator first_exit_arc() const
returns children::begin()
Definition: dgvertex.h:115
void optimize_rr_out(const SafePtr< CodeContext > &context)
after Strategy has been applied, simple recurrence relations need to be optimized away.
Definition: dg.cc:523