Polaris: AliasSets.cc Source File

00001 ///
00002 ///
00003 /// \file AliasSets.cc
00004 ///
00005 #include "../Collection/Map.h"
00006 #include "../Collection/RefMap.h"
00007 #include "../Collection/RefSet.h"
00008 #include "../Collection/Iterator.h"
00009 #include "../Collection/KeyIterator.h"
00010 #include "../utilities/equivalence_util.h"
00011 
00012 #include "AliasSets.h"
00013 
00014 /// Template instantiations:
00015 
00016 template class TypedBaseMap<Symbol,UnionFindSetElem>;
00017 template class ProtoMap<Symbol,UnionFindSetElem>;
00018 template class Map<Symbol,UnionFindSetElem>;
00019 template ostream & operator << (ostream &,
00020                                 const Map<Symbol,UnionFindSetElem> &);
00021 template class KeyIterator<Symbol,UnionFindSetElem>;
00022 
00023 template class TypedBaseRefMap<UnionFindSetElem,UnionFindSetElem>;
00024 template class ProtoRefMap<UnionFindSetElem,UnionFindSetElem>;
00025 template class RefMap<UnionFindSetElem,UnionFindSetElem>;
00026 template ostream & operator << (ostream &,
00027                                 const RefMap<UnionFindSetElem,UnionFindSetElem> &);
00028 template class KeyIterator<UnionFindSetElem,UnionFindSetElem>;
00029 
00030 template class TypedBaseMap<UnionFindSetElem,RefSet<Symbol> >;
00031 template class ProtoMap<UnionFindSetElem,RefSet<Symbol> >;
00032 template class Map<UnionFindSetElem,RefSet<Symbol> >;
00033 template ostream & operator << (ostream &,
00034                                 const Map<UnionFindSetElem,RefSet<Symbol> > &);
00035 template class KeyIterator<UnionFindSetElem, RefSet<Symbol> >;
00036 
00037 
00038 ///  Constructors
00039 
00040 AliasSets::AliasSets()
00041 {
00042     /// ...  Nothing to do.
00043 }
00044 
00045 AliasSets::AliasSets(AliasSets &other)
00046 {
00047     RefMap<UnionFindSetElem, UnionFindSetElem> rep_map;
00048 
00049     KeyIterator<Symbol, UnionFindSetElem> iter = other._alias_sets;
00050     
00051     /// ...  Copy the other objects elements to myself.
00052     
00053     for ( ; iter.valid(); ++iter) {
00054     UnionFindSetElem *elem = new UnionFindSetElem();
00055     _alias_sets.ins(iter.current_key(), elem);
00056     rep_map.ins(iter.current_data(), *elem);
00057     }
00058     
00059     /// ...  Build my set relationships so that they resemble the other
00060     /// ...  object's set relationsips.
00061     
00062     for (iter = _alias_sets; iter.valid(); ++iter)
00063     iter.current_data().union_sets(
00064         rep_map[other._alias_sets[iter.current_key()].find_set()]);
00065 }
00066 
00067 
00068 ///  Destructor
00069 
00070 AliasSets::~AliasSets()
00071 {
00072     /// ...  Nothing to do.
00073 }
00074 
00075 
00076 ///  get_elem
00077 
00078 UnionFindSetElem &
00079 AliasSets::_get_elem(const Symbol &var)
00080 {
00081     UnionFindSetElem *elem = _alias_sets.find_ref(var);
00082 
00083     if (! elem) {
00084     elem = new UnionFindSetElem;
00085     _alias_sets.ins(var, elem);
00086 
00087     /// ...  Also place any aliased variables in the set.
00088     
00089     RefSet<Symbol> *aliases = equiv_aliases(var);
00090     
00091     if (aliases) {
00092         Iterator<Symbol> alias_iter = *aliases;
00093         
00094         for ( ; alias_iter.valid(); ++alias_iter)
00095         alias(var, alias_iter.current());
00096         
00097         delete aliases;
00098     }
00099     }
00100 
00101     return *elem;
00102 }
00103  
00104 
00105 ///  alias
00106 
00107 void
00108 AliasSets::alias(const Symbol &var1, const Symbol &var2)
00109 {
00110     _get_elem(var1).union_sets(_get_elem(var2));
00111 }
00112 
00113 
00114 ///  alias
00115 
00116 void
00117 AliasSets::alias(const RefList<Symbol> &formals,
00118          const List<Expression> &actuals)
00119 {
00120     p_assert(formals.entries() == actuals.entries(),
00121          "AliasSets::alias():  The number of formals does not equal the number of actuals.");
00122     Iterator<Symbol> formal_iter = formals;
00123     Iterator<Expression> actual_iter = actuals;
00124 
00125     for ( ; formal_iter.valid(); ++formal_iter, ++actual_iter) {
00126     const Symbol &formal = formal_iter.current();
00127     const Symbol *actual = actual_iter.current().base_variable_ref();
00128 
00129     if (actual)
00130         alias(formal, *actual);
00131     }
00132 }
00133 
00134 
00135 ///  aliases
00136 
00137 RefSet<Symbol> *
00138 AliasSets::aliases(const Symbol &var)
00139 {
00140     RefSet<Symbol> *alias_vars = new RefSet<Symbol>;
00141     UnionFindSetElem *elem = _alias_sets.find_ref(var);
00142 
00143     if (elem) {
00144     UnionFindSetElem &rep_elem = elem->find_set();
00145 
00146     KeyIterator<Symbol, UnionFindSetElem> iter = _alias_sets;
00147 
00148     for ( ; iter.valid(); ++iter)
00149         if (&iter.current_data().find_set() == &rep_elem
00150         && &iter.current_key() != &var)
00151 
00152         alias_vars->ins(iter.current_key());
00153     }
00154 
00155     return alias_vars;
00156 }
00157 
00158 RefSet<Symbol> *
00159 AliasSets::aliases(const Symbol &var, const RefSet<Symbol> &filter_vars)
00160 {
00161     RefSet<Symbol> *alias_vars = aliases(var);
00162 
00163     Mutator<Symbol> iter = *alias_vars;
00164 
00165     for ( ; iter.valid(); ++iter)
00166     if (! filter_vars.member(iter.current()))
00167         iter.del();
00168 
00169     return alias_vars;
00170 }
00171 
00172 
00173 ///  print
00174 
00175 void
00176 _print(ostream &o, const RefSet<Symbol> &vars)
00177 {
00178     o << "{";
00179     Iterator<Symbol> iter = vars;
00180 
00181     if (iter.valid()) {
00182     o << iter.current().name_ref();
00183     ++iter;
00184 
00185     for ( ; iter.valid(); ++iter)
00186         o << ", " << iter.current().name_ref();
00187     }
00188 
00189     o << "}";
00190 }
00191     
00192 void 
00193 AliasSets::print(ostream &o)
00194 {
00195     Map<UnionFindSetElem, RefSet<Symbol> > all_aliases;
00196     KeyIterator<Symbol, UnionFindSetElem> iter = _alias_sets;
00197 
00198     for ( ; iter.valid(); ++iter)
00199     if (&iter.current_data() == &iter.current_data().find_set())
00200         all_aliases.ins(iter.current_data(), new RefSet<Symbol>);
00201 
00202     for (iter.reset(); iter.valid(); ++iter)
00203     all_aliases[iter.current_data().find_set()].ins(iter.current_key());
00204 
00205     o << "{";
00206     KeyIterator<UnionFindSetElem, RefSet<Symbol> > set_iter = all_aliases;
00207 
00208     if (set_iter.valid()) {
00209     _print(o, set_iter.current_data());
00210     ++set_iter;
00211 
00212     for ( ; set_iter.valid(); ++set_iter) {
00213         o << ", ";
00214         _print(o, set_iter.current_data());
00215     }
00216     }
00217 
00218     o << "}";
00219 }
00220 
00221