loop_example.cpp

This is an example of how to use the LOOP class.

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  ***************************************************************************/
00032 #include "DDG.h" // the header file of the DDG library. To be included by the user.
00033 
00034 #include <iostream>
00035 #include <cstdlib>
00036 
00037 
00038 using namespace std;
00039 using namespace DDG; // the namespace of the DDG library.
00040 
00041 
00042 
00043 int main(int argc, char *argv[])
00044 {
00045     //int are always usefull
00046     int         i,j ;
00047     int c; // for getopt
00048     // some strings for file names
00049     ARCHITECTURE isa_arch;
00050     
00051     char        str[MAX_STRING];
00052     char        *ddg_filename=NULL, *arch_filename=NULL;
00053     LEDA::list<REGISTER_TYPES> T;
00054     REGISTER_TYPES rt;
00055     // some objects for graphs
00056     //declare a DDG of a loop (cyclic data dependence graph)
00057     DDG::LOOP loop, unrolled, loop_copy;
00058     ARCHITECTURE isa_example;
00059 
00060     LEDA::node n,u;
00061     LEDA::edge e;
00062     set<node> VR;
00063     set<edge> ER;
00064     DDG::INFO_EDGE ie; //information attached to a given edge
00065 
00066     INSTRUCTIONS_TYPES it; // information attached to an opcode
00067     LEDA::list<edge> el; // a list of edges
00068     
00069     while ((c = getopt (argc, argv, "i:a:")) != -1){
00070         switch(c){
00071             case 'a': arch_filename=optarg;
00072                 break;
00073             case 'i': ddg_filename =optarg;
00074                 break;
00075             case '?': 
00076                 cout<<"usage:"<< argv[0] <<" -i ddg_filename.xml [-a isa_desc.xml] "<<endl;
00077                 return EXIT_FAILURE;
00078         }
00079         
00080     }
00081     
00082     if (arch_filename!=NULL)  { 
00083         isa_example.read_from_xml(arch_filename);
00084         if(isa_example.check()){
00085             loop=LOOP(isa_example);  //build an empty DDG loop with a user defined architcural (ISA) description
00086         } else return EXIT_FAILURE;
00087         
00088     } 
00089      //---- The user can read a DDG from an xml format defined by the DDG library
00090     if (ddg_filename != NULL){
00091         i=loop.read_from_xml(ddg_filename); // reads the DDG loop from an xml file
00092         if(i==-1) return EXIT_FAILURE;
00093 
00094     }
00095     else{
00096         cout<<"usage:"<< argv[0] <<" -i ddg_filename.xml [-a isa_desc.xml] "<<endl;
00097         return EXIT_FAILURE;
00098     }
00099 
00100     
00101 
00102      
00103      // The user can modify the DDG by many other methods
00104     // : new_node, new_edge, clear, del_node, del_edge, etc.
00105      // The user can access any information about nodes, edges,
00106     // apply well known algorithms using the LEDA library
00107      // See the LEDA manual : http://www.algorithmic-solutions.info/leda_manual
00108      // See the DDG user manual inside this distribution
00109     
00110     cout<< "DDG example program: " <<ddg_filename<<endl;
00111     cout<< "------------------------------" <<endl;
00112     // ------------------- The user can compute the critical path ---------------
00113     // Null circuits are accepted inside the DDG and detected
00114     cout<<"Critical Cycle  of "<< ddg_filename<<" = "<<loop.CRITICAL_CYCLE(el)<<endl;
00115     cout<<"Edges belonging the the critical cycle"<<endl;
00116     forall(e, el){
00117         ie=loop[e];
00118         cout<< loop.source_id(e)<< " -> "<< loop.target_id(e);
00119         cout<<" : "<< ie<<endl;
00120     }
00121 
00122     
00123     //------- The user can outputs the DDGs to a .xml format --------
00124     snprintf(str, MAX_STRING, "%s_temp.xml", ddg_filename);;
00125     loop.write_to_xml(str); // Outputs the DDG loop to a .xml file format
00126 
00127     i=loop.read_from_xml(str); // RE-reading the DDG loop from a .xml file erases the previous DDG loop.
00128     if(i==-1) return EXIT_FAILURE;
00129     
00130     // ------ The user can visualize the DDGs ---------------------
00131     snprintf(str, MAX_STRING, "%s.vcg",ddg_filename); // sets the .vcg filename for the ddg loop
00132     loop.write_to_vcg(str); //outputs the DDG loop to a vcg file to be visualized by the xvcg tool
00133     cout<<endl<<str<< " can be visualized using xvcg."<<endl;
00134     
00135     loop_copy.copy(loop); // create an exact copy of the loop
00136     snprintf(str, MAX_STRING, "%s_copy.vcg",ddg_filename);
00137     //exports the copy loop to a vcg file to be visualized by the xvcg tool
00138     loop_copy.write_to_vcg(str);
00139     
00140     // The user can access any kind of information 
00141     T=loop.T();
00142     forall(rt, T){
00143         cout <<"The set of values of type "<< rt.get_register_typename() <<" is :"<<endl;
00144         VR=loop.get_V_R(rt.get_register_type_id());
00145         forall(u, VR){
00146             it=loop.instruction_type(u);
00147             cout<< loop.id(u)<< " with opcode " << it.opcode()<< " ("<<loop.latency(u)<<","<<loop.delta_r(u)<<","<<loop.delta_w(u, rt.get_register_type_id())<<")"<<endl;
00148         }
00149     }
00150     //----- We can unroll the loop while preserving recurrent edges
00151     unroll(loop, unrolled, 3);
00152     snprintf(str, MAX_STRING, "%s_unrolled_3.vcg",ddg_filename); // sets the .vcg filename for the ddg loop
00153     unrolled.write_to_vcg(str); //outputs the DDG loop to a vcg file to be visualized by the xvcg tool
00154     cout<<endl<<str<< " can be visualized using xvcg."<<endl;
00155     forall (rt, T){ 
00156         cout <<"The set of flow edges of the loop of type "<< rt.get_register_typename()<<" is :"<<endl;
00157         ER=unrolled.get_E_R(rt.get_register_type_id());
00158         forall(e, ER){
00159         ie=unrolled[e];
00160         cout<< unrolled.source_id(e)<<" -> "<< unrolled.target_id(e)<<" : "<< ie<<endl;
00161         }
00162     }
00163 
00164     // ------------- Hiding and restoring nodes -------------
00165     // look for two arbitrary nodes to hide
00166     forall (rt, T){ 
00167         
00168         if (loop.get_V_R(rt.get_register_type_id()).size()>=2) {
00169         loop.hide_node(loop.get_V_R(rt.get_register_type_id()).choose()); // just to hide one arbitrary value node. Notice that all adjacent edges are hidden too
00170         loop.hide_node(loop.get_V_R(rt.get_register_type_id()).choose()); // hide another arbitrary one
00171         break;
00172         }
00173     }
00174     cout<<"Critical Cycle  of "<< ddg_filename<<" (after hiding two arbitrary values of type "<< rt.get_register_typename()<<" ) = "<<loop.CRITICAL_CYCLE(el)<<endl;
00175     cout<<"Edges belonging the the critical cycle"<<endl;
00176     forall(e, el){
00177         ie=loop[e];
00178         cout<< loop.source_id(e)<< " -> "<< loop.target_id(e);
00179         cout<<" : "<< ie<<endl;
00180     }
00181         
00182     
00183     loop.restore_all_nodes();
00184     loop.restore_all_edges();
00185 
00186     cout<<"Critical Cycle  of "<< ddg_filename<<" (after restoring all values and edges) = "<<loop.CRITICAL_CYCLE(el)<<endl;
00187     cout<<"Edges belonging the the critical cycle"<<endl;
00188     forall(e, el){
00189         ie=loop[e];
00190         cout<< loop.source_id(e)<< " -> "<< loop.target_id(e);
00191         cout<<" : "<< ie<<endl;
00192     }       
00193 
00194     
00195     //--- Many other software opportunities exist. See the reference manual.
00196 
00197     return EXIT_SUCCESS;
00198 }
00199
January 2009, by Sid Touati (Copyright INRIA and University of Versailles)