Polaris: GSAControlRangeDict.cc Source File

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