Polaris: cdg_dag2tree_evaluator.cc Source File

00001 ///
00002 #include <list.h>
00003 #include "utilities/switches_util.h"
00004 #include "cdg/cdg_types.h"
00005 #include "cdg/cdg.h"
00006 
00007 /// just for statistics.
00008 typedef struct _CDStat{
00009   CDGNode* node;
00010   int accum, outdeg;
00011 } CDStat;
00012 
00013 
00014 int _cdg_report_expansion=0;
00015 
00016 /// Returns the number of nodes in the tree resulted from cloning nodes in the
00017 /// CDG (it assumes the CDG is a dag).
00018 int evaluate_dag2tree(ProgramUnit& pgm){
00019   
00020   _cdg_report_expansion=0;
00021   if (_cdg_report_expansion<1) _cdg_report_expansion=0;
00022 /// Statistic 1. counts in-degrees of cdg nodes
00023   if (_cdg_report_expansion){
00024     cout<<"\n\tFor program unit "<<pgm.routine_name_ref();
00025   }
00026   for(Iterator<Statement> stit=pgm.stmts().iterator();stit.valid();++stit){
00027     int indeg=stit.current().cdgnode()->ins().entries();
00028     if (cdg_self_loop(stit.current().cdgnode())) 
00029       indeg--;
00030     if (indeg>1){
00031       if (_cdg_report_expansion){
00032     cout<<"\n\tIndegree "<<indeg;
00033     cout<<" for statement \n"<<stit.current();
00034       }
00035     }
00036   }
00037 
00038 
00039 
00040 /// Statistic 2. computes number of necessary predicates to aggregate access
00041 /// info.
00042   clear_cdg_visited(pgm);
00043   int nnodes=pgm.stmts().entries();
00044   vector<CDStat> all;
00045   int i=0;
00046   for (Iterator<Statement> stit=pgm.stmts().iterator();stit.valid();++stit){
00047     CDGNode* node=stit.current().cdgnode();
00048     CDStat stat;
00049     stat.node=node;
00050     stat.accum=1;
00051     stat.outdeg=node->outs().entries();
00052     if (cdg_self_loop(node)){
00053       stat.outdeg--;
00054     }
00055     all.push_back(stat);
00056     node->visited(i);
00057     i++;
00058   }
00059 
00060 
00061   list<int> todo;  
00062 /// initialize work queue
00063   for (i=0;i<nnodes;i++){
00064     if (all[i].outdeg==0){
00065       todo.push_back(i);
00066     }
00067   }
00068 
00069   while (todo.size()!=0){
00070     int which=todo.front();
00071     todo.pop_front();
00072     CDGNode* node=all[which].node;
00073     for (Iterator<CDElement> cdit=node->ins();cdit.valid();++cdit){
00074       CDGNode* pred=cdit.current().node();
00075       if (pred==node) continue;
00076       int which_pred=pred->visited();
00077       all[which_pred].accum+=all[which].accum;
00078       all[which_pred].outdeg--;
00079       if (all[which_pred].outdeg==0){
00080     todo.push_back(which_pred);
00081       }
00082     }
00083   }
00084 
00085   
00086   if (_cdg_report_expansion){
00087     cout<<"\n\tFor program unit "<<pgm.routine_name_ref()
00088     <<": the size of predicate set (worst case) is "
00089     <<all[pgm.stmts().first_ref()->cdgnode()->visited()].accum
00090     <<" while the program size is "
00091     <<pgm.stmts().entries();
00092   }
00093 
00094 /// End statistic 2.
00095   
00096   return all[pgm.stmts().first_ref()->cdgnode()->visited()].accum;
00097 
00098 }