21 #ifndef _libint2_src_bin_libint_dg_h_ 22 #define _libint2_src_bin_libint_dg_h_ 34 #include <global_macros.h> 35 #include <exception.h> 36 #include <smart_ptr.h> 67 typedef SafePtr<DGVertex> ver_ptr;
68 typedef SafePtr<DGArc> arc_ptr;
70 typedef std::multimap<key_type,ver_ptr> VPtrAssociativeContainer;
71 typedef std::list<ver_ptr> VPtrSequenceContainer;
73 typedef VPtrSequenceContainer targets;
74 #if USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH 75 typedef VPtrAssociativeContainer vertices;
77 typedef VPtrSequenceContainer vertices;
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;
86 typedef unsigned int size;
87 typedef std::vector<address> addresses;
91 static inline const ver_ptr& vertex_ptr(
const VPtrAssociativeContainer::value_type& v) {
94 static inline const ver_ptr& vertex_ptr(
const VPtrSequenceContainer::value_type& v) {
98 static inline ver_ptr& vertex_ptr(VPtrAssociativeContainer::value_type& v) {
101 static inline ver_ptr& vertex_ptr(VPtrSequenceContainer::value_type& v) {
120 const SafePtr<DGVertex>&
find(
const SafePtr<DGVertex>& v)
const {
return vertex_is_on(v); }
146 target->make_a_target();
147 recurse<I,RR>(target);
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)
168 SafePtr<TT> tptr = dynamic_pointer_cast<TT,DGVertex>(v);
172 SafePtr<RR> rr0(
new RR(tptr));
173 const int num_children = rr0->num_children();
175 for(
int c=0; c<num_children; c++) {
177 SafePtr<DGVertex> child = rr0->child(c);
179 tptr->add_exit_arc(
arc);
193 void apply(
const SafePtr<Strategy>& strategy,
194 const SafePtr<Tactic>& tactic);
196 typedef void (
DGVertex::* DGVertexMethodPtr)();
199 template <DGVertexMethodPtr method>
201 ((
vertex.get())->*method)();
202 typedef DGVertex::ArcSetType::const_iterator aciter;
205 for(aciter a=abegin; a!=aend; ++a)
206 apply_at<method>((*a)->dest());
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);
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);
231 template <
class Method>
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);
242 template <
class Method>
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);
275 void print_to_dot(
bool symbols, std::ostream& os = std::cout)
const;
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);
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)))
307 nchildren_on_stack++;
310 return nchildren_on_stack;
314 SafePtr<GraphRegistry>&
registry() {
return registry_; }
315 const SafePtr<GraphRegistry>&
registry()
const {
return registry_; }
318 const std::string&
label()
const {
return label_; }
320 void set_label(
const std::string& new_label) { label_ = new_label; }
332 addresses target_accums_;
337 typedef std::map<std::string,bool> FuncNameContainer;
341 FuncNameContainer func_names_;
343 #if !USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH 344 static const unsigned int default_size_ = 100;
348 SafePtr<GraphRegistry> registry_;
350 SafePtr<InternalGraphRegistry> iregistry_;
353 SafePtr<InternalGraphRegistry>& iregistry() {
return iregistry_; }
354 const SafePtr<InternalGraphRegistry>& iregistry()
const {
return iregistry_; }
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)
373 SafePtr<RR> rr0(
new RR(vertex));
374 const int num_children = rr0->num_children();
376 for(
int c=0; c<num_children; c++) {
378 SafePtr<DGVertex> child = rr0->child(c);
379 SafePtr<DGArc> arc(
new DGArcRel<RR>(vertex,child,rr0));
380 vertex->add_exit_arc(arc);
382 SafePtr<I> child_cast = dynamic_pointer_cast<I,DGVertex>(child);
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);
393 template <
class RR>
void recurse(
const SafePtr<DGVertex>& vertex) {
394 SafePtr<DGVertex> dgvertex = add_vertex(vertex);
395 if (dgvertex != vertex)
398 typedef typename RR::TargetType TT;
399 SafePtr<TT> tptr = dynamic_pointer_cast<TT,DGVertex>(vertex);
403 SafePtr<RR> rr0(
new RR(tptr));
404 const int num_children = rr0->num_children();
406 for(
int c=0; c<num_children; c++) {
408 SafePtr<DGVertex> child = rr0->child(c);
409 SafePtr<DGArc> arc(
new DGArcRel<RR>(vertex,child,rr0));
410 vertex->add_exit_arc(arc);
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);
448 SafePtr<DGVertex> first_to_compute_;
450 void prepare_to_traverse();
452 void traverse_from(
const SafePtr<DGArc>&);
454 void schedule_computation(
const SafePtr<DGVertex>&);
457 void allocate_mem(
const SafePtr<MemoryManager>& memman,
458 const SafePtr<ImplicitDimensions>& dims,
459 unsigned int min_size_to_alloc = 1);
461 void assign_symbols(
const SafePtr<CodeContext>& context,
const SafePtr<ImplicitDimensions>& dims);
463 void assign_oper_symbol(
const SafePtr<CodeContext>& context, SafePtr<DGVertex>& v);
465 void print_def(
const SafePtr<CodeContext>& context, std::ostream& os,
466 const SafePtr<ImplicitDimensions>& dims,
467 const SafePtr<CodeSymbols>& args);
473 bool cannot_enclose_in_outer_vloop()
const;
482 inline const DirectedGraph::ver_ptr&
vertex_ptr(
const DirectedGraph::VPtrAssociativeContainer::value_type& v) {
485 inline const DirectedGraph::ver_ptr&
vertex_ptr(
const DirectedGraph::VPtrSequenceContainer::value_type& v) {
489 inline DirectedGraph::ver_ptr&
vertex_ptr(DirectedGraph::VPtrAssociativeContainer::value_type& v) {
492 inline DirectedGraph::ver_ptr&
vertex_ptr(DirectedGraph::VPtrSequenceContainer::value_type& v) {
496 #if USE_ASSOCCONTAINER_BASED_DIRECTEDGRAPH 497 inline DirectedGraph::key_type key(
const DGVertex& v);
512 std::deque< SafePtr<DGVertex> > vertices;
513 void operator()(
const SafePtr<DGVertex>& v);
518 void operator()(
const SafePtr<DGVertex>& v);
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
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