20 #ifndef _libint2_src_bin_libint_dg_h_ 21 #define _libint2_src_bin_libint_dg_h_ 33 #include <global_macros.h> 34 #include <exception.h> 35 #include <smart_ptr.h> 66 typedef SafePtr<DGVertex> ver_ptr;
67 typedef SafePtr<DGArc> arc_ptr;
69 typedef std::multimap<key_type,ver_ptr> VPtrAssociativeContainer;
70 typedef std::list<ver_ptr> VPtrSequenceContainer;
72 typedef VPtrSequenceContainer targets;
73 #if USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH 74 typedef VPtrAssociativeContainer vertices;
76 typedef VPtrSequenceContainer vertices;
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;
85 typedef unsigned int size;
86 typedef std::vector<address> addresses;
90 static inline const ver_ptr& vertex_ptr(
const VPtrAssociativeContainer::value_type& v) {
93 static inline const ver_ptr& vertex_ptr(
const VPtrSequenceContainer::value_type& v) {
97 static inline ver_ptr& vertex_ptr(VPtrAssociativeContainer::value_type& v) {
100 static inline ver_ptr& vertex_ptr(VPtrSequenceContainer::value_type& v) {
119 const SafePtr<DGVertex>&
find(
const SafePtr<DGVertex>& v)
const {
return vertex_is_on(v); }
145 target->make_a_target();
146 recurse<I,RR>(target);
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)
167 SafePtr<TT> tptr = dynamic_pointer_cast<TT,
DGVertex>(v);
171 SafePtr<RR> rr0(
new RR(tptr));
172 const int num_children = rr0->num_children();
174 for(
int c=0; c<num_children; c++) {
176 SafePtr<DGVertex> child = rr0->child(c);
178 tptr->add_exit_arc(arc);
192 void apply(
const SafePtr<Strategy>& strategy,
193 const SafePtr<Tactic>& tactic);
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());
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);
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);
230 template <
class Method>
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);
241 template <
class Method>
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);
274 void print_to_dot(
bool symbols, std::ostream& os = std::cout)
const;
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);
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)))
306 nchildren_on_stack++;
309 return nchildren_on_stack;
313 SafePtr<GraphRegistry>&
registry() {
return registry_; }
314 const SafePtr<GraphRegistry>&
registry()
const {
return registry_; }
317 const std::string&
label()
const {
return label_; }
319 void set_label(
const std::string& new_label) { label_ = new_label; }
331 addresses target_accums_;
336 typedef std::map<std::string,bool> FuncNameContainer;
340 FuncNameContainer func_names_;
342 #if !USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH 343 static const unsigned int default_size_ = 100;
347 SafePtr<GraphRegistry> registry_;
349 SafePtr<InternalGraphRegistry> iregistry_;
352 SafePtr<InternalGraphRegistry>& iregistry() {
return iregistry_; }
353 const SafePtr<InternalGraphRegistry>& iregistry()
const {
return iregistry_; }
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)
372 SafePtr<RR> rr0(
new RR(vertex));
373 const int num_children = rr0->num_children();
375 for(
int c=0; c<num_children; c++) {
377 SafePtr<DGVertex> child = rr0->child(c);
379 vertex->add_exit_arc(arc);
381 SafePtr<I> child_cast = dynamic_pointer_cast<I,
DGVertex>(child);
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);
392 template <
class RR>
void recurse(
const SafePtr<DGVertex>& vertex) {
393 SafePtr<DGVertex> dgvertex = add_vertex(vertex);
394 if (dgvertex != vertex)
397 typedef typename RR::TargetType TT;
398 SafePtr<TT> tptr = dynamic_pointer_cast<TT,
DGVertex>(vertex);
402 SafePtr<RR> rr0(
new RR(tptr));
403 const int num_children = rr0->num_children();
405 for(
int c=0; c<num_children; c++) {
407 SafePtr<DGVertex> child = rr0->child(c);
409 vertex->add_exit_arc(arc);
418 void apply_to(
const SafePtr<DGVertex>& vertex,
419 const SafePtr<Strategy>& strategy,
420 const SafePtr<Tactic>& tactic);
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);
447 SafePtr<DGVertex> first_to_compute_;
449 void prepare_to_traverse();
451 void traverse_from(
const SafePtr<DGArc>&);
453 void schedule_computation(
const SafePtr<DGVertex>&);
456 void allocate_mem(
const SafePtr<MemoryManager>& memman,
457 const SafePtr<ImplicitDimensions>& dims,
458 unsigned int min_size_to_alloc = 1);
460 void assign_symbols(
const SafePtr<CodeContext>& context,
const SafePtr<ImplicitDimensions>& dims);
462 void assign_oper_symbol(
const SafePtr<CodeContext>& context, SafePtr<DGVertex>& v);
464 void print_def(
const SafePtr<CodeContext>& context, std::ostream& os,
465 const SafePtr<ImplicitDimensions>& dims,
466 const SafePtr<CodeSymbols>& args);
472 bool cannot_enclose_in_outer_vloop()
const;
481 inline const DirectedGraph::ver_ptr& vertex_ptr(
const DirectedGraph::VPtrAssociativeContainer::value_type& v) {
484 inline const DirectedGraph::ver_ptr& vertex_ptr(
const DirectedGraph::VPtrSequenceContainer::value_type& v) {
488 inline DirectedGraph::ver_ptr& vertex_ptr(DirectedGraph::VPtrAssociativeContainer::value_type& v) {
491 inline DirectedGraph::ver_ptr& vertex_ptr(DirectedGraph::VPtrSequenceContainer::value_type& v) {
495 #if USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH 511 std::deque< SafePtr<DGVertex> > vertices;
512 void operator()(
const SafePtr<DGVertex>& v);
517 void operator()(
const SafePtr<DGVertex>& v);
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'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'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'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
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