Polaris: cdg_cycle_detector.cc Source File

00001 ///
00002 ///
00003 /// $Documentation Manager$ = "Doxygen"
00004 ///
00005 /*!
00006   \file cdg_cycle_detector.cc
00007   \author Silvius Rus
00008   \date 9/19/00
00009   \brief Implementation for function to count the cycles in a CDG.
00010 */
00011 ///
00012 ///
00013 ///
00014 #include "cdg.h"
00015 #include "cdg_types.h"
00016 
00017 
00018 /// Tells whether this node has a self loop.
00019 bool cdg_self_loop(CDGNode* root){
00020   for (Iterator<CDElement> cdit=root->outs(); cdit.valid(); ++cdit){
00021     CDGNode* next=cdit.current().node();
00022     if (next==root){
00023       return true;
00024     }
00025   }
00026   return false;
00027 }
00028 
00029 
00030 /// Used to count cycles while recursing into dcc_dfs.
00031 static int count_cycles;
00032 
00033 /// Defined in cdg.cc
00034 extern int _cdg_report_cycles;
00035 
00036 /// The recursive routine called by detect_cdg_cycles.
00037 void dcc_dfs(CDGNode* root,ProgramUnit& pgm){
00038   root->visited(1);
00039   for (Iterator<CDElement> cdit=root->outs(); cdit.valid(); ++cdit){
00040     CDGNode* next=cdit.current().node();
00041     /// ...  recursive call site
00042     if (!next->visited()) dcc_dfs(next,pgm);
00043     else{
00044       if (next->visited()==1){
00045     /// ...  Report cdg back edge.
00046     if (next!=root) {
00047       if (_cdg_report_cycles){
00048         cout<<"\n\tDetected back edge in dfs traversal of CDG "
00049         <<"between statements "<<root->cfgnode()->tag()
00050         <<" and "<<next->cfgnode()->tag()
00051         <<" in program unit "<<pgm.routine_name_ref();
00052       }
00053     }
00054     
00055     /// ...  skip self-loops, they are not a problem
00056     if (next!=root){
00057       count_cycles++;
00058     }
00059       }
00060     }
00061   }
00062   root->visited(2);
00063 }
00064 
00065 /// Reports the number of cycles (back edges) in the CDG.  It does not count the self loops.
00066 int detect_cdg_cycles(ProgramUnit& pgm){
00067   count_cycles=0;
00068   //Sanity check.
00069   switch(pgm.pu_class()){
00070   case PROGRAM_PU_TYPE:
00071   case SUBROUTINE_PU_TYPE:
00072   case FUNCTION_PU_TYPE:
00073     break;
00074   default:
00075     p_warning("Input to detect_cdg_cycles is not a program, subroutine, or function: skipping.");
00076     return 0;
00077   }
00078   
00079   CDGNode* root=pgm.stmts().first_ref()->cdgnode();
00080 
00081   if (root==0){
00082     p_warning("CDG needs to be built before trying to find cycles in it.");
00083     return 0;
00084   }
00085 
00086   clear_cdg_visited(pgm);
00087 
00088   dcc_dfs(root,pgm);
00089 
00090   return count_cycles;
00091 }