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