loop.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 
00046 #ifndef DDGLOOP_H
00047 #define DDGLOOP_H
00048 
00049 #include "DAG.h"
00050 
00051 #include "LEDA/numbers/rational.h"
00057 #define Min(X,Y) X<Y ? X:Y
00058 
00059 
00060 using namespace LEDA;
00061 namespace DDG {
00071 class LOOP: public DAG
00072 {
00073     protected:
00074     
00075     /* internal functions for critical cycles */
00076     bool FLOYD(GRAPH<INFO_NODE, INFO_EDGE>&, node_matrix<double>&) const;
00077     double  MIN_CYCLE(GRAPH<INFO_NODE, INFO_EDGE>& ) const;
00078     double PREPARE_CRITICAL_CYCLE(GRAPH<INFO_NODE, INFO_EDGE>&, const LOOP&) const;
00079     double NEGATVE_CYCLE(GRAPH<INFO_NODE, INFO_EDGE>& , LEDA::list<edge>& negcycle_arcs) const;
00080     edge  theEdge(int source, int dest, int dist) const;  
00081     
00082     
00083     public:
00089     LOOP();
00090       
00091      void clear();
00092          
00097     LOOP(ARCHITECTURE isa);
00098     ~LOOP();
00100         
00104     int MaxLambda() const;
00105     
00107     int MinLambda() const;
00108         
00111     LEDA::set<edge> flow_from_to(node u, node v) const;
00112     
00116     LEDA::set<edge> flow_from_to(int id_u, int id_v) const;
00117 
00118 
00123     LEDA::set<edge> flow_reg_from_to(node u, node v) const;
00124 
00131     LEDA::set<edge> flow_reg_from_to(int id_u, int id_v) const;
00132     
00136     LEDA::set<edge> flow_reg_from_to(node u, node v, int t) const;
00137 
00143     LEDA::set<edge> flow_reg_from_to(int id_u, int id_v, int t) const;
00144     
00145 
00149     int max_dist(node u, node v) const;
00150 
00156     int max_dist(int id_u, int id_v) const;
00157         
00161     int max_flow_dist(node u, node v) const;
00162         
00168     int max_flow_dist(int id_u, int id_v) const;
00169         
00170     
00176     int max_flow_reg_dist(node u, node v) const;
00177     
00185     int max_flow_reg_dist(int id_u, int id_v) const;
00186     
00191     int max_flow_reg_dist(node u, node v, int t) const;
00192     
00200     int max_flow_reg_dist(int id_u, int id_v, int t) const; 
00201 
00205     int min_dist(node u, node v) const;
00206     
00212     int min_dist(int id_u, int id_v) const;
00213     
00218     int min_flow_dist(node u, node v) const;
00219     
00225     int min_flow_dist(int id_u, int id_v) const;
00226 
00230     int min_flow_reg_dist(node u, node v) const;
00231     
00237     int min_flow_reg_dist(int id_u, int id_v) const;
00238     
00242     int min_flow_reg_dist(node u, node v, int t) const;
00243     
00250     int min_flow_reg_dist(int id_u, int id_v, int t) const;
00251                
00261     LEDA::rational CRITICAL_CYCLE() const;
00262         
00274     LEDA::rational CRITICAL_CYCLE(LEDA::list<edge> &el) const;
00275     
00276         
00278     int lambda(edge e) const;   
00279                       
00281                
00284     
00288     void copy(const LOOP &G2);
00289         
00297        void copy(const LOOP& G2, node_map<node> &mn, edge_map<edge> &me);
00298         
00299     
00300         
00301                
00307     void build_internal_structures();
00308         
00309         
00310 
00311     
00312     
00313 
00314 
00315         
00317     void set_lambda(edge e, int l);
00318 
00319          
00320     
00321 
00323 
00325         
00331     void write_to_vcg(const char *filename) const;
00332 
00339     void write_to_vcg(const char *filename, int t) const;
00340 
00344     void write_to_gl(const char *filename) const;
00345     
00350     void write_to_gl(const char *filename, int regtype_id) const;
00351         
00362     bool read_from_gl(const char *filename, int regtype_id);
00363     
00364     
00375     bool read_from_gl(const char *filename);
00376 
00379     void write_to_xml(const char *filename) const;
00380     
00384     bool read_from_xml(const char *filename);
00385         bool check();
00386     bool check(int regtype_id);
00387     
00389     
00390 };
00391 
00392 /* Some nice loop manipulation functions. */
00393 
00405 void unroll(const LOOP& L, DAG &unrolled, int unroll_degree);
00406 
00418 void unroll(const LOOP& L, LOOP &unrolled, int unroll_degree);
00419 
00420 
00428 void loop_merge(const LOOP &L1, const LOOP &L2, LOOP &L3);
00429 
00443 bool retime_ddg(LOOP &G, LEDA::node_array<int> &r);
00444 
00458 bool retime_ddg(LOOP &G);
00459 
00474 bool apply_retiming(LOOP &G, const LEDA::node_array<int> r);
00475 
00476 
00477 
00490 bool is_lexicographic_positive( LOOP &G,  edge &e);
00491 
00503 bool is_lexicographic_positive( LOOP &G,  leda::list<edge>  &le);
00504 
00505 }
00506 
00507 
00508 #endif