Polaris: cdg.cc Source File

cdg.cc Go to the documentation of this file. /// /// /// /// /// /// $Documentation Manager$ = "Doxygen" /// /*! \file cdg.cc \author Silvius Rus \date 9/19/00 \brief Implementation for cdg.h */ /// /// /// #include "utilities/switches_util.h" #include "cdg_types.h" #include "cdg.h" #include <strings.h> #include "normalize_cfg.h" #include "ProgramUnit.h" #include "utilities/dominator_util.h" #include "domtree/polaris_domtree.h" #include "p-assert.h" #include "Timer.h" /////////////////////////////////////////////////////////////////////////// /// Static global objects. /////////////////////////////////////////////////////////////////////////// static int _cdg_pass; inline static bool equal(Statement& s1, Statement& s2){ if (&s1!=&s2) return False; return True; } inline static Statement* pdt_parent(Statement* stmt){ pDominatorWorkSpace& ws=*(pDominatorWorkSpace *) stmt->work_stack().top_ref(_cdg_pass); p_assert(&ws, "Statement without pDominatorWorkSpace."); return ws.idom; } CDGNode* pdt_parent(CDGNode* child){ Statement* parent=pdt_parent(child->cfgnode()); if (parent){ return parent->cdgnode(); } else { return 0; } } static bool postdominates(Statement& s1, Statement& s2){ Statement* stmt=&s2; while (stmt){ if (equal(*stmt,s1)) return True; stmt=pdt_parent(stmt); } return False; } inline CDSet& cd(CDGNode* cdgnode){ return cdgnode->ins(); } /////////////////////////////////////////////////////////////////////////// /// Exported objects /////////////////////////////////////////////////////////////////////////// int _cdg_report_cycles; bool postdominates(CDGNode* n1, CDGNode* n2){ if (n1==0 || n2==0) return false; return postdominates(*(n1->cfgnode()), *(n2->cfgnode())); } /// It assumes the CFG has nodes with outdegree at most 2. /// normalize_cfg should be called before this function to fix the CFG. /// Returns its pass tag. int cdg(ProgramUnit& pgm) { //Sanity check. switch(pgm.pu_class()){ case PROGRAM_PU_TYPE: case SUBROUTINE_PU_TYPE: case FUNCTION_PU_TYPE: break; default: p_warning("Input to cdg is not a program, subroutine, or function: skipping."); return 0; } /// Let the fun begin. /// _cdg_report_cycles=switch_value("cdg_report_cycles"); /// if (_cdg_report_cycles<1) _cdg_report_cycles=0; StmtList& stmts=pgm.stmts(); /// Start to build post-dominator tree. _cdg_pass = create_pass_tag(); /// Build post-dominator tree. Array<Statement *> vertex(stmts.entries()); pDominator(pgm, vertex, new pDominatorWorkSpace(_cdg_pass)); /// Create CDG nodes for every statement. for (int i=0; i<vertex.entries(); i++){ Statement* stmt=vertex[i]; stmt->cdgnode(new CDGNode(stmt)); /// ... Fix the PDT so that it looks like the edge start->end had existed in CFG when the PDT was built. if (stmt->stmt_class()==FLOW_ENTRY_STMT){ pDominatorWorkSpace& ws=*(pDominatorWorkSpace *) stmt->work_stack().top_ref(_cdg_pass); p_assert(&ws, "Statement without pDominatorWorkSpace."); ws.idom=vertex[0]; } } /// Create the CDG. for (int i=0; i<vertex.entries(); i++){ Statement& A=*vertex[i]; int which_branch=0; for (Iterator<Statement> stit=A.succ(); stit.valid(); ++stit, which_branch++){ Statement& B=stit.current(); if (postdominates(B,A)) continue; bool branch; switch (which_branch){ case 0: branch=False; break; case 1: branch=True; break; default: p_abort("Reduce the number of branches to 2 before building CDG!"); } Statement* PA=&A; Statement* parent=pdt_parent(&A); if (parent) PA=parent; CDGNode* cdgA=A.cdgnode(); Statement* N=&B; while (!equal(*N,*PA)){ CDGNode* cdgN=N->cdgnode(); CDElement in(cdgA,branch); CDElement out(cdgN,branch); /// ... Set links in CDG: cdgN->ins().ins(in); cdgA->outs().ins(out); N=pdt_parent(N); p_assert(N,"Just missed PA, so it does not postdominate N."); } } } /// Copy ipdom info to cdg nodes. for (int i=0; i<vertex.entries(); i++){ CDGNode* child=vertex[i]->cdgnode(); Statement* sparent=pdt_parent(vertex[i]); if (sparent==0) continue; CDGNode* parent=sparent->cdgnode(); child->ipdom_parent(parent); parent->ipdom_children().push_back(child); } return _cdg_pass; } /// Clears "visited" field to all nodes in the program unit cdg. void clear_cdg_visited(ProgramUnit& pgm, int reset_value){ for(Iterator<Statement> stit=pgm.stmts().iterator(); stit.valid();++stit){ CDGNode* cdgnode=stit.current().cdgnode(); if (!cdgnode) { String msg="\nCDG node does not exist for statement "; msg+=stit.current().tag(); msg+=".\n"; p_warning(msg); } cdgnode->visited(reset_value); } } /// Removes cdg nodes associated with all statements. void uncdg(ProgramUnit& pgm){ for(Iterator<Statement> stit=pgm.stmts().iterator(); stit.valid();++stit){ CDGNode* cdgnode=stit.current().cdgnode(); if (cdgnode) { delete cdgnode; stit.current().cdgnode(0); } } }

© 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:05:41 2005