Polaris: SSAControlRangeDict.cc Source File

00001 ///
00002 ///
00003 /// \file ControlRangeDict.cc
00004 ///
00005 #include "Program.h"
00006 #include "SSAProgramUnit.h"
00007 #include "Statement/Statement.h"
00008 #include "Symbol/Symbol.h"
00009 #include "Symtab.h"
00010 #include "Expression/Expression.h"
00011 #include "Directive/Assertion.h"
00012 #include "utilities/switches_util.h"
00013 #include "utilities/expression_util.h"
00014 #include "utilities/dominator_util.h"
00015 #include "Array.h"
00016 #include "IntSet.h"
00017 #include "Timer.h"
00018 #include "p-assert.h"
00019 
00020 #include "SSAControlRangeDict.h"
00021 #include "SSAControlRangeData.h"
00022 #include "RangeExpr.h"
00023 #include "range_util.h"
00024 #include "range_dict_util.h"
00025 
00026 #include "SSAControlRangeData.cc"
00027 
00028 static int _debug_level = 0;
00029 
00030 
00031 /// init_stmt_ranges
00032 ///   Initialize the data structures holding the ranges for all the statements
00033 
00034 void
00035 SSAControlRangeDict::_init_stmt_ranges(ProgramUnit &pgm)
00036 {
00037     Iterator<Statement> iter = pgm.stmts().iterator();
00038 
00039     for ( ; iter.valid(); ++iter) {
00040     SSAControlRangeData *data = new SSAControlRangeData(iter.current(),
00041                                 *this,
00042                                 _range_set);
00043 
00044     _stmt_ranges.ins(iter.current(), data);
00045     }
00046 }
00047 
00048 
00049 /// _init_idom
00050 ///   Initialize the idom (immediate dominator) field for all
00051 ///   SSAControlRangeData objects.
00052 
00053 void
00054 SSAControlRangeDict::_init_idom(ProgramUnit &pgm)
00055 {
00056     ImmediateDominator *idoms = immediate_dominator(pgm);
00057     p_assert(idoms, "Function immediate_dominator() returned NULL.");
00058 
00059     KeyIterator<Statement,SSAControlRangeData> data_iter = _stmt_ranges;
00060 
00061     for ( ; data_iter.valid(); ++data_iter) {
00062     const Statement &stmt = data_iter.current_key();
00063     SSAControlRangeData &data = data_iter.current_data();
00064     const Statement *idom = idoms->find_ref(stmt);
00065 
00066     if (idom)
00067         data._idom_ref = &_stmt_ranges[*idom];
00068     else
00069         data._idom_ref = 0;
00070     }
00071 
00072     delete idoms;
00073 }
00074 
00075 
00076 /// SSAControlRangeDict
00077 
00078 SSAControlRangeDict::SSAControlRangeDict(SSAProgramUnit &pgm, int debug GIV(0))
00079 : RangeDict(pgm.symtab())
00080 {
00081     _pgm_ref = &pgm;
00082 
00083      if (pgm.stmts().entries() == 0)
00084      return;
00085 
00086     _debug_level = debug;
00087     Timer tot_timer;
00088     Timer timer;
00089 
00090     _init_stmt_ranges(pgm);
00091 
00092     if (_debug_level > 0) {
00093     cout << "!  Data structure creation: " << timer << endl;
00094     timer.reset();
00095     }
00096 
00097     _init_idom(pgm);
00098 
00099     if (_debug_level > 0) {
00100     cout << "!  Computing immediate dominators: " << timer << endl;
00101     timer.reset();
00102     }
00103 
00104     if (_debug_level >= 10)
00105     print(cout);
00106 
00107     if (_debug_level > 0) {
00108     cout << "!  Total time: " << tot_timer << endl;
00109     cout << "!  Number of statements: " << pgm.stmts().entries() << endl;
00110     }
00111 }
00112 
00113 
00114 /// Destructor
00115 
00116 SSAControlRangeDict::~SSAControlRangeDict()
00117 {
00118 }
00119 
00120 
00121 /// icdom_touch
00122 
00123 void
00124 SSAControlRangeDict::icdom_touch()
00125 {
00126     KeyIterator<Statement, SSAControlRangeData> iter = _stmt_ranges;
00127 
00128     for ( ; iter.valid(); ++iter)
00129     iter.current_data().icdom_ref();
00130 }
00131 
00132 
00133 /// touch
00134 
00135 void
00136 SSAControlRangeDict::touch()
00137 {
00138     KeyIterator<Statement, SSAControlRangeData> data_iter = _stmt_ranges;
00139 
00140     for ( ; data_iter.valid(); ++data_iter) {
00141     Statement &stmt = data_iter.current_key();
00142 
00143     if (&stmt == &representative_stmt(stmt)) {
00144         SSAControlRangeData &data = data_iter.current_data();
00145 
00146         /// ...  RefSet<Symbol> *vars = data.range_vars();
00147         /// ...  Iterator<Symbol> var_iter = *vars;
00148         /// ...  
00149         /// ...  for ( ; var_iter.valid(); ++var_iter)
00150         /// ...      data.get_range_ref(var_iter.current());
00151         //
00152         /// ...  delete vars;
00153         
00154         KeyIterator<Symbol,Statement> var_iter = ((SSAProgramUnit *) _pgm_ref)->_def_map;
00155 
00156         for ( ; var_iter.valid(); ++var_iter) {
00157         const Symbol &var = var_iter.current_key();
00158 
00159         if (var.type().data_type() == INTEGER_TYPE && ! var.is_array())
00160             data.get_range_ref(var);
00161         }
00162     }
00163     }
00164 }
00165 
00166 
00167 /// num_icdoms
00168 
00169 void
00170 SSAControlRangeDict::stats(float &avg_num_icdoms, int &max_num_icdoms,
00171                int &tot_num_icdoms,
00172                float &avg_num_ranges, int &max_num_ranges,
00173                int &tot_num_ranges)
00174 {
00175     touch();
00176 
00177     max_num_icdoms = 0;
00178     tot_num_icdoms = 0;
00179     max_num_ranges = 0;
00180     tot_num_ranges = num_computed_ranges();
00181     clear_ranges(); 
00182 
00183     int sum_num_icdoms = 0;
00184     int sum_num_ranges = 0;
00185 
00186     KeyIterator<Statement, SSAControlRangeData> data_iter = _stmt_ranges;
00187 
00188     for ( ; data_iter.valid(); ++data_iter) {
00189     Statement &stmt = data_iter.current_key();
00190 
00191     if (&stmt == &representative_stmt(stmt)) {
00192         SSAControlRangeData &data = data_iter.current_data();
00193         KeyIterator<Symbol,Statement> var_iter = ((SSAProgramUnit *) _pgm_ref)->_def_map;
00194 
00195         for ( ; var_iter.valid(); ++var_iter) {
00196         const Symbol &var = var_iter.current_key();
00197 
00198         if (var.type().data_type() == INTEGER_TYPE
00199             && ! var.is_array()) {
00200 
00201             int num_ranges = 0;
00202             int num_icdoms = 0;
00203             data.get_range_ref(var);
00204             SSAControlRangeData *cdom = data.icdom_ref();
00205 
00206             if (cdom)
00207             ++tot_num_icdoms;
00208             
00209             while (cdom) {
00210             ++num_icdoms;
00211             num_ranges += cdom->num_computed_ranges();
00212             cdom = cdom->icdom_ref();
00213             }
00214             
00215             sum_num_icdoms += num_icdoms;
00216             max_num_icdoms = max(max_num_icdoms, num_icdoms);
00217             
00218             sum_num_ranges += num_ranges;
00219             max_num_ranges = max(max_num_ranges, num_ranges);
00220 
00221             /// ...  Clear out all the ranges in my data object,
00222             /// ...  but keep the icdoms intact.
00223 
00224             cdom = &data;
00225 
00226             while (cdom) {
00227             SSAControlRangeData *next = cdom->icdom_ref();
00228             cdom->clear_ranges();
00229             cdom = next;
00230             }
00231 
00232             _range_set.clear();
00233         }
00234         }
00235     }
00236     }
00237 
00238     if (tot_num_ranges > 0) {
00239     avg_num_icdoms = (float) sum_num_icdoms / (float) tot_num_ranges;
00240     avg_num_ranges = (float) sum_num_ranges / (float) tot_num_ranges;
00241     }
00242     else {
00243     avg_num_icdoms = 0;
00244     tot_num_ranges = 0;
00245     }
00246 }
00247 
00248 
00249 /// num_ranges
00250 
00251 int
00252 SSAControlRangeDict::num_computed_ranges() const
00253 {
00254     int num_ranges = 0;
00255     KeyIterator<Statement, SSAControlRangeData> iter = _stmt_ranges;
00256 
00257     for ( ; iter.valid(); ++iter)
00258     num_ranges += iter.current_data().num_computed_ranges();
00259 
00260     return num_ranges;
00261 }
00262 
00263 
00264 /// representative_stmt
00265 
00266 const Statement &
00267 SSAControlRangeDict::representative_stmt(const Statement &stmt) const
00268 {
00269     const Statement *rep = 0;
00270 
00271     SSAControlRangeData *data = CASTAWAY(SSAControlRangeData *)(_stmt_ranges.find_ref(stmt));
00272 
00273     if (data) {
00274     rep = data->icdom_succ_ref();
00275 
00276     if (! rep)
00277         rep = _pgm_ref->stmts().first_ref();
00278     }
00279 
00280     p_assert(rep, "Couldn't determine a representative for the given stmt.");
00281 
00282     return *rep;
00283 }
00284 
00285 
00286 /// range_vars
00287 
00288 RefSet<Symbol> *
00289 SSAControlRangeDict::range_vars(const Statement &stmt) const
00290 {
00291     const SSAControlRangeData *data = _stmt_ranges.find_ref(stmt);
00292 
00293     if (data)
00294     return (CASTAWAY(SSAControlRangeData *)data)->range_vars();
00295 
00296     return new RefSet<Symbol>;
00297 }
00298 
00299 
00300 /// set_range
00301 
00302 void
00303 SSAControlRangeDict::_set_range(const Symbol &var,
00304             const Statement &stmt, Expression *range)
00305 {
00306     p_abort("Ranges cannot be modified in a SSAControlRangeDict object.");
00307 }
00308 
00309   
00310 
00311 /// del_range
00312 
00313 void
00314 SSAControlRangeDict::_del_range(const Symbol &var, const Statement &stmt)
00315 {
00316     p_abort("Ranges cannot be modified in a SSAControlRangeDict object.");
00317 }
00318 
00319 
00320 
00321 /// get_range_ref
00322 
00323 const Expression *
00324 SSAControlRangeDict::_get_range_ref(const Symbol &var, const Statement &stmt) 
00325 {
00326     SSAControlRangeData *data = CASTAWAY(SSAControlRangeData *)(_stmt_ranges.find_ref(stmt));
00327 
00328     if (data)
00329     return data->get_range_ref(var);
00330 
00331     return 0;
00332 }
00333 
00334 
00335 /// clear
00336 
00337 void
00338 SSAControlRangeDict::clear()
00339 {
00340     KeyIterator<Statement, SSAControlRangeData> iter = _stmt_ranges;
00341 
00342     for ( ; iter.valid(); ++iter)
00343     iter.current_data().clear();
00344 
00345     _range_set.clear();
00346 }
00347 
00348 
00349 /// range_clear
00350 
00351 void
00352 SSAControlRangeDict::clear_ranges()
00353 {
00354     KeyIterator<Statement, SSAControlRangeData> iter = _stmt_ranges;
00355 
00356     for ( ; iter.valid(); ++iter)
00357     iter.current_data().clear_ranges();
00358 
00359     _range_set.clear();
00360 }
00361 
00362 
00363 /// print
00364 
00365 void
00366 SSAControlRangeDict::print(ostream & o) const
00367 {
00368     KeyIterator<Statement, SSAControlRangeData> iter = _stmt_ranges;
00369 
00370     for ( ; iter.valid(); ++iter) {
00371     o << iter.current_key().tag() << ": ";
00372     iter.current_key().print_debug(o, 0);
00373     o << endl;
00374         o << "    " << iter.current_data() << endl;
00375     }
00376 }
00377 
00378 
00379 /// pretty_print
00380 
00381 void
00382 SSAControlRangeDict::pretty_print(ostream & o, const Statement &stmt) const
00383 {
00384     SSAControlRangeData *data = CASTAWAY(SSAControlRangeData *)(_stmt_ranges.find_ref(stmt));
00385 
00386     if (! data)
00387     o << "{}";
00388     else {
00389     RefSet<Symbol> *vars = data->range_vars();
00390     RefList<Symbol> sorted_keys;
00391     Iterator<Symbol> c_iter = *vars;
00392 
00393     for ( ; c_iter.valid(); ++c_iter)
00394         sorted_keys.ins_last(c_iter.current());
00395 
00396     delete vars;
00397     sort_sym_list(sorted_keys);
00398     Iterator<Symbol> key_iter = sorted_keys;
00399     bool first = true;
00400     
00401     o << "{";
00402 
00403     for ( ; key_iter.valid(); ++key_iter) {
00404         if (! first)
00405         o << ", ";
00406         else
00407         first = false;
00408         
00409         const Symbol &var = key_iter.current();
00410         const Expression &value = *data->get_range_ref(var);
00411         pretty_print_range(o, value, var);
00412     }
00413     
00414     o << "}";
00415     }
00416 }
00417 
00418 
00419 /// listable_clone
00420 
00421 Listable *
00422 SSAControlRangeDict::listable_clone(void) const
00423 {
00424     p_abort("SSAControlRangeDicts cannot be duplicated.");
00425     return 0;
00426 }
00427 
00428 
00429 
00430 /// structures_OK
00431 
00432 int
00433 SSAControlRangeDict::structures_OK() const
00434 {
00435     return (_stmt_ranges.structures_OK());
00436 }