dag_example.cpp

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 
00034 #include "DDG.h" // the header file of the DDG library. 
00035         // To be included by the user.
00036 #include "LEDA/graph/graph_misc.h" // Is_Acyclic 
00037 #include <iostream>
00038 #include <cstdlib>
00039 
00040 
00041 using namespace std;
00042 using namespace DDG; // the namespace of the DDG library.
00043 
00044 
00045 
00046 int main(int argc, char *argv[])
00047 {
00048     //int are always usefull
00049     int         i,j,cpt ;
00050     int c; // for getopt
00051     // some strings for file names
00052     char        *ddg_filename=NULL, *arch_filename=NULL;
00053     char        str[MAX_STRING];
00054     REGISTER_TYPES rt;
00055     LEDA::list<REGISTER_TYPES> T;
00056     
00057     // some objects for graphs
00058     //declare a DDG of a loop (cyclic data dependence graph)
00059     DDG::LOOP loop; 
00060     ARCHITECTURE ISA_example;
00061     DDG::DAG dag, dag_copy;  // declare a DDG of a basic block (directed acyclic graph : DAG)
00062     
00063     LEDA::node n,u;
00064     LEDA::edge e;
00065     LEDA::set<node> VR;
00066     LEDA::set<node> MA; // for a maximal antichain computation
00067     LEDA::node_map<int> map; // when duplicating a graph, 
00068                 // we need to save node correspondance between original and new graph
00069     LEDA::node_array<node> killer; // for register saturation examples
00070     array< list<node> > ALN ; // array of sorted chains
00071 
00072     DDG::INSTRUCTIONS_TYPES it; // information attached to an opcode
00073     
00074     LEDA::list<edge> el; 
00075     LEDA::list<node> nl; 
00076     LEDA::set<node> parents, children; // set of parents and children of a node
00077 
00078     while ((c = getopt (argc, argv, "i:a:")) != -1){
00079         switch(c){
00080             case 'a': arch_filename=optarg;
00081                 break;
00082             case 'i': ddg_filename =optarg;
00083                 break;
00084             case '?': 
00085                 cout<<"usage:"<< argv[0] <<" -i ddg_filename.xml [-a isa_desc.xml] "<<endl;
00086                 return EXIT_FAILURE;
00087         }
00088         
00089     }
00090     
00091     //------- the user can define its own ISA ----------------
00092     if (arch_filename!=NULL)  { 
00093         ISA_example.read_from_xml(arch_filename);
00094         if(ISA_example.check()){
00095             loop=LOOP(ISA_example);  //build an empty DDG loop with a user defined architcural (ISA) description
00096             dag=DAG(ISA_example);   //build an empty DAG with a user defined architcural (ISA) description
00097         } else return EXIT_FAILURE;
00098     }
00099      
00100      //---------------- The user can read a DDG from an xml format defined by the DDG library 
00101     
00102     if (ddg_filename != NULL){
00103     
00104         i=loop.read_from_xml(ddg_filename); // reads the DDG loop from a n xml file
00105         
00106         if(i==-1){
00107             return EXIT_FAILURE;
00108         }
00109         
00110         i=dag.read_from_xml(ddg_filename); // reads the DDG loop from a n xml file
00111         
00112         if(i==-1){
00113             return EXIT_FAILURE;
00114         }
00115         
00116     }
00117     else{
00118         cout<<"usage:"<< argv[0] <<" -i ddg_filename.xml [-a isa_desc.xml] "<<endl;
00119         return EXIT_FAILURE;
00120     }
00121 
00122     if(! Is_Acyclic(dag, el)) {
00123         cerr<<"Input Error: Non acyclic graph.\n";
00124         cerr<<"There are "<< el.size() <<" illegal arcs:\n";
00125         forall(e, el){
00126             cerr<<dag.id(dag.source(e))<<" -> "<< dag.id(dag.target(e))<<endl;
00127         }
00128         return EXIT_FAILURE;
00129     }
00130 
00131     
00132      // The user can modify the DDG by many other methods : 
00133     // new_node, new_edge, clear, del_node, del_edge, etc.
00134      // The user can access any information about nodes, edges,
00135      // apply well known algorithms using the LEDA library
00136      // See the LEDA manual : http://www.algorithmic-solutions.info/leda_manual
00137      // See the DDG user manual inside this distribution
00138     
00139 
00140     cout<< "DAG example program: " <<ddg_filename<<endl;
00141     cout<< "-----------------------------" <<endl;
00142     T=dag.T();
00143     
00144     forall(rt,T){
00145             
00146         cout<<"Register Saturation of the DAG (loop body) for register type "<< rt.get_register_typename() <<" is " <<REGISTER_SATURATION (dag, rt.get_register_type_id(), nl)<<endl;
00147         cout<<"Saturating values of type "<<rt.get_register_typename()<<endl;
00148         forall(n, nl){
00149         it= dag.instruction_type(n);
00150         cout<< dag.id(n)<< " with opcode " << it.opcode()<< " ("<<dag.latency(n)<<","<<dag.delta_r(n)<<","<<dag.delta_w(n, rt.get_register_type_id())<<")"<<endl;
00151         }
00152     }
00153     // -------------------- The critical path is the longest path of the DAG
00154     cout<<endl<<"Critical Path ="<<dag.CriticalPath(el)<<endl;
00155 
00156     cout<<"Edges belonging to the critical path"<<endl;
00157     forall(e, el){
00158         n=dag.source(e);
00159         u=dag.target(e);
00160         it= dag.instruction_type(n);
00161         cout<< dag.id(n)<< " -> " << dag.id(u) <<endl;
00162     }
00163 
00164     //----------------------- We can access the DAG in many ways
00165     forall_nodes(u, dag){
00166         parents=dag.get_parents(u);
00167         cout<<"The parents of the node number "<<dag.id(u)<<" are : ";
00168         forall (n, parents){
00169             cout<<dag.id(n)<<" ";
00170         }
00171         cout<<endl;
00172     }
00173     forall_nodes(u, dag){
00174         children=dag.get_children(u);
00175         cout<<"The children of the node number "<<dag.id(u)<<" are : ";
00176         forall (n, children){
00177             cout<<dag.id(n)<<" ";
00178         }
00179         cout<<endl;
00180     }
00181     forall_nodes(u, dag){
00182         parents=dag.get_up(u);
00183         cout<<"The ascendants of the node number "<<dag.id(u)<<" are : ";
00184         forall (n, parents){
00185             cout<<dag.id(n)<<" ";
00186         }
00187         cout<<endl;
00188     }
00189     forall_nodes(u, dag){
00190         children=dag.get_down(u);
00191         cout<<"The descendants of the node number "<<dag.id(u)<<" are : ";
00192         forall (n, children){
00193             cout<<dag.id(n)<<" ";
00194         }
00195         cout<<endl;
00196     }
00197     
00198     // ------------------ The user can visualize the DAG ------------------------
00199     snprintf(str, MAX_STRING, "%s_dag.vcg",ddg_filename); // sets the .vcg filename for the DAG
00200     dag.write_to_vcg(str); //outputs the DAG to a vcg file to be visualized by the xvcg tool
00201     dag_copy.copy(dag); // create an exact copy.
00202     snprintf(str, MAX_STRING, "%s_dag_copy.vcg",ddg_filename); 
00203     dag_copy.write_to_vcg(str); //outputs the copy DAG to a vcg file to be visualized by the xvcg tool
00204     
00205     cout<<endl<<str<< " can be visualized using xvcg."<<endl;
00206 
00207     /*--------------- The user can extract a copy of a loop body -------------- */
00208     
00209     map.init(loop);/* initializes a mapping function from loop nodes to dag nodes.
00210     Forall u a node in the loop, map(u) stores its corresponding node in the exctracted DAG (loop body) */
00211     dag.clear();
00212     forall_nodes(u,loop){
00213         map[u]=dag.new_node((loop.instruction_type(u)).opcode_id());
00214     }
00215     forall_edges(e,loop){
00216         if(loop.lambda(e)==0) { // It is an edge belonging to the loop body ==> insert it into the DAG
00217             dag.new_edge(map[loop.source(e)], map[loop.target(e)],loop[e]);
00218         }
00219     }
00220 
00221     // --- Dilworth decomposition -----------
00222     i=MAXIMAL_ANTI_CHAIN(dag, MA);
00223     cout<<"Maximal antichain in the DAG : "<<i<<endl;
00224     cout<<"Nodes belonging to a maximal antichain "<<endl;
00225     forall(n, MA){
00226         cout<< dag.id(n)<< " with opcode " << it.opcode()<<endl;
00227     }
00228 
00229     //---The user can extract the body of a loop unrolled many times
00230     // (recurrent data dependence edges are preserved) ----------
00231     
00232     cout<<"Unrolling the loop "<<ddg_filename<<" four times and extract its body"<<endl;
00233     unroll (loop, dag, 4);
00234     snprintf(str, MAX_STRING,"%s_dag_unroll_4.vcg",ddg_filename); // sets the .vcg filename for the ddg loop
00235     dag.write_to_vcg(str);
00236     // The user can access any kind of information 
00237     forall(rt,T){
00238         cout <<"The set of values of type "<< rt.get_register_typename() <<" of the body  is :"<<endl;
00239         VR=dag.get_V_R(rt.get_register_type_id());
00240         forall(u, VR){
00241             it=dag.instruction_type(u);
00242             cout<< dag.id(u)<< " with opcode " << it.opcode()<<endl;
00243     
00244         }
00245     }
00246     cout<<endl<< "The set of sources of the body are :"<<endl;
00247     VR=dag.get_Sources();
00248     forall(u, VR){
00249         it=dag.instruction_type(u);
00250         cout<< dag.id(u)<< " with opcode " << it.opcode()<<endl;
00251     }
00252     cout<<endl<< "The set of sinks of the body are :"<<endl;
00253     VR=dag.get_Targets();
00254     forall(u, VR){
00255         it=dag.instruction_type(u);
00256         cout<< dag.id(u)<< " with opcode " << it.opcode()<<endl;
00257     }
00258     
00259     // Computes the critical path of the DAG and puts the list of its nodes in nl
00260     cout<<endl<<"Critical Path of the unrolled body ="<<dag.CriticalPath(nl)<<endl;
00261     cout<<"Nodes belonging the critical path of the unrolled body "<<endl;
00262     forall(n, nl){
00263         it= dag.instruction_type(n);
00264         cout<< dag.id(n)<< " with opcode " << it.opcode()<<endl;
00265     }
00266 
00267     // ------------- Hiding and restoring nodes -------------
00268     // look for two arbitrary values of any register type
00269     forall(rt, T){
00270         if (dag.get_V_R(rt.get_register_type_id()).size()>=2){
00271             dag.hide_node(dag.get_V_R(rt.get_register_type_id()).choose()); // just to hide one node writing into a register
00272                         // note that all adjacent edges are hidden too
00273             dag.hide_node(dag.get_V_R(rt.get_register_type_id()).choose()); // hide another one
00274             break;
00275         }
00276     }
00277     rt=T.front();
00278     cout<<"Register Saturation of the DAG (after hiding two values of type "<< rt.get_register_typename() <<") is : "<<(j=REGISTER_SATURATION (dag, rt.get_register_type_id(), nl, killer))<<endl;
00279     cout<<"Saturating values of type "<< rt.get_register_typename() <<endl;
00280     forall(n, nl){
00281         it= dag.instruction_type(n);
00282         cout<< dag.id(n)<< " with opcode " << it.opcode()<<endl;
00283     }
00284     
00285     dag.restore_all_nodes(); 
00286     dag.restore_all_edges();
00287     dag.build_internal_structures(); // restore the internal state of the DAG
00288 
00289     cout<<"Register Saturation of the DAG (after restoring the two values of type"<< rt.get_register_typename()<<") is : "<<REGISTER_SATURATION (dag, rt.get_register_type_id(), nl, killer)<<endl;
00290     cout<<"Saturating values of type "<< rt.get_register_typename()<<endl;
00291     forall(n, nl){
00292         it= dag.instruction_type(n);
00293         cout<< dag.id(n)<< " with opcode " << it.opcode()<<endl;
00294     }
00295 
00296     //--------------------- Lattices and Orders --------------------------/
00297     cout<<"Lattices and Order Notations:\n";
00298     forall_nodes(u, dag){
00299         forall_nodes(n, dag){
00300             if(lt(u,n)){
00301                 cout<<dag.id(u)<< " < " << dag.id(n) << endl;
00302             }
00303             if(le(u,n)){
00304                 cout<<dag.id(u)<< " <= " << dag.id(n)<< endl;
00305             }
00306             if(gt(u,n)){
00307                 cout<<dag.id(u)<< " > " << dag.id(n)<< endl;
00308             }
00309             if(ge(u,n)){
00310                 cout<<dag.id(u)<< " >= " << dag.id(n)<< endl;
00311             }
00312             if(parallel(u,n)){
00313                 cout<<dag.id(u)<< " || " << dag.id(n)<< endl;
00314             }
00315             if(comparable(u,n)){
00316                 cout<<dag.id(u)<< " ~ " << dag.id(n)<< endl;
00317             }
00318         }
00319     }
00320 
00321 
00322     cout<<"Minimal Chain Decomposition (Dilworth)"<<endl;
00323     cout<<"--------------------------------------"<<endl;
00324     j=MINIMAL_CHAIN(dag, ALN);
00325 
00326     cout<<"There are "<< j <<" chains"<<endl;
00327     cpt=0;
00328     for(i=0;i< j ;i++){
00329         cout<<"Chain["<<i<<"]: ";
00330         forall(u,ALN[i]){
00331             cout<<dag.id(u);
00332             cout<<" ";
00333             cpt++;
00334         }
00335         cout<<endl;
00336     }
00337     cout<<"Total "<< cpt <<" nodes"<<" in this distribution."<<endl;
00338     //--------------------- Many other software opportunities exist. See the reference manual.
00339 
00340     return EXIT_SUCCESS;
00341 }