Polaris: stmt_toporder.cc Source File

00001 ///
00002 ///
00003 /// \file ControlRangeDict.cc
00004 ///
00005 #include "../Collection/Iterator.h"
00006 #include "../Statement/Statement.h"
00007 #include "../WorkSpace.h"
00008 
00009 #include "stmt_toporder.h"
00010 
00011 unsigned int _pass_tag;
00012 
00013 
00014 /// class StmtTopOrderWS
00015 
00016 class StmtTopOrderWS : public WorkSpace {
00017 public:
00018     int toporder;       /// ...  topological order value.
00019     bool visited;               /// ...  Have I been visited when computing toporder?
00020     
00021     StmtTopOrderWS(unsigned long pass_tag) : WorkSpace(pass_tag) {
00022     toporder = -1;
00023     visited = false;
00024     }
00025     
00026     StmtTopOrderWS(const StmtTopOrderWS &other) : WorkSpace(other) {
00027     toporder = other.toporder;
00028     visited = other.visited;
00029     }
00030     
00031     virtual ~StmtTopOrderWS() {};
00032     
00033     virtual Listable *listable_clone() const {
00034     return new StmtTopOrderWS(*this);
00035     }
00036 
00037     virtual void print(ostream &o) const {
00038     o << "[toporder=" << toporder;
00039     o << ", visited=" << visited << "]";
00040     }
00041     
00042     virtual int structures_OK() const {
00043     return 1;
00044     }
00045 };
00046 
00047 
00048 /// get_workspace
00049 ///   Get the workspace for the given statement.
00050 
00051 static StmtTopOrderWS &
00052 _get_workspace(const Statement &stmt)
00053 {
00054     WorkSpace *ws = stmt.work_stack().top_ref(_pass_tag);
00055 
00056     p_assert(ws, "Statement doesn't have a StmtTopOrderWS.");
00057 
00058     return * (StmtTopOrderWS *) ws;
00059 }
00060 
00061 
00062 /// _calc_toporder
00063 ///   Calculate toporder for the flow graph.  Essentially, this algorithm
00064 ///   performs a topological sort on the flow graph, ignoring back
00065 ///   edges.
00066 
00067 static void
00068 _calc_toporder1(Statement &stmt, int &toporder)
00069 {
00070     StmtTopOrderWS &ws = _get_workspace(stmt);
00071 
00072     if (! ws.visited) {
00073     ws.visited = true;
00074     Iterator<Statement> succ_iter = stmt.succ();
00075     
00076     for (succ_iter.set_to_last(); succ_iter.valid(); --succ_iter)
00077         _calc_toporder1(succ_iter.current(), toporder);
00078 
00079     ws.toporder = toporder--;
00080     }
00081 }
00082 
00083 static void
00084 _calc_toporder(StmtList &stmts)
00085 { 
00086     /// ...  Calculate the topological order for each statement
00087 
00088     int toporder = stmts.entries() - 1;
00089 
00090     if (toporder >= 0) {
00091     Iterator<Statement> entry_iter = stmts.iterate_entry_points();
00092 
00093     for ( ; entry_iter.valid(); ++entry_iter)
00094         _calc_toporder1(entry_iter.current(), toporder);
00095  
00096     p_assert(toporder >= -1,
00097          "_calc_toporder visited a stmt more than once.");
00098     }
00099 }
00100 
00101 
00102 /// stmt_toporder
00103 
00104 Database<String, IntElem> *
00105 stmt_toporder(StmtList &stmts)
00106 {
00107     _pass_tag = create_pass_tag();
00108 
00109     /// ...  Create a workspace for each statement.
00110 
00111     Iterator<Statement> iter = stmts.iterator();
00112 
00113     for ( ; iter.valid(); ++iter)
00114     iter.current().work_stack().push(new StmtTopOrderWS(_pass_tag));
00115 
00116     /// ...  Compute the reverse topological ordering.
00117 
00118     _calc_toporder(stmts);
00119 
00120     /// ...  Fill the topological ordering mapping with the computed ordering.
00121 
00122     Database<String, IntElem> *toporder_map =  new Database<String, IntElem>;
00123     
00124     for (iter.reset() ; iter.valid(); ++iter) {
00125     const StmtTopOrderWS &ws = _get_workspace(iter.current());
00126     toporder_map->ins(iter.current().tag(), new IntElem(ws.toporder));
00127     iter.current().work_stack().pop(_pass_tag);
00128     }
00129 
00130     return toporder_map;
00131 }