Polaris: DDgraph.cc Source File

DDgraph.cc Go to the documentation of this file. #include "define.h" /// #ifdef POLARIS_GNU_PRAGMAS #pragma implementation #endif /// #include "DDgraph.h" template class TypedCollection<ActiveArc>; template class List<ActiveArc>; template ostream & operator << (ostream &, const List<ActiveArc> &); template class Iterator<ActiveArc>; template class Assign<ActiveArc>; template class TypedCollection<DVfield>; template class List<DVfield>; template ostream & operator << (ostream &, const List<DVfield> &); template class Iterator<DVfield>; template class Mutator<DVfield>; template class Assign<DVfield>; template class TypedCollection<ElementDV>; template class List<ElementDV>; template ostream & operator << (ostream &, const List<ElementDV> &); template class Iterator<ElementDV>; template class Assign<ElementDV>; template class TypedCollection<List<ElementDV> >; template class List<List<ElementDV> >; template ostream & operator << (ostream &, const List<List<ElementDV> > &); template class Assign<List<ElementDV> >; template class Iterator<List<ElementDV> >; template class Mutator<List<ElementDV> >; template class TypedCollection< List<DVfield> >; template class List< List<DVfield> >; template ostream & operator << (ostream &, const List< List<DVfield> > &); template class Iterator< List<DVfield> >; template class Mutator< List<DVfield> >; template class Assign< List<DVfield> >; #define _SLOT(stars, combos) 2 * stars + combos /// Calculate the slot number with the values of stars and combos where /// combo direction is '<=', '>=' & '<>'. single direction is '<', '>' & '='. /// And star is '*'... This _SLOT is used in 'merge_DVs' only.. void merge_DVs(List<DVfield> & dvfs) { List<DVfield> original_dvfs; List<DVfield> work_dvfs; Mutator<DVfield> copy_iter = dvfs; /// Iterator<DVfield> copy_iter(&dvfs); for (; copy_iter.valid(); ++copy_iter) original_dvfs.ins_last(copy_iter.grab()); /// Now, 'dvfs' is empty and the original list is stored in 'original_dvfs' Mutator<DVfield> iter = original_dvfs; for(; iter.valid(); iter.reset()) { DVfield * dvf = iter.grab(); work_dvfs.ins_first(dvf); for (++iter; iter.valid(); ++iter) if (dvf->dv().entries() == iter.current().dv().entries() && dvf->dep_decided() == iter.current().dep_decided() && dvf->dep_type() == iter.current().dep_type() && &dvf->from_expr() == &iter.current().from_expr() && &dvf->to_expr() == &iter.current().to_expr()) work_dvfs.ins_last(iter.grab()); /// ... The DV fields with the same dimension of their direction vectors /// ... are now collected in 'work_dvfs' grabbed from 'original_dvfs' int levels = dvf->dv().entries() * 2; DVcapsule **Slots = new DVcapsule* [levels + 1]; /// ... One more slot allocated for Top level direction (*,*,...,*) int i; for (i = 0; i <= levels; i++) Slots[i] = 0; /// ... Initialized to be empty Mutator<DVfield> diter = work_dvfs; /// ... Encapsulate each DVfield node in a DVcapsule and /// ... store it in the appropriatte slot. for (; diter.valid(); ++diter) { Iterator<ElementDV> eiter = diter.current().dv(); int num_of_stars = 0; int num_of_combos = 0; for (; eiter.valid(); ++eiter) switch (eiter.current().direction()) { case _STAR: num_of_stars++; break; case _LE: case _GE: case _NEQ: num_of_combos++; default: break; } int slot = _SLOT(num_of_stars, num_of_combos); DVcapsule * dvc = Slots[slot]; Slots[slot] = new DVcapsule(diter.grab()); Slots[slot]->next = dvc; } if (Slots[levels]) { /// ... Top level is not empty dvfs.ins_last(Slots[levels]->dvf); Slots[levels]->dvf = 0; for (; levels >= 0; levels--) _dispose_capsules(Slots[levels]); continue; /// ... Now back to the loop control: Skip } /// ... Now, do top-to-bottom search to eliminate all the subdirections. _remove_all_subdirections(Slots, levels); /// ... Now, do bottom-to-top search to find the minimal merged directions set /// ... Create parents with the DVfields in my slot DVcapsule * dvc; for (i = 0; i < levels; ++i) { for ( dvc = Slots[i]; dvc; dvc = dvc->next) { DVcapsule * compensatory = _create_parent(Slots[i + 1], dvc, dvc->next); if (compensatory && dvc->is_alive()) dvc->mark_dead(); while (compensatory) { compensatory->mark_dead(); compensatory = _create_parent(Slots[i + 1], dvc, compensatory->next); } } // Remove all the DVcapsules marked dead in this slot DVcapsule * prev = 0; dvc = Slots[i]; while (dvc) if (dvc->is_alive()) { prev = dvc; dvc = dvc->next; } else { /// ... dead delete dvc->dvf; if (prev) { prev->next = dvc->next; delete dvc; dvc = prev->next; } else { Slots[i] = dvc->next; delete dvc; dvc = Slots[i]; } } } /// ... Create parents with the DVfields in the child slot for (i = 1; i < levels; i++) { for ( dvc = Slots[i]; dvc; dvc = dvc->next) { DVcapsule * compensatory = _create_parent(Slots[i + 1], dvc, Slots[i - 1]); if (compensatory && dvc->is_alive()) dvc->mark_dead(); while (compensatory) { compensatory->mark_dead(); compensatory = _create_parent(Slots[i + 1], dvc, compensatory->next); } } /// ... Remove all the DVcapsules marked dead in this slot DVcapsule * prev = 0; dvc = Slots[i]; while (dvc) if (dvc->is_alive()) { prev = dvc; dvc = dvc->next; } else { /// ... dead delete dvc->dvf; if (prev) { prev->next = dvc->next; delete dvc; dvc = prev->next; } else { Slots[i] = dvc->next; delete dvc; dvc = Slots[i]; } } } /// ... Now, do top-to-bottom search to eliminate all the subdirections. _remove_all_subdirections(Slots, levels); /// ... Store all DVfields in the capsules alive for (i = 0; i < levels; i++) for (dvc = Slots[i]; dvc; dvc = dvc->next) { dvfs.ins_last(dvc->dvf); dvc->dvf = 0; } /// ... Clean up /* work_dvfs.clear(); */ for (i = 0; i < levels; i++) _dispose_capsules(Slots[i]); delete[] Slots; } } /// ... merge_DVs() void _dispose_capsules(DVcapsule *& dvc) { if (dvc) { _dispose_capsules(dvc->next); delete dvc->dvf; delete dvc; dvc = 0; } } DVcapsule * _create_parent(DVcapsule *& Slot, DVcapsule * dvc, DVcapsule * list) { Iterator<ElementDV> iter = dvc->dvf->dv(); ElementDV * new_dir = 0; for (; list; iter.reset(), list = list->next) { Iterator<ElementDV> riter = list->dvf->dv(); Binary_flag all_the_same = 1; int loc_count = 0; for (; riter.valid() && iter.valid(); ++iter, ++riter) { if (iter.current().direction() != riter.current().direction()) { if (all_the_same) all_the_same = 0; else break; /// ... Only one different direction allowed switch (iter.current().direction()) { case _LT: if (riter.current().direction() == _GT) new_dir = new ElementDV(_NEQ); else if (riter.current().direction() == _EQ) new_dir = new ElementDV(_LE); break; case _GT: if (riter.current().direction() == _LT) new_dir = new ElementDV(_NEQ); else if (riter.current().direction() == _EQ) new_dir = new ElementDV(_GE); break; case _EQ: if (riter.current().direction() == _GT) new_dir = new ElementDV(_GE); else if (riter.current().direction() == _LT) new_dir = new ElementDV(_LE); break; case _LE: if (riter.current().direction() == _GE || riter.current().direction() == _NEQ || riter.current().direction() == _GT) new_dir = new ElementDV(_STAR); break; case _GE: if (riter.current().direction() == _LE || riter.current().direction() == _NEQ || riter.current().direction() == _LT) new_dir = new ElementDV(_STAR); break; case _NEQ: if (riter.current().direction() == _GE || riter.current().direction() == _LE || riter.current().direction() == _EQ) new_dir = new ElementDV(_STAR); default: break; } if (!new_dir) break; } if (all_the_same) loc_count++; } if (new_dir && riter.end() && iter.end()) { /// ... Now, create new parent capsule node and add it to Slot DVfield * dvf = (DVfield *) dvc->dvf->listable_clone(); /* DVfield * dvf = new DVfield(dvc->dvf->dep_decided(), dvc->dvf->dep_type(), dvc->dvf->from_stmt(), dvc->dvf->from_expr(), dvc->dvf->to_stmt(), dvc->dvf->to_expr()); */ List<ElementDV> & dv = dvf->dv(); int i = 0; for (iter.reset(); iter.valid(); ++iter, ++i) if (i == loc_count) dv.ins_last(new_dir); else dv.ins_last(new ElementDV(iter.current().direction())); // Check if there is already the smae DVfield in Slot Iterator<ElementDV> new_iter = dv; DVcapsule * search; for ( search = Slot; search; search = search->next) { Iterator<ElementDV> siter = search->dvf->dv(); for (; new_iter.valid() && siter.valid(); ++new_iter, ++siter) if (new_iter.current().direction() != siter.current().direction()) break; if (new_iter.end() && siter.end()) break; new_iter.reset(); } if (search) delete dvf; else { DVcapsule * temp = Slot; Slot = new DVcapsule(dvf); Slot->next = temp; } return list; } } return 0; } Binary_flag _is_subdirecion(Iterator<ElementDV> & iter1, Iterator<ElementDV> & iter2) { iter1.reset(); iter2.reset(); for (; iter1.valid() && iter2.valid(); ++iter1, ++iter2) switch (iter2.current().direction()) { case _LT: if (iter1.current().direction() != _LT) return 0; break; case _GT: if (iter1.current().direction() != _GT) return 0; break; case _EQ: if (iter1.current().direction() != _EQ) return 0; break; case _LE: if (iter1.current().direction() != _LT && iter1.current().direction() != _EQ && iter1.current().direction() != _LE) return 0; break; case _GE: if (iter1.current().direction() != _GT && iter1.current().direction() != _EQ && iter1.current().direction() != _GE) return 0; break; case _NEQ: if (iter1.current().direction() != _GT && iter1.current().direction() != _LT && iter1.current().direction() != _NEQ) return 0; default: break; } if (iter1.end() && iter2.end()) return 1; else return 0; } Binary_flag _is_parent_for(Iterator<ElementDV> & citer, Iterator<ElementDV> & piter) { int how_many_cover = 0; citer.reset(); piter.reset(); for (; citer.valid() && piter.valid(); ++citer, ++piter) switch (piter.current().direction()) { case _LT: if (citer.current().direction() != _LT) return 0; break; case _GT: if (citer.current().direction() != _GT) return 0; break; case _EQ: if (citer.current().direction() != _EQ) return 0; break; case _LE: if (citer.current().direction() != _LT && citer.current().direction() != _EQ) return 0; how_many_cover++; break; case _GE: if (citer.current().direction() != _GT && citer.current().direction() != _EQ) return 0; how_many_cover++; break; case _NEQ: if (citer.current().direction() != _LT && citer.current().direction() != _GT) return 0; how_many_cover++; break; default: /// ... == _STAR if (citer.current().direction() != _STAR) how_many_cover++; } if (citer.end() && piter.end() && how_many_cover == 1) return 1; /// ... Every direction is the same but only one covered by parent else return 0; } void _remove_all_subdirections(DVcapsule ** Slots, int levels) { for (int i = levels - 1; i >= 0; i--) for (DVcapsule * dvc = Slots[i]; dvc; dvc = dvc->next) { /// ... Delete nonproper subexpressions, if any Iterator<ElementDV> eiter = dvc->dvf->dv(); DVcapsule * prev = dvc; DVcapsule * c = dvc->next; while (c) { Iterator<ElementDV> citer = c->dvf->dv(); if (_is_same(citer, eiter)) { prev->next = c->next; delete c->dvf; delete c; c = prev->next; } else { prev = c; c = c->next; } } for (int j = i - 1; j >= 0; j--) { prev = 0; c = Slots[j]; while (c) { Iterator<ElementDV> citer = c->dvf->dv(); if (_is_subdirecion(citer, eiter)) { delete c->dvf; if (prev) { prev->next = c->next; delete c; c = prev->next; } else { Slots[j] = c->next; delete c; c = Slots[j]; } } else { prev = c; c = c->next; } } } } } #define _MY_DDG_DEBUG ElementDV::~ElementDV() { /// Nothing to do } Listable * ElementDV::listable_clone() const { return new ElementDV(*this); } void ElementDV::print(ostream & o) const { char *dir = NULL; #ifdef _MY_DDG_DEBUG switch (_direction) { case _STAR: dir = "* "; break; case _LT: dir = "< "; break; case _GT: dir = "> "; break; case _LE: dir = "<="; break; case _GE: dir = ">="; break; case _NEQ: dir = "<>"; break; case _EQ: dir = "= "; default: break; } o << ' ' << dir ; #endif Boolean dist_valid = _distance_valid; if ((_min_distance == INV_DDIST) && (_max_distance == INV_DDIST)) dist_valid = False; if (dist_valid) { int min, max; min = (int) _min_distance; max = (int) _max_distance; if (_min_distance == _max_distance) { o << "D=" << min; } else { o << "D=["; if (_min_distance == INV_DDIST) o << "invalid"; else o << min; o << ","; if (_max_distance == INV_DDIST) o << "invalid"; else o << max; o << "] "; } } else o << " D=[invalid]"; } DVfield::~DVfield() { /// Nothing to do if(_label) delete _label; _label = NULL; } Listable * DVfield::listable_clone() const { return new DVfield(*this); } void DVfield::print(ostream & o) const { #ifdef _MY_DDG_DEBUG o << " /// ... DVF ref(" << _references << ")v(" << (int) _valid; switch (_dep_decided) { case _ASSUMED: o << ")as,"; break; case _PROVED: o << ")pv,"; default: break; } switch (_dep_type) { case _FLOW: o << "f,"; break; case _ANTI: o << "a,"; break; case _INPUT: o << "i,"; break; case _OUTPUT: o << "o,"; break; case _UNKNOWN: o << "u,"; } o << "f_e:"; _from_expr.print(o); o << "t_e:"; _to_expr.print(o); for (Iterator<ElementDV> iter = _dv; iter.valid(); ++iter) iter.current().print(o); o << " /// ... "; #endif if(_label) { o << "label: "; _label->print(o); o << endl; } else o << endl; } ActiveArc::~ActiveArc() { delete _original_dv_fields; /// if(_label) delete _label; } Listable * ActiveArc::listable_clone() const { return new ActiveArc(*this); } void ActiveArc::print(ostream & o) const { #ifdef _MY_DDG_DEBUG o << " { AArefs=" << _references << " p_arc=" << _prev_arc; o << " n_arc=" << _next_arc << " arc=" << _this_arc << endl; o << " source_e:"; _source_expr.print(o); o << " target_e:"; _target_expr.print(o); o << endl; Iterator<DVfield> iter = _working_dv_fields; for ( ; iter.valid(); ++iter) iter.current().print(o); /// CC 06/15/98 o << "(label: "; /// ( _label != NULL ) ? _label->print(o) : o << "NULL"; if ( _label == NULL ) { o << "NULL"; } else { _label->print( o ); } o << ")"; o << " }\n"; /// CC end #endif } /*----------------------------------------------------------*/ Binary_flag DDgraph::is_new_dvfield(Arc_type * &arc_field, int &position) { Binary_flag temp = (Binary_flag) (*arc_field << position & ARC_1_BIT); if ((position += ONE_BIT) == A_BYTE) { position = 0; arc_field++; } return temp; } DEP_DECISION DDgraph::dep_decision(Arc_type * &arc_field, int &position) { DEP_DECISION temp = (DEP_DECISION) (*arc_field << position & ARC_1_BIT); if ((position += ONE_BIT) == A_BYTE) { position = 0; arc_field++; } return temp; } DEP_DIREC DDgraph::dep_direction(Arc_type * &arc_field, int &position) { DEP_DIREC temp = (DEP_DIREC) (*arc_field << position & ARC_1_BIT); if ((position += ONE_BIT) == A_BYTE) { position = 0; arc_field++; } return temp; } DEP_TYPE DDgraph::dep_type(Arc_type * &arc_field, int &position) { Arc_type temp = *arc_field << position & ARC_2_BIT; if ((position += TWO_BIT) >= A_BYTE) { position -= A_BYTE; arc_field++; temp |= *arc_field >> position & ARC_2_BIT; } return (DEP_TYPE) temp; } DIREC_TYPE DDgraph::direction(Arc_type * &arc_field, int &position) { Arc_type temp = *arc_field << position & ARC_3_BIT; if ((position += THREE_BIT) >= A_BYTE) { position -= A_BYTE; arc_field++; temp |= *arc_field >> (THREE_BIT - position) & ARC_3_BIT; } return (DIREC_TYPE) temp; } DDIST_TYPE DDgraph::min_distance(Arc_type * &arc_field, int &position) { Arc_type temp = *arc_field << position & ARC_8_BIT; arc_field++; /// ... will always be in the next byte temp |= *arc_field >> (EIGHT_BIT - position) & ARC_8_BIT; return (DDIST_TYPE) temp; } DDIST_TYPE DDgraph::max_distance(Arc_type * &arc_field, int &position) { Arc_type temp = *arc_field << position & ARC_8_BIT; arc_field++; /// ... will always be in the next byte temp |= *arc_field >> (EIGHT_BIT - position) & ARC_8_BIT; return (DDIST_TYPE) temp; } void DDgraph::mark_new_dvfield(Arc_type * &arc_field, int &position) { *arc_field |= ARC_1_BIT >> position; if ((position += ONE_BIT) == A_BYTE) { position = 0; arc_field++; } } void DDgraph::mark_arc_end(Arc_type * &arc_field, int &position) { *arc_field &= ~(ARC_1_BIT >> position); if ((position += ONE_BIT) == A_BYTE) { position = 0; arc_field++; } } void DDgraph::store_dep_decision(Arc_type * &arc_field, int &position, DEP_DECISION ddeci) { *arc_field |= (Arc_type) ddeci >> position; if ((position += ONE_BIT) == A_BYTE) { position = 0; arc_field++; } } void DDgraph::store_dep_direction(Arc_type * &arc_field, int &position, DEP_DIREC ddirec) { *arc_field |= (Arc_type) ddirec >> position; if ((position += ONE_BIT) == A_BYTE) { position = 0; arc_field++; } } void DDgraph::store_dep_type(Arc_type * &arc_field, int &position, DEP_TYPE deptype) { *arc_field |= (Arc_type) deptype >> position; if ((position += TWO_BIT) >= A_BYTE) { position -= A_BYTE; arc_field++; if (position) *arc_field |= (Arc_type) deptype << position; /// ... --> TWO_BIT - position } } void DDgraph::store_direction(Arc_type * &arc_field, int &position, DIREC_TYPE direct) { *arc_field |= (Arc_type) direct >> position; if ((position += THREE_BIT) >= A_BYTE) { position -= A_BYTE; arc_field++; if (position) *arc_field |= (Arc_type) direct << (THREE_BIT - position); } } void DDgraph::store_min_distance(Arc_type * &arc_field, int &position, DDIST_TYPE min_dist) { *arc_field |= (Arc_type) min_dist >> position; arc_field++; /// ... position will always be in the next byte if (position) /// ... bits that fill off after the shift *arc_field |= (Arc_type) min_dist << (EIGHT_BIT - position); } void DDgraph::store_max_distance(Arc_type * &arc_field, int &position, DDIST_TYPE max_dist) { *arc_field |= (Arc_type) max_dist >> position; arc_field++; /// ... position will always be in the next byte if (position) /// ... bits that fill off after the shift *arc_field |= (Arc_type) max_dist << (EIGHT_BIT - position); } void DDgraph::store_const_distance(Arc_type * &arc_field, int &position, DDIST_TYPE const_dist) { *arc_field |= (Arc_type) const_dist >> position; arc_field++; /// ... position will always be in the next byte if (position) /// ... bits that fill off after the shift *arc_field |= (Arc_type) const_dist << (EIGHT_BIT - position); } //------------------------------------------------ void DDgraph::initialize_this_active_arc(ActiveArc * aarc, Arc_type * arc) { int pos = 1; /// ... passing by active_field activate(arc); aarc->_references = 1; /// ... for the DDiterator initially pointing to this /// ... Generate List<DVfield> _working_dv_fields arc = data_field(arc); while (is_new_dvfield(arc, pos)) { DVfield *dvf; DEP_DECISION ddeci = dep_decision(arc, pos); if (_NORMAL == dep_direction(arc, pos)) { dvf = new DVfield(ddeci, dep_type(arc, pos), aarc->_source_stmt, aarc->_source_expr, aarc->_target_stmt, aarc->_target_expr); } else { /// ... _REVERSE dvf = new DVfield(ddeci, dep_type(arc, pos), aarc->_target_stmt, aarc->_target_expr, aarc->_source_stmt, aarc->_source_expr); } /// ... Generate List<ElementDV> _dv DIREC_TYPE dir; DDIST_TYPE min_dist; DDIST_TYPE max_dist; while ((dir = direction(arc, pos)) != _DELIM) { min_dist = min_distance(arc, pos); max_dist = max_distance(arc, pos); if ( (min_dist == INV_DDIST) || (max_dist == INV_DDIST) ) dvf->dv().ins_last(new ElementDV(dir)); else dvf->dv().ins_last(new ElementDV(dir, min_dist, max_dist)); } if (!dvf->dv().entries()) { /// ... DVfield with NULL DV is assumed to /// ... have UNKNOWN dependence type dvf->dep_type(_UNKNOWN); } aarc->_working_dv_fields.ins_last(dvf); } /// ... Provide a cache _original_dv_fields for original DVfields /* aarc->_original_dv_fields = new List<DVfield>(aarc->_working_dv_fields); */ //--------------- aarc->_original_dv_fields = new List<DVfield>; Iterator<DVfield> witer = aarc->_working_dv_fields; for (; witer.valid(); ++witer) { DVfield & d = witer.current(); DVfield * new_dvf = (DVfield *) d.listable_clone(); /* DVfield * new_dvf = new DVfield(d._dep_decided, d._dep_type, d._from_stmt, d._from_expr, d._to_stmt, d._to_expr); */ aarc->_original_dv_fields->ins_last(new_dvf); Iterator<ElementDV> eiter = d.dv(); for (; eiter.valid(); ++eiter) new_dvf->dv().ins_last(new ElementDV(eiter.current())); } //--------------- } /// ... initialize_this_active_arc() void DDgraph::search_active_arcs_for(DVfield * &dvf, ActiveArc * &active_arc, First_Last fl, DEP_DIREC ddirec, const Expression & from_expr, const Expression & to_expr) { Iterator<ActiveArc> iter = _active_arcs; if (ddirec == _NORMAL) { /// ... from == source, to == target while (&iter.current()._source_expr != &from_expr || &iter.current()._target_expr != &to_expr) ++iter; } else { while (&iter.current()._source_expr != &to_expr || &iter.current()._target_expr != &from_expr) ++iter; } /// ... Now, iter.current() is the active_arc; Iterator<DVfield> dv_iter = iter.current()._working_dv_fields; dvf = NULL; if (fl == _FIRST) { for (; dv_iter.valid(); ++dv_iter) { if (&dv_iter.current()._to_expr == &to_expr && dv_iter.current()._valid) { /// ... 1st DVfield found which satisfy the condition active_arc = &iter.current(); dvf = &dv_iter.current(); active_arc->_references++; dvf->references_inc(); break; } } } else { /// ... == _LAST for (dv_iter.set_to_last(); dv_iter.valid(); --dv_iter) { if (&dv_iter.current()._to_expr == &to_expr && dv_iter.current()._valid) { /// ... 1st DVfield found which satisfy the condition active_arc = &iter.current(); dvf = &dv_iter.current(); active_arc->_references++; dvf->references_inc(); break; } } } } /// ... search_active_arcs_for() void DDgraph::update_links_between(Arc_type * new_this, ActiveArc * active_arc) { Arc_type *prev = active_arc->_prev_arc; Arc_type *next = active_arc->_next_arc; /// ... for prev_arc and this_arc link if (prev) { if (is_active(prev)) { Iterator<ActiveArc> aa_iter = _active_arcs; for (; aa_iter.valid(); ++aa_iter) { if (aa_iter.current()._this_arc == prev) { aa_iter.current()._next_arc = new_this; break; } } } else { /// ... inactive store_next_arc(prev, new_this); } } else { /// ... NULL if (active_arc->_source_expr.op() == ARRAY_REF_OP) ((ArrayRefExpr &) active_arc->_source_expr)._arcs = new_this; else { /// ... Must be ID_Expr ((IDExpr &) active_arc->_source_expr)._arcs = new_this; } } /// ... for next_arc and this_arc link if (next && is_active(next)) { /// ... not NULL & active Iterator<ActiveArc> aa_iter = _active_arcs; for (; aa_iter.valid(); ++aa_iter) { if (aa_iter.current()._this_arc == next) { aa_iter.current()._prev_arc = new_this; break; } } } } /// ... update_links_between() void DDgraph::write_back_arc(ActiveArc * active_arc) { Iterator<DVfield> iter = active_arc->_working_dv_fields; Mutator<DVfield> o_iter = *active_arc->_original_dv_fields; int w_bits, o_bits; // size of working/original DVfields in bits Arc_type *arc; o_bits = w_bits = _ptr_size * NUM_OF_PTRS + 1; /// ... For tgt_stmt, tgt_expr, label, next_arc & active_field for (; iter.valid(); ++iter) { /// ... for New mark(1), Dep_Deci, Dep_Direc, Dep_type, End mark(000) /// ... and 3 bits for each direction w_bits += CONST_BITS + iter.current()._dv.entries() * (THREE_BIT + EIGHT_BIT + EIGHT_BIT); } for (; o_iter.valid(); ++o_iter) { /// ... for New mark(1), Dep_Deci, Dep_Direc, Dep_type, End mark(000) /// ... and 3 bits for each direction o_bits += CONST_BITS + o_iter.current()._dv.entries() * (THREE_BIT+ EIGHT_BIT + EIGHT_BIT); } if (w_bits == o_bits) { /// ... Very likey that No change in working_DVfields for (iter.reset(); iter.valid(); ++iter) { for (o_iter.reset(); o_iter.valid(); ++o_iter) { if (&iter.current()._from_expr == &o_iter.current()._from_expr && &iter.current()._to_expr == &o_iter.current()._to_expr && iter.current()._dep_decided == o_iter.current()._dep_decided && iter.current()._dep_type == o_iter.current()._dep_type) { Iterator<ElementDV> wdv_iter = iter.current()._dv; Iterator<ElementDV> odv_iter = o_iter.current()._dv; for (; wdv_iter.valid() && odv_iter.valid(); ++wdv_iter, ++odv_iter) { if ( (wdv_iter.current().direction() != odv_iter.current().direction()) || (wdv_iter.current().min_distance() != odv_iter.current().min_distance()) || (wdv_iter.current().max_distance() != odv_iter.current().max_distance()) ) break; } if (wdv_iter.end() && odv_iter.end()) { /// ... The same DVfield with the original o_iter.del(); break; } } } if (o_iter.end()) { /// ... working_dv_fields & original copy are /// ... not the same break; } } if (iter.valid()) { /// ... Same size but diffrenet contents arc = active_arc->_this_arc; store_next_arc(arc, active_arc->_next_arc); } else { /// ... No change deactivate(active_arc->_this_arc); arc = 0; } } else if (Bytes(w_bits) == Bytes(o_bits)) { /// ... Same size but diffrenet contents arc = active_arc->_this_arc; store_next_arc(arc, active_arc->_next_arc); } else { /// ... Diffrent size, therefore different contents too arc = new Arc_type[Bytes(w_bits)]; /// ... Copy 3 pointers into arc: the remaining field will be /// ... written later for (int i = 0; i<_next_arc_offset; ++i) arc[i] = *(active_arc->_this_arc + i); store_next_arc(arc, active_arc->_next_arc); /// ... Update the link structure around 'arc' update_links_between(arc, active_arc); if(arcs_ptr(active_arc->_source_expr) == active_arc->_this_arc) { if (active_arc->_source_expr.op() == ID_OP) ((IDExpr &) active_arc->_source_expr)._arcs = 0; else if (active_arc->_source_expr.op() == ARRAY_REF_OP) ((ArrayRefExpr &) active_arc->_source_expr)._arcs = 0; } delete active_arc->_this_arc; active_arc->_this_arc = 0; } if (arc) { /// ... Fill up 'arc' with the contents of working_dv_fields int pos = 1; /// ... passing by the active bit arc = data_field(arc); _clear_arc(arc, Bytes(w_bits) - _data_field_offset); /// ... Automatically, deactivate this arc for (iter.reset(); iter.valid(); ++iter) { mark_new_dvfield(arc, pos); store_dep_decision(arc, pos, iter.current()._dep_decided); if (&active_arc->_source_expr == &iter.current()._from_expr) store_dep_direction(arc, pos, _NORMAL); else store_dep_direction(arc, pos, _REVERSE); store_dep_type(arc, pos, iter.current()._dep_type); Iterator<ElementDV> dv_iter = iter.current()._dv; for (; dv_iter.valid(); ++dv_iter) { store_direction(arc, pos, dv_iter.current().direction()); store_min_distance(arc, pos, dv_iter.current().min_distance()); store_max_distance(arc, pos, dv_iter.current().max_distance()); } store_direction(arc, pos, _DELIM); } mark_arc_end(arc, pos); } _active_arcs.del(*active_arc); } /// ... End of write_back_arc() void DDgraph::compute_dvf_n_arc(DVfield * &dvf, ActiveArc * &active_arc, First_Last fl, const Statement & from_stmt, const Expression & from_expr, const Statement & to_stmt, const Expression & to_expr) { Arc_type *prev_arc, *arc; /// ... Arc_type *arc_data = NULL; dvf = NULL; /// ... Try to find an arc with from_expr as a source expression first prev_arc = NULL; for (arc = arcs_ptr(from_expr); arc; arc = next_arc(arc)) { if (&to_expr != target_expr(arc)) prev_arc = arc; else if (is_active(arc)) { /// ... Found: from == source, to == target search_active_arcs_for(dvf, active_arc, fl, _NORMAL, from_expr, to_expr); } else { /// ... Inactive int pos = 1; Arc_type *traverse = data_field(arc); /// ... Traverse arc to find the exact matching DVfield /// ... with expression pair while (is_new_dvfield(traverse, pos)) { if (_NORMAL == test_dep_direction(traverse, pos + DVF_DDIREC)) { /// ... The DVfield found, so generate a new ActiveArc active_arc = new ActiveArc(*this, arc, prev_arc, next_arc(arc), from_stmt, from_expr); /// ... Attach the new ActiveArc to List<ActiveArc> _active_arcs.ins_last(active_arc); // Return the first matching first/last DVfield in it Iterator<DVfield> iter = active_arc->_working_dv_fields; if (fl == _FIRST) { while (&to_expr != &iter.current()._to_expr) ++iter; } else { /// ... == _LAST iter.set_to_last(); while (&to_expr != &iter.current()._to_expr) --iter; } dvf = &iter.current(); if(active_arc->label()) dvf->setLabel(active_arc->label()->clone()); dvf->references_inc(); break; } _skip_this_dvfield(traverse, pos); } return; } } /// ... No arc with from_expr as a source expression, so try to find /// ... an arc with to_expr as a source expression prev_arc = NULL; for (arc = arcs_ptr(to_expr); arc; arc = next_arc(arc)) { if (&from_expr != target_expr(arc)) prev_arc = arc; else if (is_active(arc)) { /// ... Found: from == target, to == source search_active_arcs_for(dvf, active_arc, fl, _REVERSE, from_expr, to_expr); } else { /// ... Inactive int pos = 1; Arc_type *traverse = data_field(arc); /// ... Traverse arc to find the exact matching DVfield /// ... with expression pair while (is_new_dvfield(traverse, pos)) { if (_REVERSE == test_dep_direction(traverse, pos+DVF_DDIREC)) { /// ... The DVfield found, so generate a new ActiveArc active_arc = new ActiveArc(*this, arc, prev_arc, next_arc(arc), to_stmt, to_expr); /// ... Attach the new ActiveArc to List<ActiveArc> _active_arcs.ins_last(active_arc); // Return the first matching first/last DVfield in it Iterator<DVfield> iter = active_arc->_working_dv_fields; if (fl == _FIRST) { while (&to_expr != &iter.current()._to_expr) ++iter; } else { /// ... == _LAST iter.set_to_last(); while (&to_expr != &iter.current()._to_expr) --iter; } dvf = &iter.current(); dvf->references_inc(); break; } _skip_this_dvfield(traverse, pos); } return; } } } /// ... compute_dvf_n_arc() DVfield * DDgraph::prev(DVfield * dvf, ActiveArc * active_arc) { Iterator<DVfield> iter = active_arc->_working_dv_fields; for ( ; iter.valid(); ++iter) { if (&iter.current() == dvf) { /// ... Itself found break; } } /// ... Now, find the previous one, if any, in the same active arc for (--iter; iter.valid(); --iter) { if (&iter.current()._from_expr == &dvf->_from_expr && iter.current()._valid) { iter.current().references_inc(); break; } } release(dvf, active_arc); if (iter.valid()) { /// ... which satisfy the condition return &iter.current(); } if (active_arc && !--active_arc->_references) write_back_arc(active_arc); return NULL; } DVfield * DDgraph::next(DVfield * dvf, ActiveArc * active_arc) { Iterator<DVfield> iter = active_arc->_working_dv_fields; for (; iter.valid(); ++iter) { if (&iter.current() == dvf) { /// ... Itself found break; } } /// ... Now, find the next one, if any, in the same active arc for (++iter; iter.valid(); ++iter) { if (&iter.current()._from_expr == &dvf->_from_expr && iter.current()._valid) { iter.current().references_inc(); break; } } release(dvf, active_arc); if (iter.valid()) { /// ... which satisfy the condition return &iter.current(); } if (active_arc && !--active_arc->_references) write_back_arc(active_arc); return NULL; } void DDgraph::release(DVfield * dvf, ActiveArc * &active_arc) { if (!dvf->references_dec() && !dvf->_valid) { /// ... Do I have to delete this? active_arc->_working_dv_fields.del(*dvf); if (!active_arc->_working_dv_fields.entries()) { /// ... Empty arc, Connect prev with next of this if (active_arc->_prev_arc && is_active(active_arc->_prev_arc)) { Iterator<ActiveArc> aa_iter = _active_arcs; for (; aa_iter.valid(); ++aa_iter) { if (aa_iter.current()._this_arc == active_arc->_prev_arc) { aa_iter.current()._next_arc = active_arc->_next_arc; break; } } if (active_arc->_next_arc) if (is_active(active_arc->_next_arc)) { /// ... _next_arc also active for (aa_iter.reset(); aa_iter.valid(); ++aa_iter) { if (aa_iter.current()._this_arc == active_arc->_next_arc) { aa_iter.current()._prev_arc = active_arc->_prev_arc; break; } } } else { /// ... _next_arc inactive /// ... store_next_arc(active_arc->_next_arc,active_arc->_prev_arc); } } else { /// ... _prev_arc inactive or NULL if (active_arc->_prev_arc) store_next_arc(active_arc->_prev_arc,active_arc->_next_arc); else { if (active_arc->_source_expr.op() == ARRAY_REF_OP) { ((ArrayRefExpr &) active_arc->_source_expr)._arcs = active_arc->_next_arc; } else { /// ... Must be ID_Expr ((IDExpr &) active_arc->_source_expr)._arcs = active_arc->_next_arc; } } if (active_arc->_next_arc) if (is_active(active_arc->_next_arc)) { /// ... _next_arc active Iterator<ActiveArc> aa_iter = _active_arcs; for (; aa_iter.valid(); ++aa_iter) { if (aa_iter.current()._this_arc == active_arc->_next_arc) { aa_iter.current()._prev_arc = active_arc->_prev_arc; break; } } } else { /// ... _next_arc also inactive /// ... store_next_arc(active_arc->_next_arc,active_arc->_prev_arc); } } /// ... Delete the original arc & active_arc if(arcs_ptr(active_arc->_source_expr) == active_arc->_this_arc) { if (active_arc->_source_expr.op() == ID_OP) /// ... && ((IDExpr &) active_arc->_source_expr)._arcs = 0; else if (active_arc->_source_expr.op() == ARRAY_REF_OP) /// ... && ((ArrayRefExpr &) active_arc->_source_expr)._arcs = 0; } delete active_arc->_this_arc; active_arc->_this_arc = 0; _active_arcs.del(*active_arc); active_arc = NULL; return; } } } /// ... release() void DDgraph::add(List<DVfield>&dv_fields) { Mutator<DVfield> iter = dv_fields; /// ... Subset of dv_fields whose elements, DVfields all have // a pair of the same two expressions as from/to-(or // to/from-)expressions List<DVfield> list; for (; iter.valid(); iter.reset()) { /// ... For all DVfields in 'dv_fields' DVfield *dvf = iter.grab(); /// ... Skip the below sequence if _from_expr.op() is /// ... neither ID nor Array Reference Expression if (dvf->_from_expr.op() != ARRAY_REF_OP && dvf->_from_expr.op() != ID_OP) continue; /// ... Scoop up all DVfields in dv_fields with the same // from/to(or to/from) /// ... expressions pair with dvf list.ins_first(dvf); for (++iter; iter.valid(); ++iter) { if ( &iter.current()._from_expr == &dvf->_from_expr && &iter.current()._to_expr == &dvf->_to_expr || &iter.current()._from_expr == &dvf->_to_expr && &iter.current()._to_expr == &dvf->_from_expr) list.ins_last(iter.grab()); } Arc_type *prev_arc = 0; Arc_type *arc = arcs_ptr(dvf->_from_expr); const Expression *src_expr = NULL, *tgt_expr; for (; arc; arc = next_arc(arc)) { if (&dvf->_to_expr == target_expr(arc)) { src_expr = &dvf->_from_expr; tgt_expr = &dvf->_to_expr; break; } prev_arc = arc; } if (!arc) { /// ... not yet found arc = arcs_ptr(dvf->_to_expr); for (prev_arc = 0; arc; arc = next_arc(arc)) { if (&dvf->_from_expr == target_expr(arc)) { src_expr = &dvf->_to_expr; tgt_expr = &dvf->_from_expr; break; } prev_arc = arc; } } if (arc) { /// ... found if (is_active(arc)) { /// ... Active Iterator<ActiveArc> aa_iter = _active_arcs; /// ... Searching for the corresponding active arc of 'arc' while (aa_iter.current()._this_arc != arc) ++aa_iter; /// ... Move all elements of 'list' to the active arc while (list.entries()) aa_iter.current()._working_dv_fields.ins_last(list.grab(0)); } else { /// ... Inactive, Calculate the size of the old arc int bits = NUM_OF_PTRS * _ptr_size + 1; /// ... pointers & an active bit int pos = 1; /// ... passing by active bit Arc_type *temp_arc = data_field(arc); while (is_new_dvfield(temp_arc, pos)) bits += _count_this_dvfield(temp_arc, pos); int old_bits = bits; /// ... Calculate the size of the newly added part Iterator<DVfield> l_iter = list; for (; l_iter.valid(); ++l_iter) bits += CONST_BITS + l_iter.current()._dv.entries() * (THREE_BIT + EIGHT_BIT + EIGHT_BIT); /// ... Now, replace the old arc by the new one in DDgraph temp_arc = new Arc_type[Bytes(bits)]; /// ... Update the link between temp_arc & next_arc(arc) if (next_arc(arc) && is_active(next_arc(arc))) { Iterator<ActiveArc> aa_iter = _active_arcs; Expression * eptr = target_expr(next_arc(arc)); while (&aa_iter.current()._source_expr != src_expr || &aa_iter.current()._target_expr != eptr) { /// ... first temp_arc ++aa_iter; } aa_iter.current()._prev_arc = temp_arc; } /// ... Update the link between prev_arc(arc) & temp_arc if (prev_arc) if (is_active(prev_arc)) { Iterator<ActiveArc> aa_iter = _active_arcs; Expression * eptr = target_expr(prev_arc); while (&aa_iter.current()._source_expr != src_expr || &aa_iter.current()._target_expr != eptr) { /// ... first temp_arc ++aa_iter; } aa_iter.current()._next_arc = temp_arc; } else store_next_arc(prev_arc, temp_arc); else /// ... temp_arc is the 1st arc for this src_expr if (ID_OP == src_expr->op()) ((IDExpr *) src_expr)->_arcs = temp_arc; else /// ... case ARRAY_REF_OP: ((ArrayRefExpr *) src_expr)->_arcs = temp_arc; /// ... First, copy the old one for (int i = Bytes(old_bits) - 1; i >= 0; --i) { /// ... byte copy temp_arc[i] = arc[i]; } delete arc; arc = 0; temp_arc += Bytes(old_bits) - 1; pos = old_bits % A_BYTE; /// ... Clear all the bits where new arc information will /// ... be written, for overlapped area switch (pos) { case 7: *temp_arc &= '\xfe'; break; case 6: *temp_arc &= '\xfc'; break; case 5: *temp_arc &= '\xf8'; break; case 4: *temp_arc &= '\xf0'; break; case 3: *temp_arc &= '\xe0'; break; case 2: *temp_arc &= '\xc0'; break; case 1: *temp_arc &= '\x80'; break; case 0: *temp_arc = '\0'; break; } _clear_arc(temp_arc + 1, Bytes(bits) - Bytes(old_bits)); /// ... Now, write it for (l_iter.reset(); l_iter.valid(); ++l_iter) { mark_new_dvfield(temp_arc, pos); store_dep_decision(temp_arc,pos,l_iter.current().dep_decided()); if (src_expr == &l_iter.current()._from_expr) store_dep_direction(temp_arc, pos, _NORMAL); else store_dep_direction(temp_arc, pos, _REVERSE); store_dep_type(temp_arc, pos, l_iter.current().dep_type()); Iterator<ElementDV> dv_iter = l_iter.current()._dv; for (; dv_iter.valid(); ++dv_iter) { store_direction(temp_arc,pos,dv_iter.current().direction()); store_min_distance(temp_arc,pos,dv_iter.current().min_distance()); store_max_distance(temp_arc,pos,dv_iter.current().max_distance()); } store_direction(temp_arc, pos, _DELIM); } mark_arc_end(temp_arc, pos); } } else { /// ... Not found, so new space needed for these DVfields int bits = NUM_OF_PTRS * _ptr_size + 1; /// ... pointers & an active bit Iterator<DVfield> l_iter = list; for ( ; l_iter.valid(); ++l_iter) bits += CONST_BITS + l_iter.current()._dv.entries() * (THREE_BIT + EIGHT_BIT + EIGHT_BIT); src_expr = &dvf->_from_expr; tgt_expr = &dvf->_to_expr; Expression *lbl_expr = dvf->label(); arc = new Arc_type[Bytes(bits)]; store_target_stmt(arc, dvf->_to_stmt); store_target_expr(arc, *tgt_expr); if(lbl_expr != NULL) store_label_expr(arc, *lbl_expr->clone()); else store_label_expr(arc, *constant(0)); if (arcs_ptr(*src_expr)) { store_next_arc(arc, arcs_ptr(*src_expr)); if (is_active(arcs_ptr(*src_expr))) { Iterator<ActiveArc> aa_iter = _active_arcs; while (&aa_iter.current()._source_expr != src_expr || aa_iter.current()._prev_arc) { /// ... first arc ++aa_iter; } aa_iter.current()._prev_arc = arc; } } else { store_next_arc(arc, NULL); } switch (src_expr->op()) { case ID_OP: ((IDExpr *) src_expr)->_arcs = arc; break; case ARRAY_REF_OP: ((ArrayRefExpr *) src_expr)->_arcs = arc; break; default: break; } int pos = 1; arc = data_field(arc); _clear_arc(arc, Bytes(bits) - _data_field_offset); /// ... Also deactivating the arc for (l_iter.reset(); l_iter.valid(); ++l_iter) { mark_new_dvfield(arc, pos); store_dep_decision(arc, pos, l_iter.current()._dep_decided); if (src_expr == &l_iter.current()._from_expr) store_dep_direction(arc, pos, _NORMAL); else store_dep_direction(arc, pos, _REVERSE); store_dep_type(arc, pos, l_iter.current()._dep_type); Iterator<ElementDV> dv_iter = l_iter.current()._dv; for (; dv_iter.valid(); ++dv_iter) { store_direction(arc, pos, dv_iter.current().direction()); store_min_distance(arc, pos, dv_iter.current().min_distance()); store_max_distance(arc, pos, dv_iter.current().max_distance()); } store_direction(arc, pos, _DELIM); } mark_arc_end(arc, pos); } list.clear(); } } /// ... DDgraph::add() //--------------------------------------------------------- DDiterator::DDiterator(RefList<Statement> * from_stmts, RefList<Statement> * to_stmts, DDgraph & ddgraph) : _ddgraph(ddgraph) { _init_from = _init_to = _STMTS; _from_refs = _to_refs = _IN_REFS; _from_stmts = from_stmts; _iter_from_stmts = new Iterator<Statement>(*from_stmts); _iter_from_exprs = new Iterator<Expression>((*from_stmts)[0].in_refs()); _to_stmts = to_stmts; _iter_to_stmts = new Iterator<Statement>(*to_stmts); _iter_to_exprs = new Iterator<Expression>((*to_stmts)[0].in_refs()); _current_dvf = NULL; /// ... Find the first valid from-expression while (_iter_from_exprs->end()) { delete _iter_from_exprs; _iter_from_exprs = 0; if (_from_refs == _IN_REFS) { _from_refs = _OUT_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().out_refs()); } else { /// ... _OUT_REFS ++(*_iter_from_stmts); if (_iter_from_stmts->end()) { /// ... Traverse is done return; } _from_refs = _IN_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); } } _next_in_STMTS_n_STMTS(); } DDiterator::DDiterator(RefList<Statement> * from_stmts, const Statement & to_stmt, const Expression & to_expr, DDgraph & ddgraph) : _ddgraph(ddgraph) { _init_from = _STMTS; _init_to = _EXPR; _from_stmts = from_stmts; _to_stmt = &to_stmt; _to_expr = &to_expr; _iter_from_stmts = new Iterator<Statement>(*from_stmts); _iter_from_exprs = new Iterator<Expression>((*from_stmts)[0].in_refs()); _current_dvf = NULL; _next_in_STMTS_n_EXPR(); } DDiterator::DDiterator(const Statement & from_stmt, const Expression & from_expr, RefList<Statement> * to_stmts, DDgraph & ddgraph) : _ddgraph(ddgraph) { _init_from = _EXPR; _init_to = _STMTS; _from_stmt = &from_stmt; _from_expr = &from_expr; _to_stmts = to_stmts; _iter_to_stmts = new Iterator<Statement>(*to_stmts); _iter_to_exprs = new Iterator<Expression>((*to_stmts)[0].in_refs()); _current_dvf = NULL; _next_in_EXPR_n_STMTS(); } DDiterator::DDiterator(const DDiterator & other) : _ddgraph(other._ddgraph) { _current_dvf = other._current_dvf; _active_arc = other._active_arc; _init_from = other._init_from; _init_to = other._init_to; if (_init_from == _STMTS) { _from_refs = other._from_refs; _from_stmts = new RefList<Statement>(*other._from_stmts); _iter_from_stmts = new Iterator<Statement>(*_from_stmts); _iter_from_exprs = new Iterator<Expression>(*other._iter_from_exprs); } else { /// ... _EXPR _from_stmt = other._from_stmt; _from_expr = other._from_expr; } if (_init_to == _STMTS) { _to_refs = other._to_refs; _to_stmts = new RefList<Statement>(*other._to_stmts); _iter_to_stmts = new Iterator<Statement>(*_to_stmts); _iter_to_exprs = new Iterator<Expression>(*other._iter_to_exprs); } else { /// ... _EXPR _to_stmt = other._to_stmt; _to_expr = other._to_expr; } } void DDiterator::operator-- () { if (!_current_dvf) /// ... at the front end or dangling postion return; if ((_current_dvf = _ddgraph.prev(_current_dvf, _active_arc))) return; if (_init_to == _STMTS) { --(*_iter_to_exprs); if (_init_from == _STMTS) { /// ... Case: from_part -> _STMTS, to_part -> _STMTS _prev_in_STMTS_n_STMTS(); } else { /// ... Case: from_part -> _EXPR, to_part -> _STMTS _prev_in_EXPR_n_STMTS(); } } else { if (_init_from == _STMTS) { /// ... Case: from_part -> _STMTS, to_part -> _EXPR --(*_iter_from_exprs); _prev_in_STMTS_n_EXPR(); } /// ... Case: from_part -> _EXPR, to_part -> _EXPR /// ... (Nothing else to do) } } void DDiterator::operator++ () { if (!_current_dvf) /// ... At the end or dangling position return; if ((_current_dvf = _ddgraph.next(_current_dvf, _active_arc))) return; if (_init_to == _STMTS) { ++(*_iter_to_exprs); if (_init_from == _STMTS) { /// ... Case: from_part -> _STMTS, to_part -> _STMTS _next_in_STMTS_n_STMTS(); } else { /// ... Case: from_part -> _EXPR, to_part -> _STMTS _next_in_EXPR_n_STMTS(); } } else { if (_init_from == _STMTS) { /// ... Case: from_part -> _STMTS, to_part -> _EXPR ++(*_iter_from_exprs); _next_in_STMTS_n_EXPR(); } /// ... Case: from_part -> _EXPR, to_part -> _EXPR /// ... (Nothing else to do) } } void DDiterator::reset() { if (_current_dvf && _active_arc) _ddgraph.exit(_current_dvf, _active_arc); if (_init_to == _STMTS) { _current_dvf = NULL; _to_refs = _IN_REFS; delete _iter_to_exprs; _iter_to_exprs = 0; _iter_to_stmts->reset(); _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().in_refs()); if (_init_from == _STMTS) { /// ... Case: from_part -> _STMTS, to_part -> _STMTS _from_refs = _IN_REFS; delete _iter_from_exprs; _iter_from_exprs = 0; _iter_from_stmts->reset(); _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); /// ... Search the first valid from_expr while (_iter_from_exprs->end()) { delete _iter_from_exprs; _iter_from_exprs = 0; if (_from_refs == _IN_REFS) { _from_refs = _OUT_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().out_refs()); } else { /// ... _OUT_REFS ++(*_iter_from_stmts); if (_iter_from_stmts->end()) { /// ... Traverse is done return; } _from_refs = _IN_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); } } _next_in_STMTS_n_STMTS(); } else { /// ... Case: from_part -> _EXPR, to_part -> _STMTS _next_in_EXPR_n_STMTS(); } } else if (_init_from == _STMTS) { /// ... Case: from_part -> _STMTS, to_part -> _EXPR _current_dvf = NULL; _from_refs = _IN_REFS; delete _iter_from_exprs; _iter_from_exprs = 0; _iter_from_stmts->reset(); _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); _next_in_STMTS_n_EXPR(); } else { /// ... Case: from_part -> _EXPR, to_part -> _EXPR _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _FIRST, *_from_stmt, *_from_expr, *_to_stmt, *_to_expr); } } void DDiterator::set_to_last() { if (_current_dvf && _active_arc) _ddgraph.exit(_current_dvf, _active_arc); if (_init_to == _STMTS) { _current_dvf = NULL; _to_refs = _IN_REFS; delete _iter_to_exprs; _iter_to_exprs = 0; _iter_to_stmts->set_to_last(); _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().in_refs()); _iter_to_exprs->set_to_last(); if (_init_from == _STMTS) { /// ... Case: from_part -> _STMTS, to_part -> _STMTS _from_refs = _IN_REFS; delete _iter_from_exprs; _iter_from_exprs = 0; _iter_from_stmts->set_to_last(); _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); /// ... Search the first valid from_expr while (_iter_from_exprs->end()) { delete _iter_from_exprs; _iter_from_exprs = 0; if (_from_refs == _IN_REFS) { _from_refs = _OUT_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().out_refs()); } else { /// ... _OUT_REFS ++(*_iter_from_stmts); if (_iter_from_stmts->end()) { /// ... Traverse is done return; } _from_refs = _IN_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); } } _iter_from_exprs->set_to_last(); _prev_in_STMTS_n_STMTS(); } else { /// ... Case: from_part -> _EXPR, to_part -> _STMTS _prev_in_EXPR_n_STMTS(); } } else if (_init_from == _STMTS) { /// ... Case: from_part -> _STMTS, to_part -> _EXPR _current_dvf = NULL; _from_refs = _IN_REFS; delete _iter_from_exprs; _iter_from_exprs = 0; _iter_from_stmts->reset(); _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); _iter_from_exprs->set_to_last(); _prev_in_STMTS_n_EXPR(); } else { /// ... Case: from_part -> _EXPR, to_part -> _EXPR _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _LAST, *_from_stmt, *_from_expr, *_to_stmt, *_to_expr); } } void DDiterator::_next_in_STMTS_n_STMTS() { while (1) if (_iter_to_exprs->valid()) { /// ... _iter_from_exprs must be valid here _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _FIRST, _iter_from_stmts->current(), _iter_from_exprs->current() ,_iter_to_stmts->current(), _iter_to_exprs->current()); if (_current_dvf) return; ++(*_iter_to_exprs); } else { delete _iter_to_exprs; _iter_to_exprs = 0; if (_to_refs == _IN_REFS) { _to_refs = _OUT_REFS; _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().out_refs()); } else { ++(*_iter_to_stmts); while (_iter_to_stmts->end()) { ++(*_iter_from_exprs); while (_iter_from_exprs->end()) { delete _iter_from_exprs; _iter_from_exprs = 0; if (_from_refs == _IN_REFS) { _from_refs = _OUT_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().out_refs()); } else { /// ... _OUT_REFS ++(*_iter_from_stmts); if (_iter_from_stmts->end()) { /// ... Traverse is done return; } _from_refs = _IN_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); } } _iter_to_stmts->reset(); } _to_refs = _IN_REFS; _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().in_refs()); } } } void DDiterator::_next_in_STMTS_n_EXPR() { while (1) { if (_iter_from_exprs->valid()) { _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _FIRST, _iter_from_stmts->current(), _iter_from_exprs->current(), *_to_stmt, *_to_expr); if (_current_dvf) return; ++(*_iter_from_exprs); } else { delete _iter_from_exprs; _iter_from_exprs = 0; if (_from_refs == _IN_REFS) { _from_refs = _OUT_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().out_refs()); } else { /// ... _OUT_REFS ++(*_iter_from_stmts); if (_iter_from_stmts->end()) return; _from_refs = _IN_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); } } } } void DDiterator::_next_in_EXPR_n_STMTS() { while (1) { if (_iter_to_exprs->valid()) { _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _FIRST, *_from_stmt, *_from_expr, _iter_to_stmts->current(), _iter_to_exprs->current()); if (_current_dvf) return; ++(*_iter_to_exprs); } else { delete _iter_to_exprs; _iter_to_exprs = 0; if (_to_refs == _IN_REFS) { _to_refs = _OUT_REFS; _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().out_refs()); } else { ++(*_iter_to_stmts); if (_iter_to_stmts->end()) return; _to_refs = _IN_REFS; _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().in_refs()); } } } } void DDiterator::_prev_in_STMTS_n_STMTS() { while (1) { if (_iter_to_exprs->valid()) { /// ... _from_expr part must be valid here _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _LAST, _iter_from_stmts->current(), _iter_from_exprs->current(), _iter_to_stmts->current(), _iter_to_exprs->current()); if (_current_dvf) return; --(*_iter_to_exprs); } else { delete _iter_to_exprs; _iter_to_exprs = 0; if (_to_refs == _IN_REFS) { _to_refs = _OUT_REFS; _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().out_refs()); _iter_to_exprs->set_to_last(); } else { --(*_iter_to_stmts); while (_iter_to_stmts->end()) { --(*_iter_from_exprs); while (_iter_from_exprs->end()) { delete _iter_from_exprs; _iter_from_exprs = 0; if (_from_refs == _IN_REFS) { _from_refs = _OUT_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().out_refs()); _iter_from_exprs->set_to_last(); } else { /// ... _OUT_REFS --(*_iter_from_stmts); if (_iter_from_stmts->end()) { /// ... Traverse is done return; } _from_refs = _IN_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); _iter_from_exprs->set_to_last(); } } _iter_to_stmts->set_to_last(); } _to_refs = _IN_REFS; _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().in_refs()); _iter_to_exprs->set_to_last(); } } } } void DDiterator::_prev_in_STMTS_n_EXPR() { while (1) { if (_iter_from_exprs->valid()) { _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _LAST, _iter_from_stmts->current(), _iter_from_exprs->current(), *_to_stmt, *_to_expr); if (_current_dvf) return; --(*_iter_from_exprs); } else { delete _iter_from_exprs; _iter_from_exprs = 0; if (_from_refs == _IN_REFS) { _from_refs = _OUT_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().out_refs()); _iter_from_exprs->set_to_last(); } else { /// ... _OUT_REFS --(*_iter_from_stmts); if (_iter_from_stmts->end()) return; _from_refs = _IN_REFS; _iter_from_exprs = new Iterator<Expression> (_iter_from_stmts->current().in_refs()); _iter_from_exprs->set_to_last(); } } } } void DDiterator::_prev_in_EXPR_n_STMTS() { while (1) { if (_iter_to_exprs->valid()) { _ddgraph.compute_dvf_n_arc(_current_dvf, _active_arc, _LAST, *_from_stmt, *_from_expr, _iter_to_stmts->current(), _iter_to_exprs->current()); if (_current_dvf) return; --(*_iter_to_exprs); } else { delete _iter_to_exprs; _iter_to_exprs = 0; if (_to_refs == _IN_REFS) { _to_refs = _OUT_REFS; _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().out_refs()); _iter_to_exprs->set_to_last(); } else { --(*_iter_to_stmts); if (_iter_to_stmts->end()) return; _to_refs = _IN_REFS; _iter_to_exprs = new Iterator<Expression> (_iter_to_stmts->current().in_refs()); _iter_to_exprs->set_to_last(); } } } }

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