DAG.h

00001 /***************************************************************************
00002  *   Copyright (C) 2009 by Touati Sid                                      *
00003  *   Sid-nospam.Touati-nospam@univ-cotedazur.fr                                      *
00004  *   Copyright  INRIA and the University of Versailles                     *
00005  *   This program is free software; you can redistribute it and/or modify  *
00006  *   it under the terms of the GNU General Public License as published by  *
00007  *   the Free Software Foundation; either version 2 of the License, or     *
00008  *   (at your option) any later version.                                   *
00009  *                                                                         *
00010  *   This program is distributed in the hope that it will be useful,       *
00011  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
00012  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
00013  *   GNU General Public License for more details.                          *
00014  *                                                                         *
00015  *   You should have received a copy of the GNU Library General Public     *
00016  *   License along with this program (LGPL); if not, write to the          *
00017  *   Free Software Foundation, Inc.,                                       *
00018  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
00019  *   Exception : this software requires a licence  of the LEDA libary.     *
00020  *   If you are from academia, you can get a free leda binary licence 
00021  *   allowing you to use freely our DDG library.                           *
00022  *   Otherwise, you can buy a LEDA licence from algorithmic-solutions      *
00023  *   http://www.algorithmic-solutions.com                                  *
00024  *   LEDA binaries and source codes are excluded from this LGPL.           *
00025  *   Obtaining a LEDA licence is not mandatory to use our GPL software     *
00026  *   If the user wants, he can  create a free source-compatible replacement*
00027  *   for LEDA, and he is allowed to use our software under LGPL.           *
00028  ***************************************************************************/
00029 
00030 
00031 
00032 #ifndef __DAG_H
00033 #define __DAG_H
00034 
00055 #ifndef MAX_NODE
00056 #define MAX_NODE 10001
00057 #endif 
00058 
00059 
00060 
00061 
00062 #include <string> 
00063 #include <iostream>
00064 #include <fstream>
00065 #include "LEDA/graph/graph.h" /* GRAPH, string */
00066 #include "LEDA/core/set.h"
00067 #include "LEDA/graph/node_set.h"
00068 #include "LEDA/graph/node_array.h"
00069 #include "LEDA/graph/node_matrix.h" /* GRAPH, string */
00070 #include "LEDA/core/array.h"
00071 #include "LEDA/graph/node_list.h"
00072 #include "LEDA/core/d_array.h"
00073 #include "LEDA/graph/mcb_matching.h" /* bipartie matching algorithm */
00074 #include "LEDA/graph/basic_graph_alg.h" /* transitive closure */
00075 #include <LEDA/core/map2.h>
00076 #include "ddg_exceptions.h"
00077 #include "architecture.h"
00078 #include "info_edge.h"
00079 #include "info_node.h"
00080 
00081 #ifndef MAX_STRING
00082 #define MAX_STRING 1000
00083 #endif
00084 
00093 using namespace std;
00094 using namespace LEDA;
00095 namespace DDG{
00096 
00097 
00106 template<class T> LEDA::set<T> list_to_set(const LEDA::list<T> l);
00107 
00114 template<class T> LEDA::list<T> set_to_list(const set<T> l) ;
00115 
00116 template<class T> set<T> list_to_set(const list<T> l) {
00117     T m;
00118     set<T> tmp;
00119     forall(m , l){tmp.insert(m);}
00120     return tmp;
00121 }
00122 
00123 template<class T> list<T> set_to_list(const set<T> l) {
00124     T m;
00125     list<T> tmp;
00126     forall(m , l){tmp.append(m);}
00127     return tmp;
00128 }
00129 
00130 
00138 bool lt(node u, node v);
00139 
00140 
00150 bool le(node u, node v);
00151 
00152 
00162 bool gt(node u, node v);
00163 
00164 
00174 bool ge(node u, node v);
00175 
00183 bool parallel(node u, node v);
00184 
00194 bool comparable(node u, node v);
00195 
00203 int compare_nodes(const node &u, const node &v);
00204 
00205 
00206 
00207 class INFO_NODE;
00208 class INFO_EDGE;
00209 class DAG;
00210 class LOOP;
00211 
00212 
00213 
00214 
00215 
00216 
00227 class DAG: public GRAPH <INFO_NODE, INFO_EDGE>
00228 {
00229     protected:
00230         unsigned int cpt_nodes; // a counter incremented each new node (but never decremented). Used for assigning a unique identifier per node.
00231     
00232     
00233     /*useful sets*/
00234     LEDA::d_array<int, LEDA::set<node> > V_R; /* set V_R,t: set of values in G for each register type */
00235     LEDA::d_array<int, LEDA::set<edge> > E_R; /* The set of flow edges through registers for each register type */
00236     
00237     ARCHITECTURE ISA;
00238     
00239     
00240     node_array<set<node> > down;
00241     node_array<set<node> > up;
00242     node_array<int> longuest_path_from;
00243     node_array<int> longuest_path_to;
00244     node_matrix<int> lp_array; /* lp_array(u,v)=lp(u,v) */
00245     /*shortest path to and from a node */
00246     node_array<int> shortest_path_from;
00247     node_array<int> shortest_path_to;
00248     /* sources and targets of a node */
00249     set<node> Sources; /* sources of the DAG */
00250     set<node> Targets; /* leaf of the DAG */
00251     map2<node, int, set<node> > Cons; /* consumer set of a value of a given register type Cons[u,t] */
00252     LEDA::map<int,node> node_index_table; //save the id of each node : node_index_table[u] is the id of the node u
00253  public:
00254      
00262      DAG(); 
00263      
00268     DAG(const ARCHITECTURE); 
00269     
00270     ~DAG();
00272     
00276     LEDA::set<edge> edges_from_to(node u, node v) const;
00277     
00282     LEDA::set<edge> edges_from_to(int id_u, int id_v) const;
00283 
00285     int LongestPath() const ;
00286  
00291     int LongestPath(LEDA::list<node> &nl) const;
00292     
00297     int LongestPath(list<edge> &el) const;
00298   
00300     int CriticalPath();
00301     
00306     int CriticalPath(LEDA::list<node> &nl);
00307                           
00308 
00313     int CriticalPath(LEDA::list<edge> &el);
00314     
00316     int LongestPathTo(node) const;
00317     
00319     int LongestPathFrom(node) const ;
00320     
00322     int ShortestPathTo(node) const;
00323     
00325     int ShortestPathFrom(node) const;
00326     
00330     int lp(node u, node v) const ;
00331     
00333     LEDA::set<node> get_down(node u) const;
00334     
00336     LEDA::set<node> get_up(node u) const;
00337   
00338     
00340     LEDA::set<node> get_parents(node u) const;
00341     
00344     LEDA::set<node> get_children(const node u) const;
00345            
00349     node node_with_id(int i) const;
00350 
00354     node node_with_name(std::string name) const;
00355     
00360     bool is_value(node n) const; 
00361            
00364     bool is_value(int i, int t)const ;
00365            
00368     bool is_value(node n, int t) const; 
00369        
00374     bool is_value(int i)const ;
00375     
00377     bool is_flow(edge e) const {INFO_EDGE ie=inf(e); return ie.is_flow(); }
00378 
00383     bool is_flow_reg(edge e) const {
00384     INFO_EDGE ie=inf(e);                         
00385     return ie.is_flow_reg(ISA.get_the_unique_register_type_id());
00386     }
00387     
00392     int get_register_type_id(edge e) const;
00393     
00395     bool is_flow_reg(edge e, int t) const {
00396     INFO_EDGE ie=inf(e);                         
00397     return ie.is_flow_reg(t);
00398     }
00399            
00401     DDG::edge_type etype(edge e)const ;
00402 
00403            
00408     set<node> get_V_R() const
00409     {return V_R[ISA.get_the_unique_register_type_id()];}
00410     
00414     set<node> get_V_R(int t) const
00415     {
00416         if (ISA.exist_register_type_id(t))
00417             return V_R[t];
00418         else throw BadRegType();
00419     }
00420     
00421     LEDA::list<REGISTER_TYPES> T() const ;
00426     LEDA::set<edge> get_E_R() const
00427     {return E_R[ISA.get_the_unique_register_type_id()];}
00428     
00432     LEDA::set<edge> get_E_R(int t) const
00433     {
00434         if (ISA.exist_register_type_id(t))
00435             return E_R[t];
00436         else throw BadRegType();
00437     }
00438     
00440     LEDA::set<node>  get_Sources() const;
00441     
00443     LEDA::set<node>  get_Targets()const ;
00444 
00450     LEDA::set<node>  get_Cons(node u) const{
00451         return Cons(u, ISA.get_the_unique_register_type_id());
00452     }
00453     
00458     LEDA::set<node>  get_Cons(node u, int id_regtype) const{
00459         if (ISA.exist_register_type_id(id_regtype))
00460             return Cons(u, id_regtype);
00461         else throw BadRegType();
00462     }
00463     
00464     
00466     LEDA::set<int >  get_Sources_id() const;
00467     
00469      LEDA::set<int >  get_Targets_id() const;
00470     
00472      LEDA::set<int> all_nodes_id();
00473              
00474 
00478         int source_id(edge e) const
00479         {
00480         return id(source(e));
00481         }
00482 
00483     
00484 
00487         int target_id(edge e) const
00488         {
00489         return id(target(e));
00490         }
00491     
00492     
00494     ARCHITECTURE get_ISA() const
00495     {
00496         return ISA;
00497     }
00498 
00499 
00503     int delta(edge e) const;
00504 
00505 
00509     int latency (node n) const ;
00510 
00514     int delta_r (node n) const;
00515     
00519     int delta_r (int idn) const;
00520     
00525     int delta_w (node n) const;
00526 
00531     int delta_w (int idn) const;
00532     
00536     int delta_w (node n, int regtype_id) const;
00537 
00541     int delta_w (int idn, int regtype_id) const;
00542      
00545         int id(node n) const
00546         {
00547         INFO_NODE in=inf(n);
00548         return in.id();
00549         }
00550 
00554     INSTRUCTIONS_TYPES instruction_type(node n)  const;
00555 
00556 
00560     INSTRUCTIONS_TYPES instruction_type(int id)  const;
00561     
00563     std::string get_string_attribute(node n) const;
00564 
00565     /* ------------------ Some LEDA methos ------------------- */
00567     const INFO_NODE& inf(node v) const { return LEDA_CONST_ACCESS(INFO_NODE,graph::inf(v));}
00568 
00570     const INFO_NODE& operator[] (node v) const
00571     { return inf(v);     }
00572 
00573     INFO_NODE& operator[] (node v)
00574     { return LEDA_ACCESS(INFO_NODE,entry(v));}
00575     
00577     const INFO_EDGE& inf(edge e) const
00578     { return LEDA_CONST_ACCESS(INFO_EDGE,graph::inf(e));}
00579 
00581     const INFO_EDGE& operator[] (edge e) const
00582     { return inf(e);                      }
00583     INFO_EDGE&       operator[] (edge e)
00584     { return LEDA_ACCESS(INFO_EDGE, entry(e)); }
00585 
00587     int  outdeg(node v)    const
00588     {return GRAPH<INFO_NODE,INFO_EDGE>::outdeg(v);}
00589 
00591     int  indeg(node v)     const
00592     {return GRAPH<INFO_NODE,INFO_EDGE>::indeg(v);}
00593 
00595     int  degree(node v)    const {return (
00596     GRAPH<INFO_NODE,INFO_EDGE>::indeg(v) +
00597     GRAPH<INFO_NODE,INFO_EDGE>::outdeg(v));}
00598 
00600     node source(edge e)    const
00601     {return GRAPH<INFO_NODE,INFO_EDGE>::source(e);}
00602 
00604     node target(edge e)    const
00605     {return GRAPH<INFO_NODE,INFO_EDGE>::target(e);}
00606 
00608     node opposite(node v, edge e) const
00609     {return GRAPH<INFO_NODE,INFO_EDGE>::opposite(v,e);}
00610 
00612     node opposite(edge e, node v) const
00613     {return GRAPH<INFO_NODE,INFO_EDGE>::opposite(e,v);}
00614 
00616     int  number_of_nodes() const
00617     {return GRAPH<INFO_NODE,INFO_EDGE>::number_of_nodes();}
00618 
00620     int  number_of_edges() const
00621     {return GRAPH<INFO_NODE,INFO_EDGE>::number_of_edges();}
00622 
00624     const LEDA::list<node>& all_nodes()  const
00625     {return GRAPH<INFO_NODE,INFO_EDGE>::all_nodes();}
00626 
00628     const LEDA::list<edge>& all_edges()  const
00629     {return GRAPH<INFO_NODE,INFO_EDGE>::all_edges();}
00630 
00631 
00633     LEDA::list<edge> out_edges(node v) const
00634     {return GRAPH<INFO_NODE,INFO_EDGE>::out_edges(v);}
00635 
00637     LEDA::list<edge> in_edges(node v) const
00638     {return GRAPH<INFO_NODE,INFO_EDGE>::in_edges(v);}
00639 
00640 
00642     node first_node()      const
00643     {return GRAPH<INFO_NODE,INFO_EDGE>::first_node();}
00644 
00646     node last_node()      const
00647     {return GRAPH<INFO_NODE,INFO_EDGE>::last_node();}
00648 
00650     node choose_node()     const
00651     {return GRAPH<INFO_NODE,INFO_EDGE>::choose_node();}
00652 
00654     node succ_node(node v) const
00655     {return GRAPH<INFO_NODE,INFO_EDGE>::succ_node(v);}
00656     
00658     node pred_node(node v) const
00659     {return GRAPH<INFO_NODE,INFO_EDGE>::pred_node(v);}
00660 
00662     edge first_edge()      const
00663     {return GRAPH<INFO_NODE,INFO_EDGE>::first_edge();}
00664 
00666     edge last_edge()      const
00667     {return GRAPH<INFO_NODE,INFO_EDGE>::last_edge();}
00668 
00670     edge choose_edge()     const
00671     {return GRAPH<INFO_NODE,INFO_EDGE>::choose_edge();}
00672 
00674     edge succ_edge(edge e) const
00675     {return GRAPH<INFO_NODE,INFO_EDGE>::succ_edge(e);}
00676 
00678     edge pred_edge(edge e) const
00679     {return GRAPH<INFO_NODE,INFO_EDGE>::pred_edge(e);}
00680 
00682     bool empty() const
00683     { return GRAPH<INFO_NODE,INFO_EDGE>::empty(); }
00684 
00686     bool   member(node v) const
00687     { return GRAPH<INFO_NODE,INFO_EDGE>::member(v); }
00688 
00690     bool   member(edge e) const
00691     { return  GRAPH<INFO_NODE,INFO_EDGE>::member(e); }
00692     
00696     bool is_hidden(edge e) const
00697     { return GRAPH<INFO_NODE, INFO_EDGE>::is_hidden(e); }
00698 
00702     bool is_hidden(node v) const
00703     { return GRAPH<INFO_NODE, INFO_EDGE>::is_hidden(v); }
00704 
00706     LEDA::list<edge> hidden_edges() const
00707     {return GRAPH<INFO_NODE, INFO_EDGE>::hidden_edges();}
00708 
00710     LEDA::list<node> hidden_nodes() const
00711     {return GRAPH<INFO_NODE, INFO_EDGE>::hidden_nodes();}
00712 
00714     int max_delta(node u, node v) const;
00715 
00717     int max_delta(int u, int v) const
00718     {return max_delta(node_with_id(u),node_with_id(v));}
00719 
00721     int min_delta(node u, node v) const;
00722     
00724     int min_delta(int u, int v) const
00725     {return min_delta(node_with_id(u),node_with_id(v));}
00726 
00728     INSTRUCTIONS_TYPES search_instruction_type(const std::string  opcode) const;
00729 
00731     INSTRUCTIONS_TYPES search_instruction_type(int opcode_id) const;
00732     
00734     bool check();
00736     bool check(int regtype_id);
00737     
00739     NodeFlag node_flag ( node n) const;
00740     
00744 
00747 
00749 
00758 
00769 
00783 
00798 
00804 
00812 
00822 
00832 
00835 
00843 
00853 
00863 
00871 
00879 
00886 
00893 
00897 
00905 
00911 
00919 
00924 
00929 
00934 
00939 
00946 
00951 
00960 
00965 
00968 
00976 
00980 
00983 
00985 
00989 
00995 
01002 
01017 
01033 
01040 
01048 
01054 
01058 
01067 
01085 
01098 
01111 
01126 
01142 
01157 
01172