Polaris: AbstractAccess.cc Source File

AbstractAccess.cc Go to the documentation of this file. /// /// \file AbstractAccess.cc /// #ifdef POLARIS_GNU_PRAGMAS #pragma implementation #endif /// #include "utilities/access_util.h" #include "utilities/lambda_util.h" #include "utilities/mem_util.h" #include "utilities/expression_util.h" #include "AbstractAccess.h" #include "InlineObject.h" #include "Monotonicity.h" #include "ProgramUnit.h" #include "SmallIntSet.h" #include "Range/RangeAccessor.h" #include "Range/AIRangeDict.h" //#include "Range/StmtRanges.h" #include "Range/range_util.h" #include "Traverser.h" #include "TranslateObject.h" #include "translateobject.h" #include "UGraphIterator.h" #include "utilities/expression_util.h" #include "utilities/gsa_util.h" #include "utilities/stmt_util.h" int _ipa = -1; /// A static global to hold the value of the ipa switch int _ipa_reasons = -1; /// A static global to hold the value of the ipa switch int _ar_coalesce = -1; /// A static global to hold the value of the ar_coalesce switch int _ar_aggregate = -1; /// A static global to hold the value of the ar_aggregate switch int _ar_interleave = -1; /// A static global to hold the value of the ar_interleave switch int _ar_match_dims = -1; /// A static global to hold the value of the ar_match_dims switch int _ar_logging = -1; /// A static global to hold the value of the ar_match_dims switch ofstream arlog; /// The file for writing the Access Region log. int _ar_leave_descr = -1; /// Controls whether descriptors are left on statements or not int _ar_prtstats = -1; /// Controls collecting and printing of statistics (ar_prtstats switch) int _ar_approx_thresh = -1; /// Set the threshold for list size which causes the list to be replaced by /// a single "approximate LMAD" int _ar_effort = -1; /// Controls how hard we work on simplifying a set of descriptors /// (scale of 1 to 10, 10 being to work the hardest) int _ar_reshape = -1; ofstream stats_out; static Boolean is_array_ref (const Expression & expr) { switch (expr.op()) { case ARRAY_REF_OP: return True; default: return False; } } AbstractAccess::AbstractAccess( ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(ABSTRACT_ACCESS, sizeof(AbstractAccess), this); #endif _symbol = NULL; _start = NULL; _accuracy = ACCU_UNKNOWN; _actual = NULL; _actual_stmt = NULL; _visited = 0; _read_only = false; _write_first = false; _approximate = false; _no_overlap = 0; _correctness = 0; _imprecise_sorting = false; _exec_pred = -1; _possible_reduction = false; _possible_induction = false; _reduct_op = RED_OP_NONE; _summarized_to = NULL; _pgm_summarized_to = NULL; _triangular = 0; _subsub = 0; _nonaffine = 0; _monoton = AR_UNKNOWN_MONO; _access_type = AR_UNKNOWN; _nesting_level = 0; _bytesize = 0; } /// We take ownership of the start expression AbstractAccess::AbstractAccess( const Symbol & sym, const List<AccessDimension> & dims, Expression * start ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(ABSTRACT_ACCESS, sizeof(AbstractAccess), this); #endif _symbol = (Symbol *)&sym; /// ... Copy the dimension list for (Iterator<AccessDimension> iter = dims; iter.valid(); ++iter) { add_dimension( iter.current().clone() ); } _start = start; _accuracy = ACCU_UNKNOWN; _actual = NULL; _actual_stmt = NULL; _visited = 0; _read_only = false; _write_first = false; _approximate = false; _no_overlap = 0; _correctness = 0; _exec_pred = -1; _possible_reduction = false; _possible_induction = false; _reduct_op = RED_OP_NONE; _imprecise_sorting = false; _summarized_to = NULL; _pgm_summarized_to = NULL; _triangular = 0; _subsub = 0; _nonaffine = 0; _monoton = AR_UNKNOWN_MONO; _access_type = AR_UNKNOWN; _nesting_level = 0; _bytesize = 0; } /// We take ownership of the start expression AbstractAccess::AbstractAccess( const Symbol & sym, const List<AccessDimension> & dims, Expression * start, ACCURACY accu, AR_TYPE artype ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(ABSTRACT_ACCESS, sizeof(AbstractAccess), this); #endif _symbol = (Symbol *)&sym; /// ... Copy the dimension list for (Iterator<AccessDimension> iter = dims; iter.valid(); ++iter) { add_dimension( iter.current().clone() ); } _start = start; _accuracy = accu; _actual = NULL; _actual_stmt = NULL; _visited = 0; _read_only = false; _write_first = false; _approximate = false; _no_overlap = 0; _correctness = 0; _exec_pred = -1; _possible_reduction = false; _possible_induction = false; _reduct_op = RED_OP_NONE; _imprecise_sorting = false; _summarized_to = NULL; _pgm_summarized_to = NULL; _triangular = 0; _subsub = 0; _nonaffine = 0; _monoton = AR_UNKNOWN_MONO; _access_type = artype; _nesting_level = 0; _bytesize = 0; } /// We take ownership of the start expression AbstractAccess::AbstractAccess( const Symbol & sym, const List<AccessDimension> & dims, Expression * start, AbstractAccess * model_aa ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(ABSTRACT_ACCESS, sizeof(AbstractAccess), this); #endif _symbol = (Symbol *)&sym; /// ... Copy the dimension list for (Iterator<AccessDimension> iter = dims; iter.valid(); ++iter) { add_dimension( iter.current().clone() ); } _start = start; _accuracy = model_aa->_accuracy; _actual = model_aa->_actual; _actual_stmt = model_aa->_actual_stmt; _visited = 0; _read_only = model_aa->_read_only; _write_first = model_aa->_write_first; _approximate = model_aa->_approximate; _no_overlap = model_aa->_no_overlap; if (model_aa->_correctness) { _correctness = model_aa->_correctness->clone(); } else { _correctness = 0; } _exec_pred = model_aa->_exec_pred; _possible_reduction = model_aa->_possible_reduction; _possible_induction = model_aa->_possible_induction; _reduct_op = model_aa->_reduct_op; _imprecise_sorting = model_aa->_imprecise_sorting; _summarized_to = model_aa->_summarized_to; _pgm_summarized_to = model_aa->_pgm_summarized_to; _triangular = model_aa->_triangular; _subsub = model_aa->_subsub; _nonaffine = model_aa->_nonaffine; _monoton = model_aa->_monoton; _access_type = model_aa->_access_type; _nesting_level = model_aa->_nesting_level; _bytesize = model_aa->_bytesize; } AbstractAccess::AbstractAccess( const AbstractAccess & other ) { #ifdef CLASS_INSTANCE_REGISTRY register_instance(ABSTRACT_ACCESS, sizeof(AbstractAccess), this); #endif _symbol = other._symbol; _visited = 0; /// ... Copy the dimension list for (Iterator<AccessDimension> iter = other._dims; iter.valid(); ++iter) { add_dimension( iter.current().clone() ); } if (other._start) { _start = other._start->clone(); } else { _start = NULL; } _exec_pred = other._exec_pred; if (other._correctness) { _correctness = other._correctness->clone(); } else { _correctness = NULL; } _accuracy = other._accuracy; if (other._actual) { _actual = other._actual->clone(); } else { _actual = 0; } _actual_stmt = other._actual_stmt; _read_only = other._read_only; _approximate = other._approximate; _write_first = other._write_first; _no_overlap = other._no_overlap; _possible_reduction = other._possible_reduction; _possible_induction = other._possible_induction;; _reduct_op = other._reduct_op; _imprecise_sorting = other._imprecise_sorting; _summarized_to = other._summarized_to; _pgm_summarized_to = other._pgm_summarized_to; _triangular = other._triangular; _subsub = other._subsub; _nonaffine = other._nonaffine; _monoton = other._monoton; _access_type = other._access_type; _nesting_level = other._nesting_level; _bytesize = other._bytesize; } AbstractAccess::~AbstractAccess( ) { #ifdef CLASS_INSTANCE_REGISTRY unregister_instance(ABSTRACT_ACCESS, this); #endif if (_start) { delete _start; } if (_actual) { delete _actual; } if (_correctness) { delete _correctness; } } Symbol & AbstractAccess::symbol( ) const{ return (Symbol &) *_symbol; } Statement * AbstractAccess::summarized_to( ) { return _summarized_to; } void AbstractAccess::summarized_to( Statement * stmt) { _summarized_to = stmt; } ProgramUnit * AbstractAccess::pgm_summarized_to( ) { return _pgm_summarized_to; } void AbstractAccess::pgm_summarized_to( ProgramUnit * stmt) { _pgm_summarized_to = stmt; } int AbstractAccess::nesting_level( ) { return _nesting_level; } Expression * AbstractAccess::lastoffset( ) const { if (_dims.entries() == 0) { if (start_exists()) { return _start->clone(); } else { return constant(0); } } else { List<Expression> * list = new List<Expression>; if (start_exists()) { list->ins_first(_start->clone()); } else { list->ins_first(constant(0)); } for (Iterator<AccessDimension> iter = _dims; iter.valid(); ++iter) { AccessDimension & dim = iter.current(); if ((dim.span_guarded().op() == INTEGER_CONSTANT_OP) && (dim.span_guarded().value() == 0)) { } else { list->ins_first(dim.span_guarded().clone()); } } return add(list); } } void AbstractAccess::nesting_level( int level ) { _nesting_level = level; } void AbstractAccess::inc_nesting( ) { ++_nesting_level; } Expression & AbstractAccess::start_guarded( ) const { p_assert(_start, "AbstractAccess: start does not exist"); return (Expression &) *_start; } Boolean AbstractAccess::start_exists( ) const { if (_start) { return True; } else { return False; } } Boolean AbstractAccess::actual_exists( ) const { if (_actual) { return True; } else { return False; } } AbstractAccess * AbstractAccess::remap_interface_vars( InlineObject * inl_obj, Statement & stmt, const Symbol & sym, const REF_TYPE ref, int exec_pred ) const { static LambdaInfo lambda(0, 0, INLINE_CALL); /// ... Go through all the symbols in the range dictionary of the current /// ... AbstractAccess object, translating them for the calling context. String tag = stmt.tag(); Statement * r_stmt = range_stmt(*_summarized_to); AIRangeDict & range_dict = (AIRangeDict &)(this->_pgm_summarized_to->range_dict_guarded()); RefSet<Symbol> * set = range_dict.range_vars(tag); if (set) { for (Iterator<Symbol> iter = *set; iter.valid(); ++iter) { VariableSymbol * trsym = inl_obj->translate_symbol( iter.current() ); /// ... If no translation exists for this symbol, it means that this is not /// ... an interface variable. Nevertheless, it needs to exist in the StmtRanges /// ... object of this AbstractAccess so that we can compare its elements /// ... symbolically. Therefore, we find a non-conflicting name for the symbol /// ... in the calling routine, and insert a new symbol in the calling routine's /// ... symbol table. We also provide a mapping for the symbol in the InlineObject /// ... so that wherever it appears in the AbstractAccess object, it will be translated /// ... to the new symbol. if (!trsym) { VariableSymbol * sym = (VariableSymbol *)(&(iter.current())); if (sym->is_gsa_symbol()) { sym = (VariableSymbol *) (&(sym->gsa_base_symbol())); } Symbol * symclone = sym->clone(); Symbol & newsym = inl_obj->pgm_main().symtab().rename_and_ins(symclone); inl_obj->TranslateObject::GSA_mapping(iter.current(), newsym); } } } List<AccessDimension> * listdim = new List<AccessDimension>; for (Iterator<AccessDimension> iter = _dims; iter.valid(); ++iter) { AccessDimension * new_dim = iter.current().remap_interface_vars( inl_obj, ref ); listdim->ins_last ( new_dim ); } Expression * new_start = 0; const AbstractAccess * caller_aa = inl_obj->access_region(sym); if (this->start_exists()) { Expression * trans_start = this->start_guarded().clone(); trans_start = trans_update_expr(inl_obj, trans_start); if (caller_aa && caller_aa->start_exists()) { new_start = simplify(add(caller_aa->start_guarded().clone(), trans_start)); } else { new_start = trans_start; } } VariableSymbol * newsym = inl_obj->translate_symbol( sym ); if (newsym->is_gsa_symbol()) { newsym = (VariableSymbol *) (&(newsym->gsa_base_symbol())); } AbstractAccess * new_aa = new AbstractAccess(*newsym, *listdim, new_start, (AbstractAccess *) this); // this->accuracy(), // (AR_TYPE) (this->_access_type) ); /// ... If an actual expression for this access appears on the CALL stmt, copy it /// ... If not, set the fields to NULL if (caller_aa && caller_aa->_actual) { new_aa->_actual = caller_aa->_actual->clone(); new_aa->_actual_stmt = caller_aa->_actual_stmt; } if (this->_correctness) { Expression * trans_corr = _correctness->clone(); trans_corr = trans_update_expr(inl_obj, trans_corr); new_aa->_correctness = trans_corr; } if (this->_exec_pred != -1) { Expression * trans_pred = _pgm_summarized_to->pred_repos().predicate(this->_exec_pred)->clone(); trans_pred = trans_update_expr(inl_obj, trans_pred); int index = inl_obj->pgm_main().pred_repos().ins(trans_pred); new_aa->_exec_pred = index; } /// StmtRanges * new_ranges = new StmtRanges(this->_pgm_summarized_to->symtab()); /// ... Go through all the symbols in the range dictionary of the current /// ... AbstractAccess object, translating the symbols and translating /// ... the ranges. delete set; set = range_dict.range_vars(tag); if (set) { for (Iterator<Symbol> iter = *set; iter.valid(); ++iter) { const Expression * range = range_dict._get_range_ref(iter.current(), *r_stmt ); if (range) { Expression *new_range = range->clone(); inl_obj->remap_expr( &new_range, lambda, ref); VariableSymbol * trsym = inl_obj->translate_symbol( iter.current() ); inl_obj->pgm_main().range_dict_guarded()._set_range(*trsym, *r_stmt, new_range); } } } delete set; new_aa->_read_only = this->_read_only; new_aa->_approximate = this->_approximate; new_aa->_write_first = this->_write_first; new_aa->_triangular = this->_triangular; new_aa->_diagonal = this->_diagonal; new_aa->_subsub = this->_subsub; new_aa->_nonaffine = this->_nonaffine; new_aa->_monoton = this->_monoton; new_aa->_nesting_level = this->_nesting_level; return new_aa; } AbstractAccess * AbstractAccess::clone( ) const { return new AbstractAccess( *this ); } Listable * AbstractAccess::listable_clone() const { return (Listable *) clone(); } void AbstractAccess::relink_eptrs( ProgramUnit & p ) { for (Iterator<AccessDimension> iter = _dims; iter.valid(); ++iter) { iter.current().relink_eptrs( p ); } if (_start) { _start->relink_eptrs( p ); } if (_correctness) { _correctness->relink_eptrs( p ); } /// if (_exec_pred) { // _exec_pred->relink_eptrs( p ); /// } } /// We take ownership of the start expression: void AbstractAccess::start( Expression * start ) { if (_start) { delete _start; } _start = start; } void AbstractAccess::print( ostream & o ) const { o << endl; o << _symbol->name_ref() << "-"; if (_imprecise_sorting) o << "?SORT:"; if (_read_only || _write_first || _no_overlap || _approximate) { o << "<"; if (_read_only) { o << "R"; } if (_approximate) { o << "A"; } if (_write_first) { o << "W"; } if (_no_overlap == 1) { o << "="; } else if (_no_overlap == 2) { o << "=?"; } o << ">"; } /// ... Don't print the predicate, if it's .TRUE. if (!(this->exec_predicate_true())) { if (_exec_pred == -11) { o << "{<uninitialized>}:"; } else if (_exec_pred != -1) { o << "{" << *(_pgm_summarized_to->pred_repos().predicate(_exec_pred)) << "}:"; } } if (_possible_reduction) { o << "<RED:" ; if (_possible_induction) o << "I"; switch (_reduct_op) { case RED_OP_NONE: o << "?"; break; case RED_OP_PLUS: o << "+"; break; case RED_OP_MUL: o << "*"; break; case RED_OP_MIN: o << "MIN"; break; case RED_OP_MAX: o << "MAX"; break; default: p_abort("bad value for reduction operator"); } o << ">"; } o << "^["; Iterator<AccessDimension> iter = _dims; for (int i=0; iter.valid(); ++i) { if (iter.current()._check_overlap) o << "#"; if (iter.current().stride_exists()) { ACCURACY acc = iter.current().accuracy(); if (acc == ACCU_EXACT) { o << iter.current().stride_guarded(); } else if (acc == ACCU_SUPERSET) { o << "~" << iter.current().stride_guarded(); } else if (acc == ACCU_SUBSET) { o << "_" << iter.current().stride_guarded(); } else { o << "?" << iter.current().stride_guarded(); } } ++iter; if (iter.valid()) { o << ","; } } o << "]v["; for (iter.reset(); iter.valid(); ) { if (iter.current().span_exists()) { ACCURACY acc = iter.current().accuracy(); if (acc == ACCU_EXACT) { o << iter.current().span_guarded(); } else if (acc == ACCU_SUPERSET) { o << "~" << iter.current().span_guarded(); } else if (acc == ACCU_SUBSET) { o << "_" << iter.current().span_guarded(); } else { o << "?" << iter.current().span_guarded(); } } ++iter; if (iter.valid()) { o << ","; } } o << "]"; o << "+" << *_start; } ostream & operator << (ostream & o, const AbstractAccess & aa) { aa.print(o); return o; } void AbstractAccess::accuracy( ACCURACY accu ) { _accuracy = accu; } ACCURACY AbstractAccess::accuracy ( ) const { return _accuracy; } void AbstractAccess::add_actual ( Statement * stmt, Expression * expr ) { _actual_stmt = stmt; _actual = expr; /// ... Take possession of the actual expression } Expression & AbstractAccess::actual_guarded ( ) const { return (Expression &) *_actual; } void AbstractAccess::remove_actual( ) { if (_actual) { delete _actual; _actual = 0; } } Statement * AbstractAccess::actual_stmt() const { return _actual_stmt; } int AbstractAccess::number_of_dimensions( ) const { return this->_dims.entries(); } void AbstractAccess::byte_size( int bytes ) { _bytesize = bytes; } bool AbstractAccess::poss_reduct( ) { return _possible_reduction; } bool AbstractAccess::poss_induct( ) { return _possible_induction; } void AbstractAccess::poss_reduct( bool val ) { _possible_reduction = val; } void AbstractAccess::poss_induct( bool val ) { _possible_induction = val; } void AbstractAccess::reduct_op( RED_OP op ) { _reduct_op = op; } RED_OP AbstractAccess::reduct_op( ) { return (RED_OP) _reduct_op; } void AbstractAccess::exec_predicate( int pred ) { _exec_pred = pred; } bool AbstractAccess::exec_predicate_exists() const { if (_exec_pred != -11) { return true; } else { return false; } } bool AbstractAccess::exec_predicate_true() const { if (_exec_pred == -1) { return true; } else if (_exec_pred == -2) { return false; } else { Expression * expr = _pgm_summarized_to->pred_repos().predicate(_exec_pred); if ((expr->op() == LOGICAL_CONSTANT_OP) && (expr->str_data() == ".TRUE.")) { return true; } } return false; } bool AbstractAccess::exec_predicate_false() const { if (_exec_pred == -2) { return true; } else if (_exec_pred == -1) { return false; } else { Expression * expr = _pgm_summarized_to->pred_repos().predicate(_exec_pred); if ((expr->op() == LOGICAL_CONSTANT_OP) && (expr->str_data() == ".FALSE.")) { return true; } } return false; } int AbstractAccess::exec_predicate( ) { return _exec_pred; } int AbstractAccess::byte_size( ) { return _bytesize; } /// Convert this descriptor to a new bytesize. The new size must be /// smaller than the current bytesize, and also must divide the current /// bytesize. The standard Fortran sizes always fit this criteria: /// 16, 8, 4, 2, 1. void AbstractAccess::convert_size (int new_size) { p_assert((new_size < _bytesize) && (_bytesize % new_size == 0), "improper size for converting AbstractAccess"); _start = simplify(mul(constant(4),_start)); for (Iterator<AccessDimension> iter = _dims; iter.valid(); ++iter) { AccessDimension & accdim = iter.current(); accdim._span = simplify(mul(constant(4),accdim._span)); accdim._stride = simplify(mul(constant(4),accdim._stride)); } AccessDimension * newdim = new AccessDimension(constant(1), constant(new_size - 1)); newdim->singleton(true); add_dimension(newdim); } void AbstractAccess::add_dimension( const AccessDimension * dim ) { if (dim->stride_exists()) { _dims.ins_last(dim); } } void AbstractAccess::add_dimension( const AccessDimension * dim, int which_dim ) { if (which_dim < 0) return; if (dim->stride_exists()) { _dims.ins(dim, which_dim); } } AccessDimension & AbstractAccess::dimension( int i ) { return _dims[i]; } Iterator<AccessDimension> AbstractAccess::iter_dims( ) { Iterator<AccessDimension> iter = _dims; return iter; } /// Look for an exact match on all major parts of the access regions bool AbstractAccess::match( AbstractAccess * other ) { if ( this->accuracy() != other->accuracy() ) return false; int dims = this->number_of_dimensions(); if ( dims != other->number_of_dimensions() ) return false; if ( ! (this->start_guarded().match( other->start_guarded() )) ) return false; int number_matches = this->match_dims( other ); if (number_matches == dims) return true; else return false; } /// Look for a match ignoring the start expression bool AbstractAccess::match_by_dims( AbstractAccess * other ) { if ( this->accuracy() != other->accuracy() ) return false; int dims = this->number_of_dimensions(); if ( dims != other->number_of_dimensions() ) return false; int number_matches = this->match_dims( other ); if (number_matches == dims) return true; else return false; } /// Look for an exact match on strides of two access regions bool AbstractAccess::match_by_strides( AbstractAccess * other ) { if ( this->accuracy() != other->accuracy() ) return false; int dims = this->number_of_dimensions(); if ( dims != other->number_of_dimensions() ) return false; int number_matches = this->match_dims_stride( other ); if (number_matches == dims) return true; else return false; } /// Look for an exact match on start and all dimensions except 1 bool AbstractAccess::match_by_start_dims_except_1( AbstractAccess * other ) { if ( this->accuracy() != other->accuracy() ) return false; int dims = this->number_of_dimensions(); if ( dims != other->number_of_dimensions() ) return false; if ( ! this->start_guarded().match( other->start_guarded() ) ) return false; int number_matches = this->match_dims( other ); if (number_matches >= dims-1) return true; else return false; } /// Look for an exact match on all dimensions except 1 (ignoring start) bool AbstractAccess::match_by_dims_except_1( AbstractAccess * other ) { if ( this->accuracy() != other->accuracy() ) return false; int dims = this->number_of_dimensions(); if ( dims != other->number_of_dimensions() ) return false; int number_matches = this->match_dims( other ); if (number_matches >= dims-1) return true; else return false; } /// Match up the dimensions and return how many matching pairs there are int AbstractAccess::match_dims( AbstractAccess * other ) { SmallIntSet matched_dims; int matches = 0; for (Iterator<AccessDimension> iter = _dims; iter.valid(); ++iter) { AccessDimension & dim = iter.current(); int inner = 0; for (Iterator<AccessDimension> other_iter = other->iter_dims(); other_iter.valid(); ++other_iter,++inner) { if ( matched_dims[inner] ) continue; AccessDimension & other_dim = other_iter.current(); if (dim.stride_guarded().match(other_dim.stride_guarded()) && ((! dim.span_exists() && ! other_dim.span_exists()) || (( dim.span_exists() && other_dim.span_exists()) && (dim.span_guarded().match(other_dim.span_guarded()))) )) { matched_dims.ins(inner); matches++; break; } } } return matches; } /// Match up the strides and return how many matching pairs there are int AbstractAccess::match_dims_stride( AbstractAccess * other ) { SmallIntSet matched_dims; int matches = 0; for (Iterator<AccessDimension> iter = _dims; iter.valid(); ++iter) { AccessDimension & dim = iter.current(); int inner = 0; for (Iterator<AccessDimension> other_iter = other->iter_dims(); other_iter.valid(); ++other_iter,++inner) { if ( matched_dims[inner] ) continue; AccessDimension & other_dim = other_iter.current(); if (dim.stride_guarded().match(other_dim.stride_guarded())) { matched_dims.ins(inner); matches++; break; } } } return matches; } void AbstractAccess::set_check_overlap( int which_dim, bool value ) { _dims[which_dim]._check_overlap = value; } /// Calculate the overlap value. This is accomplished by computing /// the sum of the spans of all dimensions before "which_dim" and /// checking whether it is less than the stride of dimension "which_dim". /// Likewise, we have to make sure that the span of "which_dim" is /// not larger than the stride of the next outer dimension (at which_dim+1). /// If so, we say there is "No overlap". Otherwise, there is overlap. void AbstractAccess::calc_overlap( int which_dim ) { int entries = _dims.entries(); /// which_dim == -1 means that expand didn't find the loop index in the start expression. /// This definitely means there is an overlap. if (which_dim == -1) { _no_overlap = 0; return; } else if (entries <= 1) { /// ... If index appeared in start expression, and < 2 dimensions, there can be no overlap _no_overlap = 1; return; } /// If we couldn't sort the dimensions, then nothing can be done /// at compile time to determine overlap. if (_imprecise_sorting) { _dims[which_dim]._check_overlap = true; _no_overlap = 2; return; } /// The rest of this routine assumes that sorting was precise! Statement * r_stmt = range_stmt(*_summarized_to); RangeAccessor range_acc(_pgm_summarized_to->range_dict_guarded(), *r_stmt ); /// Check the sum of the spans inside this dimension against this stride Expression * sum = 0; Expression * stride = 0; Expression * span = 0; if (which_dim > 0) { p_assert(_dims[0].span_exists(), "Span does not exist"); sum = _dims[0].span_guarded().clone(); for (int i = 1; i<which_dim; ++i) { p_assert(_dims[i].span_exists(), "Span does not exist"); sum = add(sum, _dims[i].span_guarded().clone()); } sum = simplify(sum); p_assert(_dims[which_dim].stride_exists(), "Stride does not exist"); stride = _dims[which_dim].stride_guarded().clone(); Relation rel = range_acc.compare(*sum, *stride); if (rel.is_greater_equal()) { _no_overlap = 0; delete stride; delete sum; return; } /// ... If the Relation couldn't say that sum >= stride AND /// ... can't say that sum<stride, it obviously doesn't know, /// ... so this is where we need a correctness condition. if (!(rel.is_less_than())) { if (_correctness) { _correctness = and(_correctness, lt(sum->clone(), stride->clone())); } else { _correctness = lt(sum->clone(), stride->clone()); } _dims[which_dim]._check_overlap = true; _no_overlap = 2; } } delete stride; /// Check the span of this dim against the stride of the next outer dim if (which_dim < entries-1) { p_assert(_dims[which_dim+1].stride_exists(), "Stride does not exist"); p_assert(_dims[which_dim].span_exists(), "Span does not exist"); stride = _dims[which_dim+1].stride_guarded().clone(); span = _dims[which_dim].span_guarded().clone(); /// ... If there were no prior dimensions, just compare which_dim to outer if (sum == 0) { Relation rel = range_acc.compare(*stride, *span); if (rel.is_less_equal()) { _no_overlap = 0; delete stride; delete span; return; } // If we can't say that stride <= span and we can't say // that stride > span, then we need a correctness condition // to be tested at runtime. if (!(rel.is_greater_than())) { if (_correctness) { _correctness = and(_correctness, gt(stride->clone(), span->clone())); } else { _correctness = gt(stride->clone(), span->clone()); } _dims[which_dim]._check_overlap = true; _no_overlap = 2; } delete stride; delete span; } else { sum = simplify(add(sum, span->clone())); Relation rel = range_acc.compare(*stride, *sum); if (rel.is_less_equal()) { _no_overlap = 0; delete stride; delete span; delete sum; return; } // If we can't say that stride <= sum and we can't say // that stride > sum, then we need a correctness condition // to be tested at runtime. if (!(rel.is_greater_than())) { if (_correctness) { _correctness = and(_correctness, gt(stride->clone(), sum->clone())); } else { _correctness = gt(stride->clone(), sum->clone()); } _dims[which_dim]._check_overlap = true; _no_overlap = 2; } delete stride; delete span; } } if (_no_overlap != 2) _no_overlap = 1; delete sum; return; } /// compute a new dimension holding at a point in the program, /// using expressions as from a DO statement: /// index = lo, hi, by /// Insert the new dimension in the AbstractAccess object, in /// sorted order (by stride). /// /// The return value is the position of the new dimension in the /// resulting AbstractAccess object. int AbstractAccess::compute_new_dimension(ProgramUnit & pgm, Statement & stmt, Symbol & index, Expression & lo, Expression & hi, Expression & by) { Expression * start = start_guarded().clone(); int which_dim; Statement * r_stmt = range_stmt(stmt); String stmt_tag = r_stmt->tag(); RangeAccessor range_acc( pgm.range_dict_guarded(), *r_stmt ); Symbol *max_sym = pgm.symtab().find_ref("MAX"); Expression * beg = lo.clone(); Expression * stride = by.clone(); Expression * end = &hi; if ((stride->op() == INTEGER_CONSTANT_OP) && ((stride->value() == 1) || (stride->value() == -1))) { end = hi.clone(); } else { /// ... silvius: -1 shows in some cases as ( U_MINUS_OP ( INTEGER_CONSTANT_OP ( 1 ) ) ) if (stride->op() == U_MINUS_OP){ Expression& val=stride->expr_guarded(); if (val.op()==INTEGER_CONSTANT_OP && (val.value() == 1 || val.value() == -1) ) { end = hi.clone(); } } else { /// ... Form the most general expression for the ending value end = ((AIRangeDict &)(pgm.range_dict_guarded())).elim_known_facts(stmt_tag, add(mul(sub(intrinsic_call(id(*max_sym), comma(div(add(sub(end->clone(), beg->clone()), stride->clone()), stride->clone()), constant(0))), constant(1)), stride->clone()), beg->clone()) ); } } /// ... Form pseudo-index with begin:end:stride => pseudo_beg:pseudo_end:pseudo_stride Expression * pseudo_beg = 0; Expression * pseudo_end = 0; Expression * pseudo_stride = 0; Expression * new_start, * new_stride, * new_span; /// ... If the index appears in the start, calc a new dimension if (is_var_in_expr( *start, index)) { /// ... Test the monotonicity of the start expression Monotonicity * mono = test_monotonicity(range_acc, index, stride, start ); if (_monoton == AR_UNKNOWN_MONO) { if (mono->unknown_dir()) { monoton( AR_MONO_UNSURE ); } else { monoton( AR_PROVEN_MONO); } } else { if (mono->unknown_dir()) { monoton( AR_MONO_UNSURE ); } } if (mono->negative()) { /// ... If monotonically decreasing, then reverse the /// ... beginning and ending values and negate the stride. pseudo_beg = end->clone(); pseudo_end = beg->clone(); pseudo_stride = mul(stride->clone(), constant(-1)); } else { pseudo_beg = beg->clone(); pseudo_end = end->clone(); pseudo_stride = stride->clone(); } /// ... Form the new starting expression /// ... new_start = start(I = pseudo_beg) new_start = simplify( substitute_var( start->clone(), index, *pseudo_beg ) ); /// ... Form the new stride expression /// ... new_stride = start(I = I+pseudo_stride) - start(I) Expression * index_plus_stride = add(id(index), pseudo_stride->clone()); new_stride = simplify(sub(substitute_var(start->clone(), index, *index_plus_stride), start->clone())); delete index_plus_stride; /// ... Form the new span expression /// ... new_span = start(I = pseudo_end) - new_start new_span = simplify(sub(substitute_var(start->clone(), index, *pseudo_end), new_start->clone())); AccessDimension *ad; /// ... Don't add a new dimension if the stride is a integer constant 0 if ((new_stride->op() != INTEGER_CONSTANT_OP) || (new_stride->value() != 0)) { ad = new AccessDimension( new_stride, new_span, ACCU_EXACT, mono ); ad->_index = &index; /// ... Determine which position this dimension should occupy (keep the /// ... dimensions sorted by increasing stride value). which_dim = sort_add_dim(ad, range_acc); } else { which_dim = -1; } } else { which_dim = -1; new_start = start->clone(); /// ... Now, check whether the index occurs in any existing span for the descriptor /// ... If it does, we have to replace the occurence with the index value which /// ... maximizes the span for (Iterator<AccessDimension> iter = _dims; iter.valid(); ++iter) { AccessDimension & ad = iter.current(); Expression & span = ad.span_guarded(); if (is_var_in_expr( span, index )) { Expression * one = constant(1); Monotonicity * mono2 = test_monotonicity(range_acc, index, one, &span); delete one; if (mono2->positive()) { ad.span(substitute_var(ad._span->clone(), index, *end->clone())); } else if (mono2->negative()) { ad.span(substitute_var(ad._span->clone(), index, *beg->clone())); } delete mono2; } } } this->start( new_start ); this->summarized_to(&stmt); /// ... Link AbstractAccess to the statement this->pgm_summarized_to(&pgm); /// ... ...and the ProgramUnit delete beg; delete end; delete stride; delete start; delete pseudo_beg; delete pseudo_end; delete pseudo_stride; return which_dim; } /// Check whether a particular access tree contains any access regions /// exhibiting trans-dimensional access (diagonality), triangularity, /// non-affinity, or subscripted subscripts. /// /// If so, mark the AbstractAccess objects as such. void AbstractAccess::check_access_patterns ( ) { static LambdaInfo lambda(0, 0, INLINE_CALL); RefList<AbstractAccess> aa_list; /// ... Collect the list of AbstractAccess objects defining the /// ... nestings of this access, the list of actual array references /// ... for these AbstractAccess objects, and /// ... the list of loop indices of the loops in the nest. Statement * stmt; for (Iterator<AbstractAccess> aa_iter = aa_list; aa_iter.valid(); ++aa_iter) { AbstractAccess & aa = aa_iter.current(); int ndims = aa.number_of_dimensions(); if (ndims == 0) continue; bool is_diagonal = false; bool is_triangular = false; bool is_nonaffine = false; bool is_subsub = false; /// ... Test monotonicity of the whole Access Descriptor bool nonmono = false; for (int i=0; i<ndims; ++i) { const AccessDimension & dim = aa.dimension(i); if (dim.monotonicity().varying() && dim.monotonicity().unknown_dir()) { nonmono = true; } } if (nonmono) { aa.monoton( AR_PROVEN_NON_MONO ); } else { aa.monoton( AR_PROVEN_MONO ); } stmt = aa.summarized_to(); if (stmt->stmt_class() != DO_STMT) continue; /// ... Test for the various subscript forms - /// ... First subscripted-subscripts, second non-affinity, /// ... third triangularity, fourth trans-dimensionality. for (int j=0; j<ndims; ++j) { const AccessDimension & dimj = aa.dimension(j); if (dimj._index == 0) continue; Symbol & index = *(dimj._index); for (int i=0; i<ndims; ++i) { const AccessDimension & dimi = aa.dimension(i); /// ... Find an ARRAY_REF_OP - /// ... If subscripted-subscript in either stride or span, mark it. for (Traverser trav(dimi.stride_guarded(), is_array_ref); trav.valid(); ++trav) { const Expression & exprnode = trav.current(); if (is_var_in_expr(exprnode.subscript(), index)) { aa.mark_subsub(); is_subsub = true; break; } } if (is_subsub) break; for (Traverser trav(dimi.span_guarded(), is_array_ref); trav.valid(); ++trav) { const Expression & exprnode = trav.current(); if (is_var_in_expr(exprnode.subscript(), index)) { aa.mark_subsub(); is_subsub = true; break; } } if (is_subsub) break; /// ... Check stride for an index (non-affine) if ((! is_subsub) && (! is_nonaffine)) { if (is_var_in_expr(dimi.stride_guarded(), index)) { aa.mark_nonaffine(); is_nonaffine = true; } } /// ... Check span for an index (triangular) if ((! is_subsub) && (! is_nonaffine) && (! is_triangular)) { if (is_var_in_expr(dimi.span_guarded(), index)) { aa.mark_triangular(); is_triangular = true; } } } if (is_subsub) break; if ((! is_subsub) && (! is_nonaffine) && (! is_triangular) && (! is_diagonal)) { if (aa.actual_exists()) { /// ... Test trans-dimensional (diagonal) access Expression & expr = aa.actual_guarded(); bool index_appears = false; if (expr.op() == ARRAY_REF_OP) { for (Iterator<Expression> subscr_iter = expr.subscript().arg_list(); subscr_iter.valid(); ++subscr_iter) { Expression & subscr_expr = subscr_iter.current(); if (is_var_in_expr(subscr_expr, index)) { if (index_appears) { aa.mark_diagonal(); is_diagonal = true; } else { index_appears = true; } } } } } } if (is_subsub) break; } } } /// coalesce( ) - Perform the coalescing operation which reduces two /// dimensions to a single one. The conditions are: /// Given n dimensions D0, D1, ... Dn, find a Di and a Dj such that /// SPANi divides SPANj and SPANi+STRIDEi <= STRIDEj. If some coalescing /// happens, return TRUE, otherwise FALSE. bool AbstractAccess::coalesce( ) { bool coalesced = false; /// ... Need at least 2 dimensions for coalescing int ndims = _dims.entries(); if (ndims <= 1) return coalesced; Statement * r_stmt = range_stmt(*_summarized_to); RangeAccessor range_acc( _pgm_summarized_to->range_dict_guarded(), *r_stmt ); for (int i=0; i<ndims; ++i) { p_assert(_dims[i].stride_exists(),"coalesce: Stride missing"); p_assert(_dims[i].span_exists(), "coalesce: Span missing"); } /// ... Use a complete undirected graph as a device to visit /// ... all combinations of dimensions, to try to coalesce them. /// ... The UGraphIterator will not return self-edges (edges in which /// ... both endpoints are the same node). /// ... The coalesce_nodes call below signals the UGraphIterator that /// ... coalescing has occured. It adjusts the internal graph and /// ... resets the iterator so that it will continue by returning only /// ... the dimension combinations which still need to be tested for coalescing. UGraphIterator ugi( ndims ); for ( ; ugi.valid(); ++ugi) { UEdge & edge = ugi.current(); int lodim = edge.node_1( ); int hidim = edge.node_2( ); AccessDimension & dim_lo = _dims[lodim]; AccessDimension & dim_hi = _dims[hidim]; coalesced = this->try_coalescing(range_acc, dim_lo, lodim, dim_hi, hidim, ugi); if (_imprecise_sorting && !coalesced) { coalesced = this->try_coalescing(range_acc, dim_hi, hidim, dim_lo, lodim, ugi); } } return coalesced; } /// Try coalescing on two specific dimensions. If it's legal, do it and adjust /// the given UGraph. We don't need to adjust the _singleton index flag here /// since it should be the same as the _singleton index flag of the /// dimension with the smaller stride, which is the dimension which gets modified /// to hold the new coalesced dimension, so it will be carried across by virtue /// of that. bool AbstractAccess::try_coalescing(RangeAccessor & range_acc, AccessDimension & dim_lo, int lodim, AccessDimension & dim_hi, int hidim, UGraphIterator & ugi) { bool coalesced = false; if (expr_divides(dim_lo.stride_guarded(), dim_hi.stride_guarded())==AR_YES) { Expression * width = simplify(add(dim_lo.span_guarded().clone(), dim_lo.stride_guarded().clone())); Expression * step = simplify(dim_hi.stride_guarded().clone()); Relation rel = range_acc.compare(*width, *step); if (rel.is_greater_equal()) { coalesced = true; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Coalesce: " << *this << " => "; } Expression * new_span = simplify(add(dim_lo.span_guarded().clone(), dim_hi.span_guarded().clone())); dim_lo.span( new_span ); dim_lo._index = 0; /// ... Calculate the overlap characteristic if (rel.is_equal()) { _no_overlap = 1; } else if (rel.is_not_equal()) { _no_overlap = 0; } else { /// ... If rel can't tell equal or not equal, do runtime check dim_lo._check_overlap = true; } /// ... remove the dimension _dims.del(hidim); /// ... If the sorting was imprecise before, it might have been because /// ... of the eliminated dimension. Recheck the sorting. If sorting /// ... is now precise again, the check_sort() function will reset /// ... _imprecise_sorting. if (_imprecise_sorting) this->check_sort(); if (_ar_logging && _ar_logging % 2 == 0) { arlog << *this << endl; } /// ... Coalesce the nodes in the UGraph: /// ... This will reset the UGraphIterator, causing it /// ... to return all the edges still needing to be tested, /// ... without returning those edges it has already returned. ugi.coalesce_nodes( lodim, hidim ); } } return coalesced; } /// Translate the variable references in an AbstractAccess object from /// GSA form to original form. void AbstractAccess::translate_GSA_symbols ( TranslateObject * tobj ) { /// ... First, translate the dimensions for (Iterator<AccessDimension> iter = _dims; iter.valid(); ++iter) { iter.current().translate_GSA_symbols( tobj ); } /// ... Then, translate the start expression _start = tobj->translate_GSA_refs_expr(_start); } void AbstractAccess::check_sort( ) { Statement * r_stmt = range_stmt(*_summarized_to); RangeAccessor range_acc( _pgm_summarized_to->range_dict_guarded(), *r_stmt ); int entries = _dims.entries(); bool problem = false; for (int i=0; i<entries-1; ++i) { Relation rel = range_acc.compare(_dims[i].stride_guarded(), _dims[i+1].stride_guarded()); if (! rel.is_less_than()) { _imprecise_sorting = true; problem = true; break; } } if (! problem) { _imprecise_sorting = false; } } int AbstractAccess::sort_add_dim (AccessDimension * newdim, RangeAccessor & range_acc) { int which_dim; int entries = _dims.entries(); if (entries == 0) { which_dim = 0; } else { which_dim = entries; /// ... If the sorting has been precise up to now, check where to place the /// ... new dimension. If not, skip the sorting check, because we'll have to /// ... check at runtime anyway. if (!_imprecise_sorting) { for (int i=0; i<entries; ++i) { Relation rel = range_acc.compare(*newdim->_stride, _dims[i].stride_guarded()); if (rel.is_less_than()) { which_dim = i; _imprecise_sorting = false; break; } /// ... If we couldn't place the new dimension prior to the last existing dim, /// ... then check whether the new stride is legitimately greater than the last one. if (i == entries-1) { if (rel.is_greater_than()) { _imprecise_sorting = false; } else { _imprecise_sorting = true; } } } } } add_dimension( newdim, which_dim ); return which_dim; } void AbstractAccess::del_dimension( int which_dim ) { p_assert((which_dim >= 0) && (which_dim < _dims.entries()),"Dimension index out of range"); _dims.del(which_dim); } void AbstractAccess::correctness( Expression * e ) { _correctness = e; }

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