Polaris: cdg_dag2tree.cc Source File

cdg_dag2tree.cc Go to the documentation of this file. /// /// $Documentation Manager$ = "Doxygen" /// /*! \file dag2tree.cc \author Silvius Rus \date 9/19/00 \brief Implementation for some functions defined in cdg.h */ /// /// /// #include <list.h> #include <set.h> #include <algorithm> #include "Directive/RecurrenceAssertion.h" #include "Directive/AssertLoopLabel.h" #include "cdg/cdg_types.h" #include "cdg/cdg.h" #include "Statement/Statement.h" #include "Statement/LabelStmt.h" #include "ProgramUnit.h" #include "Directive/AssertComment.h" #include <exception> /// Clones node and links the clone to the given parent. /// It is recursive. it assumes node is a tree root (it won't fail for a /// dag but will result in infinite cycle if the graph is cyclic). void cdg_clone(CDGNode* node, CDGNode* parent, bool value){ /// Sanity check. p_assert(node, "Null CDG node to be cloned."); /// create the clone /// do not clone the statements. we will clone them anyway when /// we restore the cfg (in cdg2cfg). CDGNode* clone=new CDGNode(node->cfgnode()); /// link it to the parent CDSet pred; CDElement newcde(parent, value); pred.ins(newcde); clone->ins(pred); /// add all its children to the newly created node recursively for( Iterator<CDElement> cdit=node->outs(); cdit.valid(); ++cdit){ cdg_clone(cdit.current().node(), clone, cdit.current().value()); } } /// simple struct needed to walk up the CDG DAG. typedef struct __cdg_ws_node{ CDGNode* node; int outdeg; } _cdg_ws_node; /// Assumes the CDG has no cycles other then self-loops. /// call "detect_cdg_cycles(pgm)" if you need to check that. /// Modifies the CDG from a DAG to a tree (if it is not already one). void cdg_dag2tree(ProgramUnit& pgm){ clear_cdg_visited(pgm); int nnodes=pgm.stmts().entries(); vector<_cdg_ws_node> all; int i=0; for (Iterator<Statement> stit=pgm.stmts().iterator();stit.valid();++stit){ CDGNode* node=stit.current().cdgnode(); _cdg_ws_node ws; ws.node=node; ws.outdeg=node->outs().entries(); if (cdg_self_loop(node)){ ws.outdeg--; } all.push_back(ws); node->visited(i); i++; } list<int> todo; /// initialize work queue for (i=0;i<nnodes;i++){ if (all[i].outdeg==0){ todo.push_back(i); } } while (todo.size()!=0){ int which=todo.front(); todo.pop_front(); CDGNode* node=all[which].node; RefList<CDElement> to_del; int at_first=1; for (Iterator<CDElement> cdit=node->ins();cdit.valid();++cdit){ CDGNode* pred=cdit.current().node(); if (pred==node) continue; /// ... self loops are not interesting right now if (at_first){ at_first=0; continue; /// ... don't clone for this one, it's the first parent } else { /// ... remove all other parents from predecessor list. to_del.ins_first(cdit.current()); /// ... remove it from this parent's successors list for(Iterator<CDElement> cdit2=pred->outs();cdit2.valid();++cdit2){ if (cdit2.current().node()==node){ pred->outs().del(cdit2.current()); break; } } /// ... clone this node (with the whole subtree) and link it to this parent cdg_clone(node, pred, cdit.current().value()); /// ... look at the predecessor and check whether it is time /// ... to put it in the work queue (has no unvisited predecessors). int which_pred=pred->visited(); if (all[which_pred].outdeg==0){ todo.push_back(which_pred); } } } /// ... remove from ins all the parents that have been given clones as children for (Iterator<CDElement> cdit=to_del;cdit.valid();++cdit){ node->ins().del(cdit.current()); } } } /// sort the nodes in the given vector based on the postdominance relation /// it assumes the nodes are completely ordered by this relation (they are /// on a path from the root to a leaf). /// none of the nodes can be 0. void sort_pdt(vector<CDGNode*>& nodes){ unsigned int size=nodes.size(); unsigned int i,j; /// define a comparison table vector<int> zero(size,0); vector<vector<int> > table(size,zero); /// this thing can be done more efficiently using disjoint sets but I am in /// a hurry now. reconsider it if we need performance. for (i=0;i<size;i++){ for (j=0;j<size;j++){ if (i==j) continue; /// cerr<<"\n i="<<*nodes[i]->cfgnode() /// <<", j="<<*nodes[j]->cfgnode(); if (postdominates(nodes[i],nodes[j])){ /// cerr<<"\n\tTRUE"; table[i][j]=1; } else { /// cerr<<"\n\tFALSE"; } } } /// at this step it found all the relations. vector<CDGNode*> result(size); /// this vector will hold the mapping of positions in the sorted vector vector<int> pos(size,0); for (i=0;i<size;i++){ for (j=0;j<size;j++){ pos[i]+=table[i][j]; } result[pos[i]]=nodes[i]; } nodes=result; } /// Put all the children on the TRUE branch in PDT order. void get_trues(CDGNode* node, vector<CDGNode*>& trues){ if (node->outs().entries()==0){ return; } for (CDElement* cdit=node->outs().last_ref(); cdit; cdit=(CDElement*)cdit->prev_ref()){ if (cdit->node()==node) continue; /// ... skip myself Statement& stmt=*(cdit->node()->cfgnode()); switch(stmt.stmt_class()){ case ENDDO_STMT: case IMPLIED_GOTO_STMT: case ENTRY_STMT: case ENDIF_STMT: case ELSE_STMT: case RETURN_STMT: case LABEL_STMT: case GOTO_STMT: continue; default: break; } if (!cdit->value()) trues.push_back(cdit->node()); } sort_pdt(trues); } void write(vector<CDGNode*>& v, ostream& o); /// Put all the children on the FALSE branch in PDT order. void get_falses(CDGNode* node, vector<CDGNode*>& falses ){ if (node->outs().entries()==0){ return; } for (CDElement* cdit=node->outs().last_ref(); cdit; cdit=(CDElement*)cdit->prev_ref()){ if (cdit->node()==node) continue; /// ... skip myself Statement& stmt=*(cdit->node()->cfgnode()); /// cerr<<"\n Now at false: "<<stmt; switch(stmt.stmt_class()){ case ENDDO_STMT: case IMPLIED_GOTO_STMT: case ENTRY_STMT: case ENDIF_STMT: case ELSE_STMT: case RETURN_STMT: case LABEL_STMT: case GOTO_STMT: continue; default: break; } /// cerr<<"\nPushing back cdgnode: "<<cdit->node(); if (cdit->value()) falses.push_back(cdit->node()); } /// cerr<<"\nFalses before sorting:"; /// write(falses, cerr); sort_pdt(falses); } static set<String> _loop_labels; inline void copy_directives(Statement& from, Statement& to){ static unsigned llc=0; to.pre_directives()=from.pre_directives(); to.post_directives()=from.post_directives(); to.assertions()=from.assertions(); /// Modify loop label if DO stmt. if (to.stmt_class()==DO_STMT){ for(Iterator<Assertion> iter = to.assertions(); iter.valid(); ++iter) { if (iter.current().type() == AS_LOOPLABEL) { AssertLoopLabel &a = (AssertLoopLabel &) iter.current(); p_assert(a.string_arg_list_valid(), "Loop Label assertion with no valid name"); p_assert(a.string_arg_list_guarded().entries() == 1, "Only supporting Loop Label assertions with 1 field"); String old_label=a.string_arg_list_guarded()[0]; String new_label; if (_loop_labels.find(old_label)==_loop_labels.end()){ // First copy. new_label=old_label; _loop_labels.insert(new_label); } else { // Additional copy. strstream oldname; oldname<<old_label<<"_"<<llc++<<'\0'; const char* s=oldname.str(); new_label=s; oldname.freeze(0); } a.string_arg_list_guarded()[0]=new_label; } } } } void cdg_self_loop(CDGNode* root, bool& is_loop, bool& inside_predicate){ is_loop=false; inside_predicate=false; for (Iterator<CDElement> cdit=root->outs(); cdit.valid(); ++cdit){ CDGNode* next=cdit.current().node(); if (next==root){ is_loop=true; inside_predicate=cdit.current().value(); return; } } return; } /// Removes '\n' from given line. inline void clean_line(const char* l, String& cl){ const char* pc=l; char one[]="*"; while (*pc){ if (*pc!='\n'){ one[0]=*pc; cl+=one; } ++pc; } } /// Inserts the statements in the tree below "node" after "ref" /// Returns the last statement inserted. /// It assumes that any GOTO loops have been identified and transformed /// into DO or WHILE loops Statement* cdg2cfg(CDGNode* node, Statement* ref, ProgramUnit& pgm){ /// cerr<<"\n Now at node: "<<*node->cfgnode(); vector<CDGNode*> trues; get_trues(node, trues); vector<CDGNode*> falses; get_falses(node, falses); /// cerr<<"\nFalses:"; /// write(falses, cerr); Statement* where=ref; Statement& stmt=*(node->cfgnode()); if (node->outs().entries()==0){ /// ... This is a leaf. /// ... Ignore a few specific types of statements. switch(stmt.stmt_class()){ case ENDDO_STMT: case ENTRY_STMT: case IMPLIED_GOTO_STMT: case ENDIF_STMT: case ELSE_STMT: case RETURN_STMT: case LABEL_STMT: case GOTO_STMT: /// ... Ignore it. return ref; case DO_STMT: /// ... To add other cases. /// ... This would be an error. cerr<<stmt; p_abort("Abnormal type of statement as CDG leaf."); return ref; case STOP_STMT: /// ... For now, leave the STOP statements here. /// ... They have interprocedural effects. default: pgm.stmts().ins_after(stmt.clone(),ref); return ref->next_ref(); } } bool is_loop; bool inside_predicate; cdg_self_loop(node, is_loop, inside_predicate); if (is_loop){ Statement* where_else_is=0; if (inside_predicate){ /// ... Insert false children. for (unsigned int i=0;i<falses.size();i++){ where=cdg2cfg(falses[i],where,pgm); } where_else_is=where; /// ... Insert true children. for (unsigned int i=0;i<trues.size();i++){ where=cdg2cfg(trues[i],where,pgm); } } else { /// ... Insert true children. for (unsigned int i=0;i<trues.size();i++){ where=cdg2cfg(trues[i],where,pgm); } /// ... Insert false children. where_else_is=where; for (unsigned int i=0;i<falses.size();i++){ where=cdg2cfg(falses[i],where,pgm); } } /// ... Analyze this current node. switch(stmt.stmt_class()){ case WRITE_STMT: case READ_STMT: pgm.stmts().ins_after(stmt.clone(),ref); return ref->next_ref(); case IF_STMT: case ELSEIF_STMT:{ /// ... Wrap a WHILE around the children on the same edge value as the /// ... self loop and let the others out. Expression* predicate=stmt.expr().clone(); if (inside_predicate==true){ predicate=simplify(not(predicate)); } /// ... Check whether loop is empty. If so, add a label inside. if (ref==where_else_is){ Statement* dl=new LabelStmt(pgm.stmts().new_tag(), pgm.stmts().new_label()); pgm.stmts().ins_after(dl, ref); where_else_is=dl; } String comment=""; for (Iterator<Assertion> ait=stmt.assertions(); ait.valid(); ++ait){ if (ait.current().type()==AS_RECURRENCE){ RecurrenceAssertion& ra=(RecurrenceAssertion&)ait.current(); comment+=ra.ra_string_arg_list_guarded()[0]; } } if (comment==""){ strstream s; int w=1; stmt.write(s,w); s<<'\0'; clean_line(s.str(), comment); s.freeze(0); } Statement& clone=pgm.stmts().ins_WHILE_after(predicate, ref, where_else_is); AssertComment* newassert=new AssertComment(); newassert->string_arg_list_guarded(). ins_last(new StringElem(comment)); clone.assertions().ins_last(newassert); return ref->next_ref()->follow_ref(); } case DO_STMT: if (ref==where){ /// ... empty do body Statement* dummy=new LabelStmt(pgm.stmts().new_tag(), pgm.stmts().new_label()); pgm.stmts().ins_after(dummy,ref); where=dummy; Statement& clone=pgm.stmts().ins_DO_after(stmt.index().clone(), stmt.init().clone(), stmt.limit().clone(), stmt.step().clone(), ref, where); copy_directives(stmt,clone); pgm.stmts().del(*dummy); return ref->next_ref()->next_ref(); } else { Statement& clone=pgm.stmts().ins_DO_after(stmt.index().clone(), stmt.init().clone(), stmt.limit().clone(), stmt.step().clone(), ref, where); copy_directives(stmt,clone); return ref->next_ref()->follow_ref(); } break; case WHILE_STMT: if (ref==where){ /// ... empty while body Statement* dummy=new LabelStmt(pgm.stmts().new_tag(), pgm.stmts().new_label()); pgm.stmts().ins_after(dummy,ref); where=dummy; Statement& clone=pgm.stmts().ins_WHILE_after(stmt.expr().clone(), ref, where); copy_directives(stmt,clone); pgm.stmts().del(*dummy); return where->next_ref()->follow_ref(); } else { Statement& clone=pgm.stmts().ins_WHILE_after(stmt.expr().clone(), ref, where); copy_directives(stmt,clone); return ref->next_ref()->follow_ref(); } break; default: /// ... This statement cannot be a CDG internal node, since the only types /// ... of CFG branches are above. The other types of branching statements /// ... should have been transformed into one (or more) of the above. cerr<<"Unknown branch type encountered in the following statement:"; stmt.print(cerr); p_abort("Fatal error in IPA_CDG: see above message"); return ref; } } else { /// ... This is not a loop, must be IF, ELSEIF or FLOW_ENTRY. /// ... Insert true children. for (unsigned int i=0;i<trues.size();i++){ where=cdg2cfg(trues[i],where,pgm); } /// ... Insert false children. Statement* where_else_is=where; for (unsigned int i=0;i<falses.size();i++){ where=cdg2cfg(falses[i],where,pgm); } /// ... Analyze this current node. switch(stmt.stmt_class()){ case IF_STMT: case ELSEIF_STMT: if (trues.size()==0){ if (falses.size()==0){ // This case is an empty IF (IF (...) THEN ENDIF) // Polaris has some bug when I try to create an empty IF stmt // so I will do a trick: insert a dummy label, insert the if // around it then delete the label. Statement* dummy=new LabelStmt(pgm.stmts().new_tag(), pgm.stmts().new_label()); pgm.stmts().ins_after(dummy,ref); where=ref->next_ref(); pgm.stmts().ins_IF_after(not(stmt.expr().clone()),ref,where); // remove the dummy label /// pgm.stmts().del(*dummy); return ref->next_ref()->matching_endif_ref(); } else { /// cerr<<"\nref: "<<*ref /// <<"\nwhere: "<<*where; pgm.stmts().ins_IF_after(not(stmt.expr().clone()),ref,where); return ref->next_ref()->matching_endif_ref(); } } else { if (falses.size()>0){ // Insert an IF_ELSE_ENDIF pgm.stmts().ins_IF_ELSE_after(stmt.expr().clone(),ref, where_else_is,where); return ref->next_ref()->matching_endif_ref(); } else { // Insert an IF_ENDIF pgm.stmts().ins_IF_after(stmt.expr().clone(),ref,where); return ref->next_ref()->matching_endif_ref(); } } break; case FLOW_ENTRY_STMT: return ref; case READ_STMT: case WRITE_STMT: case PRINT_STMT: case OPEN_STMT: case CLOSE_STMT: case REWIND_STMT: case BACKSPACE_STMT: case ENDFILE_STMT: case INQUIRE_STMT: cerr<<"\nThe restructurer cannot handle for now I/O exception" <<"\nhandling constructs. The following statement at line " <<stmt.line()<<",\nin file "<<pgm.original_file_ref() <<" contains such a construct: \n"; { int w=1; stmt.write(cerr, w); } p_warning("Non-fatal error in CDG2CFG: see message above."); throw bad_exception(); default: /// ... This statement cannot be a CDG internal node, since the only types /// ... of CFG branches are above. The other types of branching statements /// ... should have been transformed into one (or more) of the above. cerr<<"Unknown branch type encountered in the following statement:"; stmt.print(cerr); p_abort("Fatal error in CDG2CFG: see above message"); return ref; } } } /// Removes cdg node associated with current statement. static void uncdg(Statement* stmt){ CDGNode* cdgnode=stmt->cdgnode(); if (cdgnode) { delete cdgnode; stmt->cdgnode(0); } } /// Removes old information from the only original statements. /// They are FLOW_ENTRY, ENTRY and FLOW_EXIT. /// Will remove the cdg nodes if they exist. static void custom_cleanup(ProgramUnit& pgm){ uncdg(pgm.stmts().first_ref()); uncdg(pgm.stmts().first_ref()->next_ref()); uncdg(pgm.stmts().last_ref()); _loop_labels.clear(); } /// Rewrites the CFG from the CDG. void cdg2cfg(ProgramUnit& pgm){ /// Initialize loop label repository. _loop_labels.clear(); /// Save start of old statement list, skip FLOW_ENTRY and ENTRY. Statement* old_start=pgm.stmts().first_ref()->next_ref()->next_ref(); /// cerr<<"\nold_start: "<<*old_start; /// Insert statements for all nodes recursively. cdg2cfg(pgm.stmts().first_ref()->cdgnode(), pgm.stmts().first_ref()->next_ref(),pgm); /// pgm.write(cerr); /// cerr<<"\nold_start: "<<*old_start; /// Remove original statements. pgm.stmts().del(*old_start,*(pgm.stmts().last_ref()->prev_ref())); /// Do some custom cleanup. custom_cleanup(pgm); }

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