Polaris: access_util.cc Source File

access_util.cc Go to the documentation of this file. /// /// /// \file access_util.cc /// #include <stdio.h> #include "Expression/LogicalConstExpr.h" #include "Range/RangeAccessor.h" #include "Range/AIRangeDict.h" #include "Program.h" #include "ProgramUnit.h" #include "Statement/Statement.h" #include "utilities/expression_util.h" #include "Range/range_util.h" #include "Range/RangeDict.h" #include "utilities/switches_util.h" #include "utilities/stmt_util.h" #include "SimBiGraphIterator.h" #include "SimGraphIterator.h" #include "Traverser.h" #include "UBiGraphIterator.h" #include "utilities/access_util.h" void print_access_region_statistics( ostream & o, const RefList<AbstractAccess> & list, Statement & stmt, Symbol & sym ) { if (_ar_prtstats != 1) return; AR_Stats stats; init_ar_statistics( stats ); stats.total = list.entries(); for (Iterator<AbstractAccess> iter = list; iter.valid(); ++iter) { AbstractAccess & access_region = iter.current(); collect_ar_statistics( access_region, stats, sym ); } print_ar_stats_line( o, stmt, stats ); } void print_access_region_statistics( ostream & o, const List<AbstractAccess> & list, Statement & stmt, Symbol & sym ) { if (_ar_prtstats != 1) return; AR_Stats stats; init_ar_statistics( stats ); stats.total = list.entries(); for (Iterator<AbstractAccess> iter = list; iter.valid(); ++iter) { AbstractAccess & access_region = iter.current(); collect_ar_statistics( access_region, stats, sym ); } print_ar_stats_line( o, stmt, stats ); } void init_ar_statistics( AR_Stats & stats ) { stats.print = false; stats.total_dims = 0; stats.total = 0; stats.exact = 0; stats.inexact = 0; stats.proc_boundary = 0; stats.both_same_dims = 0; stats.caller_grtr_dims = 0; stats.callee_grtr_dims = 0; stats.callee_1 = 0; stats.caller_1 = 0; stats.subscr_subscr = 0; stats.match_declared_dim = 0; stats.less_declared_dim = 0; stats.greater_declared_dim = 0; stats.nonaffine = 0; stats.triangular = 0; stats.diagonal = 0; stats.proven_monotonic = 0; stats.proven_nonmonotonic = 0; stats.monotonic_unknown = 0; stats.minnest = 10000000; stats.maxnest = 0; stats.totalnest = 0; stats.base_dc = 0; stats.last_dc = 0; stats.dc_count = 0; stats.base_ars_uniq = 0; stats.last_ars_uniq = 0; stats.ars_uniq_count = 0; stats.base_ars_uniq_dims = 0; stats.last_ars_uniq_dims = 0; stats.ars_uniq_dims_count = 0; stats.base_ars_uniq_strd = 0; stats.last_ars_uniq_strd = 0; stats.ars_uniq_strd_count = 0; stats.base_ars_uniq_dims = 0; stats.last_ars_uniq_dims = 0; stats.ars_uniq_dims_count = 0; stats.base_ars_uniq_dims_st = 0; stats.last_ars_uniq_dims_st = 0; stats.ars_uniq_dims_st_count = 0; } void collect_ar_statistics ( AbstractAccess & access_region, AR_Stats & stats, Symbol & sym ) { if (_ar_prtstats != 1) return; Dimcount * dc_ptr; Accreg_set * ars_ptr; int decl_dims = sym.dim().entries(); /// ... dims in calling context int ar_dims = access_region.number_of_dimensions(); stats.total_dims += ar_dims; Statement * stmt = access_region.summarized_to(); /// if ((stmt->stmt_class() == CALL_STMT) || /// ((stmt->stmt_class() == ASSIGNMENT_STMT) && /// (stmt->rhs().op()==FUNCTION_CALL_OP))) { /// /// if (access_region.inner().entries() == 0) return; /// /// p_assert(access_region.inner().entries() == 1, /// "ARD at CALL has multiple inner ARDs"); /// /// stats.print = true; /// /// stats.proc_boundary++; /// callee_dims = access_region.inner()[0].symbol().dim().entries(); /// if (decl_dims == callee_dims) { /// stats.both_same_dims++; /// } /// if (decl_dims > callee_dims) { /// stats.caller_grtr_dims++; /// if (callee_dims == 1) { /// stats.callee_1++; /// } /// } /// if (decl_dims < callee_dims) { /// stats.callee_grtr_dims++; /// if (decl_dims == 1) { /// stats.caller_1++; /// } /// } /// return; /// } /// if (stmt->stmt_class() == ENTRY_STMT) return; stats.print = true; /// switch (access_region.monoton()) /// { /// case AR_PROVEN_MONO: /// stats.proven_monotonic++; /// break; /// case AR_PROVEN_NON_MONO: /// stats.proven_nonmonotonic++; /// break; /// case AR_UNKNOWN_MONO: /// stats.monotonic_unknown++; /// break; /// } bool found_one; /// bool exact = access_region.accuracy() == ACCU_EXACT; bool exact = true; /// if (exact) { /// stats.exact++; /// } else { /// stats.inexact++; /// } bool subsub = access_region.is_subsub(); if (exact && subsub) { stats.subscr_subscr++; } /// p_assert(access_region.actual_exists(), "No actual expression registered"); /// p_assert((access_region.actual_guarded().op() == ARRAY_REF_OP) || // (access_region.actual_guarded().op() == ID_OP), // "Actual expression must be ARRAY_REF_OP"); bool nonaffine = access_region.is_nonaffine(); if (nonaffine && exact && !subsub) { stats.nonaffine++; } bool triangular = access_region.is_triangular(); if (triangular && exact && !subsub && !nonaffine) { stats.triangular++; } bool diagonal = access_region.is_diagonal(); if (diagonal && !triangular && exact && !subsub && !nonaffine) { stats.diagonal++; } bool normal = exact && !diagonal && !triangular && !subsub && !nonaffine; if ((ar_dims == decl_dims) && normal) stats.match_declared_dim++; if ((ar_dims < decl_dims) && normal) stats.less_declared_dim++; if ((ar_dims > decl_dims) && normal) stats.greater_declared_dim++; int level = access_region.nesting_level(); if (level < stats.minnest) stats.minnest = level; if (level > stats.maxnest) stats.maxnest = level; stats.totalnest += level; if (_ar_match_dims == -1) { _ar_match_dims = switch_value("ar_matchdims"); } if (_ar_match_dims) { /// ... Go through the set of dimensionalities found_one = false; for (dc_ptr = stats.base_dc; dc_ptr; dc_ptr = dc_ptr->next) { if (dc_ptr->dims == ar_dims) { dc_ptr->count++; found_one = true; break; } } if (! found_one) { Dimcount * dc = new Dimcount; stats.dc_count++; dc->count = 1; dc->next = 0; dc->dims = ar_dims; if (stats.base_dc == 0) { stats.base_dc = dc; stats.last_dc = dc; } else { stats.last_dc->next = dc; stats.last_dc = dc; } } /// ... Check for uniqueness found_one = false; for (ars_ptr = stats.base_ars_uniq; ars_ptr; ars_ptr = ars_ptr->next) { if (access_region.match( ars_ptr->ar )) { ars_ptr->count++; found_one = true; break; } } if (! found_one) { Accreg_set * ars = new Accreg_set; stats.ars_uniq_count++; ars->count = 1; ars->next = 0; ars->ar = & access_region; if (stats.base_ars_uniq == 0) { stats.base_ars_uniq = ars; stats.last_ars_uniq = ars; } else { stats.last_ars_uniq->next = ars; stats.last_ars_uniq = ars; } } /// ... Check for uniqueness only considering dimensions (ignoring start expr) found_one = false; for (ars_ptr = stats.base_ars_uniq_dims; ars_ptr; ars_ptr = ars_ptr->next) { if (access_region.match_by_dims( ars_ptr->ar )) { ars_ptr->count++; found_one = true; break; } } if (! found_one) { Accreg_set * ars = new Accreg_set; stats.ars_uniq_dims_count++; ars->count = 1; ars->next = 0; ars->ar = & access_region; if (stats.base_ars_uniq_dims == 0) { stats.base_ars_uniq_dims = ars; stats.last_ars_uniq_dims = ars; } else { stats.last_ars_uniq_dims->next = ars; stats.last_ars_uniq_dims = ars; } } /// ... Check for uniqueness only considering strides found_one = false; for (ars_ptr = stats.base_ars_uniq_strd; ars_ptr; ars_ptr = ars_ptr->next) { if (access_region.match_by_strides( ars_ptr->ar )) { ars_ptr->count++; found_one = true; break; } } if (! found_one) { Accreg_set * ars = new Accreg_set; stats.ars_uniq_strd_count++; ars->count = 1; ars->next = 0; ars->ar = & access_region; if (stats.base_ars_uniq_strd == 0) { stats.base_ars_uniq_strd = ars; stats.last_ars_uniq_strd = ars; } else { stats.last_ars_uniq_strd->next = ars; stats.last_ars_uniq_strd = ars; } } /// ... Check for uniqueness considering all-but-one dimensions found_one = false; for (ars_ptr = stats.base_ars_uniq_dims; ars_ptr; ars_ptr = ars_ptr->next) { if (access_region.match_by_dims_except_1( ars_ptr->ar )) { ars_ptr->count++; found_one = true; break; } } if (! found_one) { Accreg_set * ars = new Accreg_set; stats.ars_uniq_dims_count++; ars->count = 1; ars->next = 0; ars->ar = & access_region; if (stats.base_ars_uniq_dims == 0) { stats.base_ars_uniq_dims = ars; stats.last_ars_uniq_dims = ars; } else { stats.last_ars_uniq_dims->next = ars; stats.last_ars_uniq_dims = ars; } } /// ... Check for uniqueness considering start and all-but-one dimension found_one = false; for (ars_ptr = stats.base_ars_uniq_dims_st; ars_ptr; ars_ptr = ars_ptr->next) { if (access_region.match_by_start_dims_except_1( ars_ptr->ar )) { ars_ptr->count++; found_one = true; break; } } if (! found_one) { Accreg_set * ars = new Accreg_set; stats.ars_uniq_dims_st_count++; ars->count = 1; ars->next = 0; ars->ar = & access_region; if (stats.base_ars_uniq_dims_st == 0) { stats.base_ars_uniq_dims_st = ars; stats.last_ars_uniq_dims_st = ars; } else { stats.last_ars_uniq_dims_st->next = ars; stats.last_ars_uniq_dims_st = ars; } } } return; } void print_ar_stats_line( ostream & o, Statement & stmt, AR_Stats & stats ) { o << "ARSTATS: "; if (stmt.stmt_class() == DO_STMT) { o << stmt.get_loop_name(); } else if (stmt.stmt_class() == CALL_STMT) { o << "CALL_STMT"; } else if (stmt.stmt_class() == ENTRY_STMT) { o << "ENTRY_STMT"; } else { o << "UNKNOWN_STMT"; } o << " TOT: " << stats.total << " #MATCH_DECL: " << stats.match_declared_dim; o << " >DECLARED_DIM: " << stats.greater_declared_dim << " <DECLARED_DIM: " << stats.less_declared_dim ; o << " NONAFFINE: " << stats.nonaffine; o << " TRIANG: " << stats.triangular; o << " DIAG: " << stats.diagonal; o << " NEST: " << stats.minnest << " "<< stats.maxnest << " " << float(stats.totalnest)/float(stats.total); o << " XCT: " << stats.exact << " INXCT: " << stats.inexact; o << " SS: " << stats.subscr_subscr; o << " PROV_MONO: " << stats.proven_monotonic; o << " PROV_NMONO: " << stats.proven_nonmonotonic; o << " MONO_UNK: " << stats.monotonic_unknown; o << " CALLS: " << stats.proc_boundary; o << " CALLER>: " << stats.caller_grtr_dims; o << " CALLEE>: " << stats.callee_grtr_dims; o << " CALLER1: " << stats.caller_1; o << " CALLEE1: " << stats.callee_1; o << " #UNIQ: " << stats.ars_uniq_count << " DIMS: " << stats.ars_uniq_dims_count; o << " STRD: " << stats.ars_uniq_strd_count << " DIMS-1: " << stats.ars_uniq_dims_count; o << " DIMS-1/STRT: " << stats.ars_uniq_dims_st_count << " #DIFF-DIM: " << stats.dc_count; o << " TOT_DIMS: " << stats.total_dims; o << " DIM-LIST: "; for (Dimcount * dc_ptr = stats.base_dc; dc_ptr; dc_ptr = dc_ptr->next) { o << " " << dc_ptr->dims; } o << endl; if (stats.caller_grtr_dims > stats.callee_1) { o << "RESHAPING (CALLER>): N to M" << endl; } if (stats.callee_grtr_dims > stats.caller_1) { o << "RESHAPING (CALLEE>): N to M" << endl; } } /// ar_intersect - /// When you are not sure: /// OVERESTIMATE means A <intersect> B => A <union> B (maximize the result) /// UNDERESTIMATE means A <intersect> B => <emptyset> (minimize the result) void ar_intersect(List<AbstractAccess> & list1, List<AbstractAccess> & list2, AR_CONSERVATIVE direction, List<AbstractAccess> & result, IPAStats & istats) { if ((list1.entries() == 0) || (list2.entries() == 0)) return; istats.ar_inter1.restart(); istats.ar_inter1_elems1.add(list1.entries()); istats.ar_inter1_elems2.add(list2.entries()); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Intersect1:" << list1 << " and " << list2 ; } RefList<AbstractAccess> discard1; RefList<AbstractAccess> discard2; SimBiGraph sbg(list1, list2 ); SimBiGraphIterator sbgi( sbg ); for ( ; sbgi.list1_valid(); sbgi.next_list1_node()) { int ard1 = sbgi.current_list1(); AbstractAccess & candidate = list1[ard1]; for ( ; sbgi.list2_valid(); sbgi.next_list2_node()) { int ard2 = sbgi.current_list2( ); SimEdge & edge = sbgi.current(); List<AbstractAccess> new_ard1; List<AbstractAccess> new_ard2; Statement * ref_stmt; if (candidate.actual_stmt()) { ref_stmt = candidate.actual_stmt(); } else { ref_stmt = range_stmt(*(candidate.summarized_to())); } RangeAccessor range_acc(candidate.pgm_summarized_to()->range_dict_guarded(), *ref_stmt); istats.ar_inter1.stop(); /// ... Use AND as the Meet operator, since this is for straight-line code bool inter = intersect_ARDs(list1[ard1], list2[ard2], range_acc, edge, direction, new_ard1, new_ard2, result, AR_AND, istats); istats.ar_inter1.restart(); if (inter) { for (int i=0; i<new_ard2.entries(); ++i) { if (!ar_descriptor_member(list2, new_ard2[i])) { list2.ins_last(new_ard2.grab(i)); } } if (!discard2.member(list2[ard2])) discard2.ins_last(list2[ard2]); for (int i=0; i<new_ard1.entries(); ++i) { if (!ar_descriptor_member(list1, new_ard1[i])) { list1.ins_last(new_ard1.grab(i)); } } if (!discard1.member(list1[ard1])) discard1.ins_last(list1[ard1]); break; } } } /// ... discard the indicated descriptors for (Iterator<AbstractAccess> iter = discard1; iter.valid(); ++iter) { list1.del(iter.current()); } for (Iterator<AbstractAccess> iter = discard2; iter.valid(); ++iter) { list2.del(iter.current()); } if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Result: list1" << list1 << " list2:" << list2 << " Result:" << result; } istats.ar_inter1.stop(); } /// ar_intersect - Internal intersection within a single list /// When you are not sure: /// OVERESTIMATE means A <intersect> B => A <union> B (maximize the result) /// UNDERESTIMATE means A <intersect> B => <emptyset> (minimize the result) /// /// Only report whether an intersection exists or not, considering bool ar_intersect(List<AbstractAccess> & list, AR_CONSERVATIVE direction, IPAStats & istats) { if (list.entries() < 2) return false; istats.ar_inter4.restart(); istats.ar_inter4_elems.add(list.entries()); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Intersect4:" << list ; } SimGraph sg(list); SimGraphIterator sgiter( sg ); for ( ; sgiter.valid(); ++sgiter) { SimEdge & edge = sgiter.current(); AbstractAccess * ard1 = edge.node_1(); AbstractAccess * ard2 = edge.node_2(); RangeAccessor range_acc(ard1->pgm_summarized_to()->range_dict_guarded(), *(range_stmt(*(ard1->summarized_to()))) ); istats.ar_inter4.stop(); List<AbstractAccess> new_ard1; List<AbstractAccess> new_ard2; List<AbstractAccess> result; /// ... Use AND as the Meet operator since this is for straightline code bool inter = intersect_ARDs(*ard1, *ard2, range_acc, edge, direction, new_ard1, new_ard2, result, AR_AND, istats); istats.ar_inter4.restart(); bool plausible = ar_plausible_execution(result); if (inter && plausible) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << " - Intersects"; } istats.ar_inter4.stop(); return true; } } istats.ar_inter4.stop(); if (_ar_logging && _ar_logging % 2 == 0) { arlog << " - No Intersection"; } istats.ar_inter4.stop(); return false; } /// ar_subregion /// is ard1 a subregion of ard2 ? bool ar_subregion(AbstractAccess & ard1, AbstractAccess & ard2, SimEdge & edge, AR_CONSERVATIVE direction, Array<int> *match ) { SimilarityType simtype = edge.type(); if (_ar_logging && _ar_logging % 2 == 0) { arlog << endl << "Subregion- ARD1:" << ard1 << " vs ARD2:" << ard2 ; } AbstractAccess * aa1 = &ard1; AbstractAccess * aa2 = &ard2; int dims1 = aa1->number_of_dimensions(); int dims2 = aa2->number_of_dimensions(); if ((simtype == SIM_EQUIV) || ((simtype == SIM_EQUIV_SEMI) && (dims1 < dims2))) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-YES-" << endl; } return true; } bool newaa1 = false; bool newaa2 = false; RangeAccessor range_acc(aa2->pgm_summarized_to()->range_dict_guarded(), *(range_stmt(*(aa2->summarized_to()))) ); Relation rel_start = range_acc.compare(aa1->start_guarded(), aa2->start_guarded()); /// ... If either ARD1's start is less than ARD2's, or we just can't tell /// ... where ARD1 starts in relation to ARD2, then report NO if (!rel_start.is_greater_equal()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-NO-" << endl; } return false; } /// ... Now we know aa2 is left of aa1 if (dims2 == 1) { /// ... When aa2 is 1-dimensional, stride 1, if /// ... aa1 fits totally inside aa2, then it is a subregion if (is_integer_one(aa2->dimension(0).stride_guarded())) { Expression *lastoff1 = aa1->lastoffset(); Expression *lastoff2 = aa2->lastoffset(); Relation rel_off = range_acc.compare(*lastoff1, *lastoff2); if (rel_off.is_less_equal()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-YES-" << endl; } return true; } } } Array<int> * match_index = 0; /// ... If pred(ARD1) implies pred(ARD2), then check the regions for subregion-ness if (ar_implies(*aa1, *aa2)) { /// ... Take care of the _SEMI cases. if ((simtype == SIM_DIM_EQUIV_SEMI) || (simtype == SIM_STRIDE_EQUIV_SEMI)) { if (dims1 < dims2) { /// ... Copy ARD1 AbstractAccess * new_aa = aa1->clone(); Array<int> * new_match_index = new Array<int>; new_match_index->resize(dims2); if (match == 0) { match_index = edge.edge()->stridematch(); } else { match_index = match; } /// ... Invert match_index Array<int> * inverted_match_index = invert_match(match_index, dims2); /// ... Check whether we can determine subregion-ness immediately if (simtype == SIM_DIM_EQUIV_SEMI) { /// ... If ARD1's dimensions each match a dimension in ARD2, the difference /// ... between the starting points is a multiple of some non-matching dimension's /// ... stride, and the difference between the starting points is less than the /// ... span of that non-matching dimension, then ARD1 is a subregion of ARD2. Expression *diff = simplify(sub(aa1->start_guarded().clone(), aa2->start_guarded().clone())); for (int ii=0; ii<dims2; ++ii) { if ((*inverted_match_index)[ii] == -1) { /// ... No match in ARD1 for dim ii in ARD2 if (expr_divides(aa2->dimension(ii).stride_guarded(), *diff)==AR_YES) { Relation rel = range_acc.compare(*diff, aa2->dimension(ii).span_guarded()); if (rel.is_less_equal()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-YES-" << endl; } delete diff; delete inverted_match_index; delete new_aa; return true; } } } } delete diff; } /// ... Make a new descriptor for aa1 with strides equivalent to those in aa2 and zero spans /// ... Add dimensions from ARD2 which were not matched, set spans to 0 int new_dim = dims1; /// ... add_dimension does ins_last for (int ii=0; ii<dims2; ++ii) { if ((*inverted_match_index)[ii] == -1) { AccessDimension * dim =aa2->dimension(ii).clone(); dim->span(constant(0)); new_aa->add_dimension(dim); (*new_match_index)[new_dim] = ii; ++new_dim; } else { (*new_match_index)[(*inverted_match_index)[ii]] = ii; } } delete inverted_match_index; match_index = new_match_index; aa1 = new_aa; newaa1 = true; dims1 = dims2; simtype = SIM_STRIDE_EQUIV; } else { /// ... Copy ARD2 AbstractAccess * new_aa = aa2->clone(); Array<int> * new_match_index = new Array<int>; new_match_index->resize(dims1); if (match == 0) { match_index = edge.edge()->stridematch(); } else { match_index = match; } for (int ii=0; ii<dims1; ++ii) { (*new_match_index)[ii] = (*match_index)[ii]; } /// ... Add dimensions from ARD1 which were not matched, set spans to 0 int new_dim = dims2; for (int ii=0; ii<dims1; ++ii) { if ((*match_index)[ii] == -1) { AccessDimension * dim =aa1->dimension(ii).clone(); dim->span(constant(0)); new_aa->add_dimension(dim); (*new_match_index)[ii] = new_dim; ++new_dim; } } match_index = new_match_index; aa2 = new_aa; newaa2 = true; dims2 = dims1; simtype = SIM_STRIDE_EQUIV; } } else { if (match == 0) { match_index = edge.edge()->stridematch(); } else { match_index = match; } } Expression * lastoffset_1 = aa1->lastoffset(); Expression * lastoffset_2 = aa2->lastoffset(); if ((simtype == SIM_STRIDE_EQUIV) && (rel_start.is_equal())) { /// ... If all spans of ard1 are less or equal to the associated spans of ard2 /// ... we have a subregion bool success = true; for (int i=0; i < dims1; ++i) { Relation relspan = range_acc.compare(aa1->dimension(i).span_guarded(), aa2->dimension(((*match_index)[i])).span_guarded()); if (relspan.is_greater_than()) { success = false; break; } } if (success) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-YES-" << endl; } if (newaa1) { delete aa1; delete match_index; } if (newaa2) { delete aa2; delete match_index; } return true; } } if ((simtype == SIM_STRIDE_EQUIV) && (rel_start.is_greater_than())) { /// ... Find one stride in ard2 and a matching dim in ard1, /// ... such that the difference between the starting /// ... points of the two ards is a multiple of that stride and /// ... offset_1 + span_1 <= offset_2 + span_2, PLUS /// ... for all other dims span_1 <= span_2 Array<int> * inverted_match_index = invert_match(match_index, dims2); Expression *diff = simplify(sub(aa1->start_guarded().clone(), aa2->start_guarded().clone())); int mult_dim = -1; for (int ii=0; ii<dims2; ++ii) { if (expr_divides(aa2->dimension(ii).stride_guarded(), *diff)==AR_YES) { Expression *sum1 = simplify(add(aa1->start_guarded().clone(), aa1->dimension((*inverted_match_index)[ii]).span_guarded().clone())); Expression *sum2 = simplify(add(aa2->start_guarded().clone(), aa2->dimension(ii).span_guarded().clone())); Relation rel = range_acc.compare(*sum1, *sum2); delete sum1; delete sum2; if (rel.is_less_equal()) { mult_dim = (*inverted_match_index)[ii]; break; } } } delete inverted_match_index; delete diff; if (mult_dim != -1) { bool success = true; for (int ii=0; ii<dims1; ++ii) { if (ii == mult_dim) continue; Relation rel = range_acc.compare(aa1->dimension(ii).span_guarded(), aa2->dimension((*match_index)[ii]).span_guarded()); if (!rel.is_less_equal()) { success = false; } } if (success) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-YES-" << endl; } if (newaa1) { delete aa1; delete match_index; } if (newaa2) { delete aa2; delete match_index; } return true; } } } Relation rel_end = range_acc.compare(*lastoffset_1, *lastoffset_2); if ((dims2 == 1) && (aa2->dimension(0).stride_guarded().op() == INTEGER_CONSTANT_OP) && (aa2->dimension(0).stride_guarded().value() == 1) && rel_start.is_greater_equal() && rel_end.is_less_equal()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-YES-" << endl; } if (newaa1) { delete aa1; delete match_index; } if (newaa2) { delete aa2; delete match_index; } return true; } if (rel_start.is_less_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-NO-" << endl; } if (newaa1) { delete aa1; delete match_index; } if (newaa2) { delete aa2; delete match_index; } return false; } if (rel_end.is_greater_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-NO-" << endl; } if (newaa1) { delete aa1; delete match_index; } if (newaa2) { delete aa2; delete match_index; } return false; } } /// ... If we get to this point, we just don't know, so let the /// ... conservative direction determine how we respond. if (direction == UNDERESTIMATE) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-NO-" << endl; } if (newaa1) { delete aa1; delete match_index; } if (newaa2) { delete aa2; delete match_index; } return false; } if (_ar_logging && _ar_logging % 2 == 0) { arlog << "-YES-" << endl; } if (newaa1) { delete aa1; delete match_index; } if (newaa2) { delete aa2; delete match_index; } return true; /// ... direction == OVERESTIMATE } /// append ard to list void ar_append(List<AbstractAccess> & list, AbstractAccess * ard) { if (ard) { for (Iterator<AbstractAccess> iter = list; iter.valid(); ++iter) { if (ar_descriptors_equal(iter.current(), *ard)) { return; } } list.ins_last(ard); } } /// append list2 to list1 void ar_append(List<AbstractAccess> & list1, List<AbstractAccess> & list2, IPAStats & istats) { if (list2.entries() == 0) return; for (Iterator<AbstractAccess> iter = list2; iter.valid(); ++iter) { if (iter.current().exec_predicate_false()) continue; list1.ins_last(iter.current().clone()); } return; } /// append list2 to list1, changing the predicate of the elements of list2 to /// a new predicate consisting of the AR_MEET applied to the predicates of /// AbstractAccess descriptors lista[indexa] and listb[indexb]. void ar_append_new_pred(List<AbstractAccess> & list1, List<AbstractAccess> & list2, List<AbstractAccess> & lista, int indexa, List<AbstractAccess> & listb, int indexb, AR_MEET meet_op, PredicateRepository & repos, IPAStats & istats) { AbstractAccess & ard1 = lista[indexa]; AbstractAccess & ard2 = listb[indexb]; if (list2.entries() == 0) return; for (Iterator<AbstractAccess> iter = list2; iter.valid(); ++iter) { AbstractAccess * descr = iter.current().clone(); switch(meet_op) { case AR_X: descr->exec_predicate(ard1.exec_predicate()); break; case AR_Y: descr->exec_predicate(ard2.exec_predicate()); break; case AR_AND: descr->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: descr->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: descr->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: descr->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } list1.ins_last(descr); } } AbstractAccess * compute_abstract_access( const Expression & expr, Statement * stmt, AR_TYPE artype ) { Expression * start; if (expr.base_variable_ref() == 0) return 0; if ((expr.base_variable_ref()->sym_class() != VARIABLE_CLASS) && (expr.base_variable_ref()->sym_class() != FUNCTION_CLASS)) { return 0; } const Symbol * sym = expr.base_variable_ref(); /// if (! sym->is_array()) return 0; ---Removed to compute ARDs for scalars also /// ... If this is a GSA symbol, find the base symbol for it if ((sym->sym_class() == VARIABLE_CLASS) && ((VariableSymbol *)sym)->is_gsa_symbol()) { sym = &(((VariableSymbol * )sym)->gsa_base_symbol()); } if (expr.op() == ARRAY_REF_OP) { start = linearize_zero_registered( expr.subscript().clone(), *((VariableSymbol *)sym) ); } else { start = constant( 0 ); } List<AccessDimension> adl; AbstractAccess * aa = new AbstractAccess(*sym, adl, start, ACCU_EXACT, artype); aa->add_actual( stmt, expr.clone() ); /// ... Add the actual expression to the rep aa->byte_size(sym->type().size()); /// ... Set the byte size of the descriptor. if (artype == AR_READ) { aa->read_only(true); } if (artype == AR_WRITE) { aa->write_first(true); } aa->no_overlap(true); return aa; } SimilarityType contig_type (SimilarityType oldtype) { SimilarityType new_type; switch (oldtype) { case SIM_EQUIV_SEMI: case SIM_DIM_EQUIV_SEMI: case SIM_STRIDE_EQUIV_SEMI: new_type = SIM_STRIDE_EQUIV_SEMI; break; case SIM_EQUIV: case SIM_DIM_EQUIV: new_type = SIM_STRIDE_EQUIV; break; case SIM_STRIDE_EQUIV: case SIM_DIM_EQUIV_UP: case SIM_STRIDE_EQUIV_UP: new_type = SIM_STRIDE_EQUIV_UP; break; case SIM_NOT_SIMILAR: new_type = SIM_NOT_SIMILAR; break; case SIM_UNKNOWN: new_type = SIM_UNKNOWN; break; default: p_abort("Bad type for SimEdgeKernel"); break; } return new_type; } /// result <- list1 - list2 /// Here, when we don't know for sure, /// UNDERESTIMATE means that A - B => <empty set> /// and OVERESTIMATE means that A - B => A void ar_subtract(List<AbstractAccess> & list1, List<AbstractAccess> & list2, AR_CONSERVATIVE direction, List<AbstractAccess> & result) { if (list1.entries() == 0) return; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Subtract: " << list1 << " - " << list2 << endl; } p_assert(&list1 != &result, "Use other ar_subtract when &list1==&result"); if (list2.entries() == 0) { for (Iterator<AbstractAccess> iter = list1; iter.valid(); ++iter) { result.ins_first(iter.current().clone()); } if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Result: " << result; } return; } AbstractAccess & aa = list1[0]; RangeAccessor range_acc(aa.pgm_summarized_to()->range_dict_guarded(), *(range_stmt(*(aa.summarized_to()))) ); SimBiGraph sbg(list1, list2 ); SimBiGraphIterator sbgi( sbg ); for ( ; sbgi.list1_valid(); sbgi.next_list1_node()) { int ard1 = sbgi.current_list1(); bool keep = true; for ( ; sbgi.list2_valid(); sbgi.next_list2_node()) { int ard2 = sbgi.current_list2( ); SimEdge & edge = sbgi.current(); SimilarityType simtype = edge.type(); if (simtype == SIM_EQUIV) { keep = false; break; } /// ... if lastoffset[A] < baseoffset[B] Relation rel1 = range_acc.compare(*list1[ard1].lastoffset(), list2[ard2].start_guarded()); if (rel1.is_less_than()) continue; Relation rel2 = range_acc.compare(*list2[ard2].lastoffset(), list1[ard1].start_guarded()); if (rel2.is_less_than()) continue; if (ar_subregion(list1[ard1], list2[ard2], edge, direction)) { keep = false; break; } } if (keep) { result.ins_first(list1[ard1].clone()); } else if (direction == OVERESTIMATE) { result.ins_first(list1[ard1].clone()); } } if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Result: " << result; } } /// list1 <- list1 - list2 /// Here, when we don't know for sure, /// UNDERESTIMATE means that A - B => <empty set> /// and OVERESTIMATE means that A - B => A void ar_subtract(List<AbstractAccess> & list1, List<AbstractAccess> & list2, AR_CONSERVATIVE direction) { if (list1.entries() == 0) return; if (list2.entries() == 0) return; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Subtract: " << list1 << " - " << list2; } AbstractAccess & aa = list1[0]; RangeAccessor range_acc(aa.pgm_summarized_to()->range_dict_guarded(), *(range_stmt(*(aa.summarized_to()))) ); RefList<AbstractAccess> discard; SimBiGraph sbg(list1, list2 ); SimBiGraphIterator sbgi( sbg ); for ( ; sbgi.list1_valid(); sbgi.next_list1_node()) { int ard1 = sbgi.current_list1(); AbstractAccess & candidate = list1[ard1]; bool determined = false; for ( ; sbgi.list2_valid(); sbgi.next_list2_node()) { int ard2 = sbgi.current_list2( ); SimEdge & edge = sbgi.current(); SimilarityType simtype = edge.type(); if (simtype == SIM_EQUIV) { discard.ins_first(candidate); determined = true; break; } /// ... if lastoffset[A] < baseoffset[B] Relation rel1 = range_acc.compare(*list1[ard1].lastoffset(), list2[ard2].start_guarded()); if (rel1.is_less_than()) continue; Relation rel2 = range_acc.compare(*list2[ard2].lastoffset(), list1[ard1].start_guarded()); if (rel2.is_less_than()) continue; if (ar_subregion(list1[ard1], list2[ard2], edge, direction)) { discard.ins_first(candidate); determined = true; break; } } if (! determined) { if (direction == UNDERESTIMATE) { discard.ins_first(candidate); } } } for (Iterator<AbstractAccess> iter = discard; iter.valid(); ++iter) { list1.del(iter.current()); } if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Result in list1: " << list1; } } void check_access_patterns(Program & prog, ProgramUnit & pgm) { for (Iterator<Statement> iter = pgm.stmts(); iter.valid(); ++iter) { Statement & stmt = iter.current(); if (stmt.access_table_exists()) { for (KeyIterator<Symbol, SymbolAccess> ar_iter = stmt.iter_access_table_guarded(); ar_iter.valid(); ++ar_iter) { SymbolAccess & sa = ar_iter.current_data(); /// ... Iterate through the read accesses for (Iterator<AbstractAccess> rd_iter = sa.iter_read(); rd_iter.valid(); ++rd_iter) { AbstractAccess & aa = rd_iter.current(); aa.check_access_patterns(); } /// ... Iterate through the write accesses for (Iterator<AbstractAccess> wr_iter = sa.iter_write(); wr_iter.valid(); ++wr_iter) { AbstractAccess & aa = wr_iter.current(); aa.check_access_patterns(); } // Iterate through the read/write accesses for (Iterator<AbstractAccess> rdwr_iter = sa.iter_readwrite(); rdwr_iter.valid(); ++rdwr_iter) { AbstractAccess & aa = rdwr_iter.current(); aa.check_access_patterns(); } } } } } void simplify_descriptors( List<AbstractAccess> & list, IPAStats & istats ) { bool changed = false; if (list.entries() == 0) return; istats.simp_descr.restart(); istats.simp_descr_elems.add(list.entries()); /// ... eliminate all descriptors with .FALSE. execution predicates for (Mutator<AbstractAccess> iter = list; iter.valid(); ++iter) { if (iter.current().exec_predicate_false()) { iter.del(); } } elim_equivalent_descrs( list, istats ); istats.coal_tim.restart(); if (_ar_coalesce) { for (Iterator<AbstractAccess> outer_iter = list; outer_iter.valid(); ++outer_iter) { changed = outer_iter.current().coalesce(); } } istats.coal_tim.stop(); SimTypeOfChange change; if (_ar_aggregate && (list.entries() > 1)) { /// ... Build similarity graph: /// ... Match up all combinations of descriptors if (_ar_logging && _ar_logging % 2 == 0) { arlog << endl << "Simplify descriptors:" << endl; int i = 0; for (Iterator<AbstractAccess> it=list; it.valid(); ++it,++i) { arlog << "[" << i << "]" << it.current() << endl; } arlog << endl; } SimGraph sg( list ); sg.print_similarities(); /// ... First, eliminate all but one in the same equivalence class SimGraphIterator sgit( sg ); for ( ; sgit.valid(); ++sgit) { SimEdge & edge = sgit.current(); AbstractAccess * descr1 = edge.node_1(); AbstractAccess * descr2 = edge.node_2(); if (descr1->pgm_summarized_to() != descr2->pgm_summarized_to()) continue; /// ... If the descriptors are structurally equivalent and neither /// ... have execution predicates: if (edge.type() == SIM_EQUIV) { if (ar_predicates_equal(*descr1, *descr2)) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Equivalence: " << *descr1 << " and " << *descr2 << endl; } list.del(*descr2); sgit.delete_node(*descr2); /// ... adjust similarity graph sgit.record_change( SIM_EQUIVALENCE, edge ); } else if (ar_predicates_negation(*descr1, *descr2)) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Negation: " << *descr1 << " and " << *descr2 << endl; } list.del(*descr2); sgit.delete_node(*descr2); descr1->exec_predicate(-1); /// ... Set predicate .TRUE. for remaining descriptor /// ... adjust similarity graph sgit.record_change( SIM_EQUIVALENCE, edge ); } else { /// ... Form the OR of the predicates if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ORing predicates: " << *descr1 << " and " << *descr2 << endl; } PredicateRepository & repos = descr1->pgm_summarized_to()->pred_repos(); Expression * descr1_pred = repos.predicate(descr1->exec_predicate())->clone(); Expression * descr2_pred = repos.predicate(descr2->exec_predicate())->clone(); Expression * new_pred = simplify(or(descr1_pred,descr2_pred)); list.del(*descr2); sgit.delete_node(*descr2); descr1->exec_predicate(repos.ins(new_pred)); } } else if (ar_subregion(*descr1, *descr2, edge, UNDERESTIMATE)) { /// ... ar_subregion uses "ar_implies" to see if /// ... descr1's exec predicate implies descr2's exec predicate sgit.record_change( SIM_SUBREG_NODE2, edge ); } } if (_ar_interleave) { /// ... Let the user tell us how much effort to apply /// ... to the interleaving test. int size_limit = ar_effort_limit(); if ( (size_limit == -1) || (list.entries() < size_limit)) { istats.interl_tim.restart(); /// ... Check for interleaving pattern among STRIDE_EQUIVALENT descriptors RefList<AbstractAccess> * interleave_list = ar_interleave(sgit, sg); int max_entries = interleave_list->entries(); if (max_entries > 0) { Iterator<AbstractAccess> iter = interleave_list; /// ... New combined descriptor AbstractAccess & combined = iter.current(); /// ... Remove eliminated nodes from list and graph for (++iter; iter.valid(); ++iter) { AbstractAccess & aa = iter.current(); list.del(aa); sgit.delete_node(aa); } sgit.mark_unknown(combined); } delete interleave_list; istats.interl_tim.stop(); } } istats.agg_tim.restart(); /// ... Check for contiguous aggregation sgit.reset(); for ( ; sgit.valid(); ++sgit) { SimEdge & edge = sgit.current(); if (! ar_predicates_equal(*(edge.node_1()), *(edge.node_2()))) continue; change = ar_aggregate( edge, sg, list ); if ( change != SIM_NOCHANGE ) { /// ... adjust similarity graph sgit.record_change( change, edge ); if (_ar_coalesce) { if (change == SIM_CONTIG_NODE1) { changed = edge.node_1()->coalesce(); if (changed) { sgit.record_change( SIM_COALESCE_NODE1, edge ); } } else if (change == SIM_CONTIG_NODE2) { changed = edge.node_2()->coalesce(); if (changed) { sgit.record_change( SIM_COALESCE_NODE2, edge ); } } } sg.print_similarities(); } } istats.agg_tim.stop(); } istats.simp_descr.stop(); } RefList<AbstractAccess> * ar_interleave( SimGraphIterator & sgit, SimGraph & sg ) { RangeAccessor * range_acc = sg.range_acc( ); sgit.reset(); List<Expression> dist_list; Expression * distance; /// ... Build chains of equidistant offsets Map<Expression,List<RefList<AbstractAccess> > > offset_db; for ( ; sgit.valid(); ++sgit) { SimEdge & edge = sgit.current(); if (edge.type() != SIM_DIM_EQUIV) continue; AbstractAccess * node1 = edge.node_1(); AbstractAccess * node2 = edge.node_2(); if (! ar_predicates_equal(*node1, *node2)) continue; bool reverse = false; distance = simplify(sub(node1->start_guarded().clone(), node2->start_guarded().clone())); dist_list.ins_first(distance); EXPR_SIGN sign = range_acc->signz(*distance); if (sign == NEG_EXPR) { distance = simplify(sub(node2->start_guarded().clone(), node1->start_guarded().clone())); dist_list.ins_first(distance); reverse = true; } bool constant_distance = false; if (distance->op() == INTEGER_CONSTANT_OP) { constant_distance = true; } bool added = false; for (KeyIterator<Expression,List<RefList<AbstractAccess> > > key_iter = offset_db; key_iter.valid(); ++key_iter) { Expression & keydist = key_iter.current_key(); List<RefList<AbstractAccess> > & chain_list = key_iter.current_data(); /// ... First use a cheap comparison to find it if (constant_distance) { if (keydist.op() != INTEGER_CONSTANT_OP) continue; if (distance->value() == keydist.value()) { if (reverse) { add_to_chain(node1, node2, chain_list); added = true; } else { add_to_chain(node2, node1, chain_list); added = true; } } else continue; } else { /// ... Then, if necessary, use a range comparison Relation rel = range_acc->compare(*distance, keydist); if (rel.is_equal()) { if (reverse) { add_to_chain(node2, node1, chain_list); added = true; } else { add_to_chain(node1, node2, chain_list); added = true; } } } } /// ... If the current distance wasn't added to an existing chain, /// ... start a new chain if (!added) { List<RefList<AbstractAccess> > * lists = new List<RefList<AbstractAccess> >; RefList<AbstractAccess> * chain = new RefList<AbstractAccess>; if (reverse) { chain->ins_first(*node2); chain->ins_first(*node1); } else { chain->ins_first(*node1); chain->ins_first(*node2); } lists->ins_first(chain); offset_db.ins(*distance, lists); } } /// ... Now, find the longest single chain and use that for interleaving. RefList<AbstractAccess> * longest_list = 0; Expression * longest_distance = 0; int max_entries = -1; for (KeyIterator<Expression,List<RefList<AbstractAccess> > > key_iter = offset_db; key_iter.valid(); ++key_iter) { List<RefList<AbstractAccess> > & chain_list = key_iter.current_data(); for (Iterator<RefList<AbstractAccess> > iter_list = chain_list; iter_list.valid(); ++iter_list) { RefList<AbstractAccess> & aa_list = iter_list.current(); if (aa_list.entries() > max_entries) { max_entries = aa_list.entries(); longest_list = &aa_list; longest_distance = &(key_iter.current_key()); } } } /// ... Return the longest chain RefList<AbstractAccess> * return_list = new RefList<AbstractAccess>; if (max_entries == -1) return return_list; if ((longest_distance->op() == INTEGER_CONSTANT_OP) && (longest_distance->value() == 1)) { /// ... drop through } else if (max_entries < 3) { return return_list; } if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Interleaving: "; } Iterator<AbstractAccess> iter = longest_list; p_assert(iter.valid(), "Longest list was empty"); return_list->ins_last(iter.current()); /// ... Add a new dimension to descriptor with smallest offset /// ... to represent all descriptors on the list. Expression * span = simplify(mul(constant(max_entries-1),longest_distance->clone())); AccessDimension * newdim = new AccessDimension(longest_distance->clone(), span); int which_dim = (*return_list)[0].sort_add_dim(newdim, *range_acc); AbstractAccess & combined = (*return_list)[0]; combined.calc_overlap( which_dim ); if (_ar_logging && _ar_logging % 2 == 0) { arlog << combined << " "; } for (++iter; iter.valid(); ++iter) { AbstractAccess & aa = iter.current(); if (_ar_logging && _ar_logging % 2 == 0) { arlog << aa << " "; } /// ... In "combined", save the info that dimensions need overlap checking Iterator<AccessDimension> iter = aa.iter_dims(); for (int index=0; iter.valid(); ++iter,++index) { if (iter.current().check_overlap()) { combined.set_check_overlap(index, true); } } return_list->ins_last(aa); } /// ... Calc_overlap where necessary if (! combined.is_imprecise()) { Iterator<AccessDimension> iter2 = combined.iter_dims(); for (int index=0; iter2.valid(); ++iter2,++index) { if (iter2.current().check_overlap()) { combined.calc_overlap(index); } } } if (_ar_logging && _ar_logging % 2 == 0) { arlog << " -> " << combined << endl; } return return_list; } /// Add a link node1->node2 to the chain(s) in the List of RefLists. /// Since we have removed all-but-one descriptors in each equivalence /// class, each node1->node2 link will be added either at the beginning /// or the end of one of the RefLists, or else will serve to tie two /// RefLists together into a single list. void add_to_chain(AbstractAccess *node1, AbstractAccess *node2, List<RefList<AbstractAccess> > & chain_list) { /// ... First, look for node1 at the end of a RefList bool found_node1 = false; for (Iterator<RefList<AbstractAccess> > iter = chain_list; iter.valid(); ++iter) { RefList<AbstractAccess> & list1 = iter.current(); int last_index = list1.entries() - 1; if (node1 == &(list1[last_index])) { /// ... Check whether node2 is at the beginning of a list found_node1 = true; bool found_node2 = false; for (Iterator<RefList<AbstractAccess> > iter2 = chain_list; iter2.valid(); ++iter2) { RefList<AbstractAccess> & list2 = iter2.current(); if (node2 == &(list2[0])) { /// ... Append list2 to list1 found_node2 = true; for (Iterator<AbstractAccess> iter3 = list2; iter3.valid(); ++iter3) { list1.ins_last(iter3.current()); } break; } } if (found_node2) break; /// ... Didn't find node2, so add node2 to RefList list1.ins_last(*node2); break; } } if (found_node1) return; /// ... If we didn't find node1, check this time for node2 at the beginning of a RefList bool part2_found_node2 = false; for (Iterator<RefList<AbstractAccess> > iter = chain_list; iter.valid(); ++iter) { RefList<AbstractAccess> & list1 = iter.current(); if (node2 == &(list1[0])) { /// ... Check whether node2 is at the end of a list part2_found_node2 = true; bool part2_found_node1 = false; for (Iterator<RefList<AbstractAccess> > iter2 = chain_list; iter2.valid(); ++iter2) { RefList<AbstractAccess> & list2 = iter2.current(); int last_index2 = list2.entries() - 1; if (node1 == &(list2[last_index2])) { /// ... Prepend list2 to list1 part2_found_node1 = true; for (Iterator<AbstractAccess> iter3 = list2; iter3.valid(); ++iter3) { list1.ins_first(iter3.current()); } break; } } if (part2_found_node1) break; /// ... Didn't find node1, so add node1 to RefList list1.ins_first(*node1); break; } } if (part2_found_node2) return; /// ... If found neither node1 nor node2 in the lists, then we must begin a new RefList, containing /// ... those two nodes. RefList<AbstractAccess> * newlist = new RefList<AbstractAccess>; newlist->ins_first(*node1); newlist->ins_last (*node2); chain_list.ins_first(newlist); return; } SimTypeOfChange ar_aggregate( SimEdge & edge, SimGraph & sg, List<AbstractAccess> & list ) { SimTypeOfChange change = SIM_NOCHANGE; AbstractAccess * desc_less; AbstractAccess * desc_grt; AbstractAccess * descr1 = edge.node_1(); AbstractAccess * descr2 = edge.node_2(); SimilarityType type = edge.type(); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "COMPARE: " << endl; arlog << "[" << edge.index1() << "]"; arlog << *descr1 << " and " << endl; arlog << "[" << edge.index2() << "]"; arlog << *descr2 << " (" << edge.type_name() << ") " << endl; } int dims1 = descr1->number_of_dimensions(); int dims2 = descr2->number_of_dimensions(); /// ... Take care of the _SEMI cases. Array<int> * stridematch=0; Array<bool> * spanmatch=0; bool must_cleanup=false; /// ... This represented the descriptor which has dimension(s) added (if any) int augmented_dim = -1; if ((type == SIM_DIM_EQUIV_SEMI) || (type == SIM_STRIDE_EQUIV_SEMI)) { if (dims1 < dims2) { /// ... Copy ARD1 AbstractAccess * new_aa = descr1->clone(); Array<int> * new_stridematch = new Array<int>; Array<bool> * new_spanmatch = new Array<bool>; (*new_stridematch).resize(dims2); (*new_spanmatch).resize(dims2); /// ... Get the match from ARD2 to ARD1 stridematch = sg.kernel(edge.index2(), edge.index1()).stridematch(); spanmatch = sg.kernel(edge.index2(), edge.index1()).spanmatch(); /// ... Add dimensions from ARD2 which were not matched, set spans to 0 int new_dim = dims1; /// ... add_dimension does ins_last for (int ii=0; ii<dims2; ++ii) { if ((*stridematch)[ii] == -1) { AccessDimension * dim =descr2->dimension(ii).clone(); dim->span(constant(0)); new_aa->add_dimension(dim); (*new_stridematch)[new_dim] = ii; (*new_spanmatch)[new_dim] = false; ++new_dim; } else { (*new_stridematch)[(*stridematch)[ii]] = ii; (*new_spanmatch)[(*stridematch)[ii]] = (*spanmatch)[ii]; } } stridematch = new_stridematch; spanmatch = new_spanmatch; /// ... silvius: this is a memory leak must_cleanup=true; descr1 = new_aa; dims1 = dims2; type = SIM_STRIDE_EQUIV; augmented_dim = 1; dims1 = dims2; } else { /// ... Copy ARD2 AbstractAccess * new_aa = descr2->clone(); Array<int> * new_stridematch = new Array<int>; Array<bool> * new_spanmatch = new Array<bool>; (*new_stridematch).resize(dims1); (*new_spanmatch).resize(dims1); stridematch = edge.edge()->stridematch(); spanmatch = edge.edge()->spanmatch(); for (int ii=0; ii<dims1; ++ii) { (*new_stridematch)[ii] = (*stridematch)[ii]; (*new_spanmatch)[ii] = (*spanmatch)[ii]; } /// ... Add dimensions from ARD1 which were not matched, set spans to 0 int new_dim = dims2; for (int ii=0; ii<dims1; ++ii) { if ((*stridematch)[ii] == -1) { AccessDimension * dim =descr1->dimension(ii).clone(); dim->span(constant(0)); new_aa->add_dimension(dim); (*new_stridematch)[ii] = new_dim; ++new_dim; (*new_spanmatch)[ii] = false; } } stridematch = new_stridematch; spanmatch = new_spanmatch; /// ... silvius: this is a memory leak must_cleanup=true; descr2 = new_aa; type = SIM_STRIDE_EQUIV; augmented_dim = 2; dims2 = dims1; } } else { stridematch = edge.edge()->stridematch(); spanmatch = edge.edge()->spanmatch(); } switch (type) { case SIM_EQUIV: change = SIM_EQUIVALENCE; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Equivalence: " << *descr1 << " and " << *descr2 << endl; } list.del(*(edge.node_2())); break; case SIM_EQUIV_SEMI: if (dims1 < dims2) { list.del(*(edge.node_1())); change = SIM_CONTIG_NODE2; } else { list.del(*(edge.node_2())); change = SIM_CONTIG_NODE1; } break; case SIM_NOT_SIMILAR: change = SIM_NOCHANGE; break; case SIM_STRIDE_EQUIV: /// ... Common point for Dimension-equivalent and Stride-equivalent descriptors case SIM_DIM_EQUIV: { /// ... First, determine the descriptor with the lesser offset /// ... If can't decide, can't go further for either type of relationship int smaller_offset = 0; RangeAccessor * range_acc = sg.range_acc( ); if ((descr1->start_guarded().op() == INTEGER_CONSTANT_OP) && (descr2->start_guarded().op() == INTEGER_CONSTANT_OP)) { int start1 = descr1->start_guarded().value(); int start2 = descr2->start_guarded().value(); if (start1 < start2) { desc_less = descr1; desc_grt = descr2; smaller_offset = 1; } else { desc_less = descr2; desc_grt = descr1; smaller_offset = 2; } } else { Relation rel = range_acc->compare(descr1->start_guarded(), descr2->start_guarded()); if (rel.is_less_than()) { /// ... start1 < start2 desc_less = descr1; desc_grt = descr2; smaller_offset = 1; } else if (rel.is_greater_equal()) { /// ... start2 <= start1 desc_less = descr2; desc_grt = descr1; smaller_offset = 2; } else { /// ... cannot decide change = SIM_NOCHANGE; break; } } if (type == SIM_STRIDE_EQUIV) { /// ... For Stride-equivalent descriptors, check for all-but-one matching /// ... and determine which dimension does not match. int count = 0; int nonmatch = -1; for (int i=0; i<dims1; ++i) { if ( (*spanmatch)[i] ) { ++count; } else { nonmatch = i; } } if (count < (dims1-1)) { change = SIM_NOCHANGE; } else if (count == (dims1-1)) { /// ... all spans but one match - try to aggregate if (smaller_offset == 1) { change = contiguous_aggregation(range_acc, desc_less, desc_grt, smaller_offset, nonmatch, (*stridematch)[nonmatch]); } else { change = contiguous_aggregation(range_acc, desc_less, desc_grt, smaller_offset, (*stridematch)[nonmatch], nonmatch); } if (change == SIM_CONTIG_NODE1) { if (augmented_dim == 2) { delete descr2; } list.del(*(edge.node_2())); if (augmented_dim == 1) { list.modify(*(edge.node_1()), descr1); sg.set_ptr(edge.index1(), *descr1); sg.set_unknown( edge, edge.index1()); } else { sg.redo_spanmatch( edge, edge.index1(), nonmatch ); } } else if (change == SIM_CONTIG_NODE2) { if (augmented_dim == 1) { delete descr1; } list.del(*(edge.node_1())); if (augmented_dim == 2) { list.modify(*(edge.node_2()), descr2); sg.set_ptr(edge.index2(), *descr2); sg.set_unknown( edge, edge.index2()); } else { sg.redo_spanmatch( edge, edge.index2(), (*stridematch)[nonmatch] ); } } } else { cout << "All spans match on SIM_STRIDE_EQUIV"; change = SIM_NOCHANGE; } break; } else { /// ... type == SIM_DIM_EQUIV /// ... For Dimension-equivalent descriptors, must try each matched set /// ... to see if any one meets the criterion. When one pair /// ... does, we stop. int dim1 = 0, dim2 = 0; int dims = dims1; Array<int> * stridematch = edge.edge()->stridematch(); for (dim1=0; dim1<dims; ++dim1) { dim2 = (*stridematch)[dim1]; if (smaller_offset == 1) { change = contiguous_aggregation(range_acc, desc_less, desc_grt, smaller_offset, dim1, dim2); } else { change = contiguous_aggregation(range_acc, desc_less, desc_grt, smaller_offset, dim2, dim1); } if (change != SIM_NOCHANGE) { break; } } if (change == SIM_CONTIG_NODE1) { list.del(*(edge.node_2())); sg.redo_spanmatch( edge, edge.index1(), dim1 ); break; } if (change == SIM_CONTIG_NODE2) { list.del(*(edge.node_1())); sg.redo_spanmatch( edge, edge.index2(), dim2 ); break; } change = SIM_NOCHANGE; break; } break; } default: p_abort("Similarity type was not one of the valid types"); } if (must_cleanup){ delete stridematch; delete spanmatch; } return change; } /// Test the contiguous-region conditions SimTypeOfChange contiguous_aggregation (RangeAccessor * range_acc, AbstractAccess * desc_less, AbstractAccess * desc_grt, int smaller_offset, int dim_less_index, int dim_grt_index ) { SimTypeOfChange change; AccessDimension & dim_less = (AccessDimension & ) desc_less->dimension(dim_less_index); AccessDimension & dim_grt = (AccessDimension & ) desc_grt->dimension(dim_grt_index); Expression * diff = simplify(sub(desc_grt->start_guarded().clone(), desc_less->start_guarded().clone())); Expression * dimsum = simplify(add(dim_less.stride_guarded().clone(), dim_less.span_guarded().clone())); if ((diff->op() == INTEGER_CONSTANT_OP) && (dimsum->op() == INTEGER_CONSTANT_OP) && (dim_grt.stride_guarded().op() == INTEGER_CONSTANT_OP) && (dim_grt.span_guarded().op() == INTEGER_CONSTANT_OP) && (dim_less.span_guarded().op() == INTEGER_CONSTANT_OP)) { int diff_i = diff->value(); int dimsum_i = dimsum->value(); int grt_stride_i = dim_grt.stride_guarded().value(); int grt_span_i = dim_grt.span_guarded().value(); int less_span_i = dim_less.span_guarded().value(); if (dimsum_i < diff_i) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << " NOT >=" << endl; } change = SIM_NOCHANGE; } else if (diff_i % grt_stride_i == 0) { /// ... We can aggregate the two descriptors if (_ar_logging && _ar_logging % 2 == 0) { arlog << " >=" << endl; } if (grt_span_i + diff_i > less_span_i) { Expression * new_span = simplify(add( dim_grt.span_guarded().clone(), diff->clone() )); dim_less.span( new_span ); /// ... Modify descriptor with smaller offset dim_less.singleton( dim_less.singleton() && dim_grt.singleton() ); desc_less->add_actual(0, 0); /// ... Remove the actual pointer, because now it represents >1 sites /// ... Calculating the overlap characteristic if (dimsum_i > diff_i) { desc_less->no_overlap(false); } /// ... Transfer overlap-check notations from dim_grt to dim_less Iterator<AccessDimension> iter = desc_grt->iter_dims(); for (int index=0; iter.valid(); ++iter,++index) { if (iter.current().check_overlap()) { desc_less->set_check_overlap(index,true); } } /// ... Calc_overlap where necessary if (! desc_less->is_imprecise()) { Iterator<AccessDimension> iter2 = desc_less->iter_dims(); for (int index=0; iter2.valid(); ++iter2,++index) { if (iter2.current().check_overlap()) { desc_less->calc_overlap(index); } } } } else { /// ... dim_grt is a subregion of dim_less, don't change span dim_less.singleton( dim_less.singleton() && dim_grt.singleton() ); } if (_ar_logging && _ar_logging % 2 == 0) { arlog << "RESULT: " << *desc_less << endl; } if ( smaller_offset == 1) { change = SIM_CONTIG_NODE1; } else { change = SIM_CONTIG_NODE2; } } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << " OK" << endl; arlog << dim_grt.stride_guarded() << " DOES NOT DIVIDE " << *diff << endl; } change = SIM_NOCHANGE; } } else { /// cerr<<"\n descr1 = "<<*desc_less; /// cerr<<"\n descr2 = "<<*desc_grt; Relation rel2 = range_acc->compare(*dimsum, *diff); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Contiguous Aggregation: " << *desc_less << "[" << dim_less_index << "] and " << *desc_grt << "[" << dim_grt_index << "]" << endl; arlog << *dimsum << " VS " << *diff ; } if (rel2.is_less_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << " NOT >=" << endl; } change = SIM_NOCHANGE; } else if (rel2.is_greater_equal()) { if (expr_divides(dim_grt.stride_guarded(),*diff) == AR_YES) { /// ... We can aggregate the two descriptors if (_ar_logging && _ar_logging % 2 == 0) { arlog << " >=" << endl; } Expression * sum = simplify(add(dim_grt.span_guarded().clone(), diff->clone())); Relation subreg = range_acc->compare(*sum, dim_less.span_guarded()); /// cerr<<"\n sum = "<<*sum; delete sum; /// ... silvius: /// ... maybe start2=start1+span1+stride Expression* sum1=add(desc_less->start_guarded().clone(), dim_less.span_guarded().clone()); sum1=add(sum1, dim_less.stride_guarded().clone()); sum1=simplify(sum1); bool can_do=false; if (*sum1==desc_grt->start_guarded()){ can_do=true; } delete sum1; if (subreg.is_greater_than() || can_do) { Expression * new_span = simplify(add( dim_grt.span_guarded().clone(), diff->clone() )); dim_less.span( new_span ); /// ... Modify descriptor with smaller offset dim_less.singleton( dim_less.singleton() && dim_grt.singleton() ); desc_less->add_actual(0, 0); /// ... Remove the actual pointer, because now it represents >1 sites /// ... Calculating the overlap characteristic if (rel2.is_equal()) { /// ... Does not change the overlap characteristic } else if (rel2.is_not_equal()) { desc_less->no_overlap(false); } else { desc_less->no_overlap(2); /// ... Say it will take a runtime test dim_less.check_overlap(true); } /// ... Transfer overlap-check notations from dim_grt to dim_less Iterator<AccessDimension> iter = desc_grt->iter_dims(); for (int index=0; iter.valid(); ++iter,++index) { if (iter.current().check_overlap()) { desc_less->set_check_overlap(index,true); } } /// ... Calc_overlap where necessary if (! desc_less->is_imprecise()) { Iterator<AccessDimension> iter2 = desc_less->iter_dims(); for (int index=0; iter2.valid(); ++iter2,++index) { if (iter2.current().check_overlap()) { desc_less->calc_overlap(index); } } } } else if (subreg.is_less_equal()) { /// ... dim_grt is a subregion of dim_less, don't change span dim_less.singleton( dim_less.singleton() && dim_grt.singleton() ); } else { /// ... cannot be sure, don't do anything change = SIM_NOCHANGE; delete diff; delete dimsum; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "RESULT: " << *desc_less << endl; } return change; } if (_ar_logging && _ar_logging % 2 == 0) { arlog << "RESULT: " << *desc_less << endl; } if ( smaller_offset == 1) { change = SIM_CONTIG_NODE1; } else { change = SIM_CONTIG_NODE2; } } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << " OK" << endl; arlog << dim_grt.stride_guarded() << " DOES NOT DIVIDE " << *diff << endl; } change = SIM_NOCHANGE; } } else { /// ... Don't know, no change if (_ar_logging && _ar_logging % 2 == 0) { arlog << " OK" << endl; arlog << *dimsum << " DOES NOT DIVIDE " << *diff << endl; } change = SIM_NOCHANGE; } } delete dimsum; delete diff; return change; } /// ar_intersect - /// Attempt to remove the overlapping portion from the descriptor in list1. /// list1[ard1] - list2[ard2] -> list1[ard1] /// /// list2[ard2] is not changed. /// /// If new descriptors are /// added to list1 as a result of this operation, they must be added at /// the end of the list, since we assume that an iteration involving the /// two lists is going on outside of this routine and we don't want to /// add or delete elements which would disturb that. /// /// The notion of conservatism used in this routine is that whenever /// we aren't totally sure of something, the list1 descriptor is left /// untouched. bool ar_intersect (List<AbstractAccess> & list1, int ard1, RefList<AbstractAccess> & discard1, List<AbstractAccess> & list2, int ard2, SimBiGraph & sbg, SimEdge & edge, AR_MEET meet_op, IPAStats & istats) { List<AbstractAccess> new_ard1; List<AbstractAccess> new_ard2; List<AbstractAccess> intersect; RangeAccessor * range_acc = sbg.range_acc( ); bool inter = intersect_ARDs(list1[ard1], list2[ard2], *range_acc, edge, UNDERESTIMATE, new_ard1, new_ard2, intersect, meet_op, istats); istats.ar_inter2.restart(); if (inter) { for (int i=0; i<new_ard1.entries(); ++i) { if (!ar_descriptor_member(list1, new_ard1[i])) { ar_append(list1, new_ard1.grab(i)); } } if (!discard1.member(list1[ard1])) discard1.ins_last(list1[ard1]); } istats.ar_inter2.stop(); return inter; } /// ar_intersect - /// Attempt to remove the overlapping portion from the descriptors in list1 and list2. /// Also, move the overlapping portion to a new list. /// list1[ard1] - list2[ard2] -> list1 /// list2[ard2] - list1[ard1] -> list2 /// list1[ard1] <intersect> list2[ard2] -> intersect /// /// If new descriptors are added to list1 or list2 as a result of this operation, /// they must be added at the end of the list, since we assume that an iteration /// involving the two lists is going on outside of this routine and we don't want /// to add or delete elements which would disturb that. bool ar_intersect (List<AbstractAccess> & list1, int ard1, RefList<AbstractAccess> & discard1, List<AbstractAccess> & list2, int ard2, RefList<AbstractAccess> & discard2, SimBiGraph & sbg, SimEdge & edge, List<AbstractAccess> & intersect, AR_CONSERVATIVE direction, AR_MEET meet_op, IPAStats & istats) { List<AbstractAccess> new_ard1; List<AbstractAccess> new_ard2; RangeAccessor * range_acc = sbg.range_acc( ); bool inter = intersect_ARDs(list1[ard1], list2[ard2], *range_acc, edge, direction, new_ard1, new_ard2, intersect, meet_op, istats); istats.ar_inter3.restart(); istats.ar_inter3_elems1.add(list1.entries()); istats.ar_inter3_elems2.add(list2.entries()); if (inter) { for (Mutator<AbstractAccess> iter = new_ard1; iter.valid(); ++iter) { if (!ar_descriptor_member(list1, iter.current())) { ar_append(list1, iter.grab()); } } if (!discard1.member(list1[ard1])) discard1.ins_last(list1[ard1]); for (Mutator<AbstractAccess> iter = new_ard2; iter.valid(); ++iter) { if (!ar_descriptor_member(list2, iter.current())) { ar_append(list2, iter.grab()); } } if (!discard2.member(list2[ard2])) discard2.ins_last(list2[ard2]); } istats.ar_inter3.stop(); return inter; } /// intersect_ARDs - /// Assume that ARD1 represents an "earlier" access, in the sense that /// it precedes the ARD2 access(es) in an execution-order traversal of the /// program. /// /// Intersect ARD1 with ARD2 and return the three parts: the part /// that intersects, and the part remaining in ARD1 and ARD2 after /// the intersecting part is removed. The new ARD1 is passed back in /// new_ard1 and the new ARD2 is passed back in new_ard2. /// /// This routine uses a "meet" operation specified as a parameter to /// handle the predicates which occur on the input ARDs. For straight-line /// code where logical implication can be proven, the meet operation should /// be AND (AR_AND). "Logical implication" means that the predicate on the /// later access can be shown to imply that the predicate on the earlier /// access was TRUE. This establishes an order between the accesses. In this /// case, the earlier access can be shown to actually occur prior to the /// later access. In this situation, predicates for the two descriptors /// should be ANDed together. /// /// For straightline code in which logical implication cannot be proven, /// the results of the intersection will be loaded into the ReadWrite /// summary set and the meet operation of "Not X and Y" (AR_NOTX_Y) will /// be used to produce the condition under which the dependence happens. /// /// So, for example, for code such as: /// /// do . . . /// if (P) then /// a(1:N) = /// endif /// if (Q) then /// . . . = a(1:N) /// endif /// end do /// /// if we can't prove that Q=>P, then there is a dependence /// /// For IF constructs, such as: /// /// if (P) then /// a(1:N) = /// else /// a(1:n) = /// endif /// /// the meet operation should be OR (AR_OR). Thus, we can say /// <WRITE> {P}:a(1:N) intersecting <WRITE> {~P}:a(1:N) equals <WRITE> {P || ~P}:a(1:N), /// which equals <WRITE> a(1:N). This reflects the reality that A(1:N) is written /// regardless of the value of P. /// /// new_ard1 and new_ard2 are filled with descriptors which are different /// from ard1 and ard2, respectively. If ard1 or ard2 are changed by this /// routine, or "disappear" (it is a subregion of the other, or ard1==ard2), /// then that will be signalled by the routine returning true. /// /// If either ard1 or ard2 is unchanged by this routine, the routine returns false /// and nothing is placed in new_ard1 or new_ard2, respectively. /// /// So, for example, if the intersection causes a span in ard1 to change, then /// the new version of the descriptor is written to new_ard1[0] and the routine /// returns true. /// The match_index in the SimEdge argument gives a matching from ard1 to ard2 /// (not from ard2 to ard1). The ard2 to ard1 matching can be inferred from the /// ard1 to ard2 matching. THE TWO DESCRIPTORS ARD1 AND ARD2 MUST BE CONSIDERED /// IN THE SAME ORDER AS THEY WERE USED IN CONSTRUCTING THE SIMEDGE. bool intersect_ARDs (AbstractAccess & ard1, AbstractAccess & ard2, RangeAccessor & range_acc, SimEdge & edge, AR_CONSERVATIVE direction, List<AbstractAccess> & new_ard1, List<AbstractAccess> & new_ard2, List<AbstractAccess> & intersect, AR_MEET meet_op, IPAStats & istats) { istats.inter_ARD.restart(); SimilarityType simtype = edge.type(); PredicateRepository & repos = ard1.pgm_summarized_to()->pred_repos(); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "intersect_ARDs:" << ard1 << " vs " << ard2 << endl; } /// ... silvius: try this first. Expression* s1=simplify(ard1.start_guarded().clone()); Expression* lo1=simplify(ard1.lastoffset()); Expression* s2=simplify(ard2.start_guarded().clone()); Expression* lo2=simplify(ard2.lastoffset()); Relation rel1 = range_acc.compare(*s1, *lo2); Relation rel2 = range_acc.compare(*s2, *lo1); delete s1; delete s2; delete lo1; delete lo2; if (rel1.is_greater_than() || rel2.is_greater_than()){ return false; } if (ard1.approximate()) { if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Adding approximate LMAD" << intersect << endl; } istats.inter_ARD.stop(); return true; } if (direction == UNDERESTIMATE) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Approximate LMAD - UNDERESTIMATE with empty intersection" << endl; } istats.inter_ARD.stop(); return false; } } if (ard2.approximate()) { if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Adding approximate LMAD" << intersect << endl; } istats.inter_ARD.stop(); return true; } if (direction == UNDERESTIMATE) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Approximate LMAD - UNDERESTIMATE with empty intersection" << endl; } istats.inter_ARD.stop(); return false; } } /// ... If either predicate is .FALSE., then there can be no intersection if (ard1.exec_predicate_false() || ard2.exec_predicate_false()) { istats.inter_ARD.stop(); return false; } if (simtype == SIM_NOT_SIMILAR) { /// ... Can't do much. Just check if mins against maxes. Expression *last1 = simplify(ard1.lastoffset()); Relation rel1 = range_acc.compare(*last1, ard2.start_guarded()); if (rel1.is_less_than()) { /// ... no intersection if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } istats.inter_ARD.stop(); delete last1; return false; } Expression *last2 = simplify(ard2.lastoffset()); Relation rel2 = range_acc.compare(*last2, ard1.start_guarded()); if (rel2.is_less_than()) { // no intersection if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } istats.inter_ARD.stop(); delete last2; return false; } /// ... assume intersection if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); /// ... Add nothing to new_ard1 or new_ard2 if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Just don't know - OVERESTIMATE by including both ARD1 & ARD2" << endl; } istats.inter_ARD.stop(); return true; } else { /// ... UNDERESTIMATE if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Just don't know - UNDERESTIMATE with empty intersection" << endl; } istats.inter_ARD.stop(); return false; } } AbstractAccess * aa1 = &ard1; AbstractAccess * aa2 = &ard2; int dims1 = aa1->number_of_dimensions(); int dims2 = aa2->number_of_dimensions(); bool newaa1 = false; bool newaa2 = false; /// ... Take care of the _SEMI cases. Array<int> * match_index; if ((simtype == SIM_STRIDE_EQUIV_SEMI) || (simtype == SIM_EQUIV_SEMI) || (simtype == SIM_DIM_EQUIV_SEMI)) { if (dims2 < dims1) { /// ... Make a new descriptor for aa2 with /// ... strides equivalent to those in aa1 and zero spans /// ... Just fill in the existing match_index, since it's big enough AbstractAccess * new_aa = aa2->clone(); match_index = edge.edge()->stridematch(); if (dims2 > 0) { /// ... Add match elements for new dimensions int new_dim = dims2; for (int ii=0; ii<dims1; ++ii) { if ((*match_index)[ii] == -1) { AccessDimension * dim =aa1->dimension(ii).clone(); dim->span(constant(0)); new_aa->add_dimension(dim); (*match_index)[ii] = new_dim; ++new_dim; } } } else { /// ... dims2 == 0 int new_dim = dims2; for (int ii=0; ii<dims1; ++ii) { AccessDimension * dim =aa1->dimension(ii).clone(); dim->span(constant(0)); new_aa->add_dimension(dim); (*match_index)[ii] = new_dim; ++new_dim; } } aa2 = new_aa; newaa2 = true; dims2 = dims1; simtype = SIM_STRIDE_EQUIV; } else { /// ... aa1 has fewer dimensions /// ... Make a new descriptor for aa1 with strides equivalent to those in aa2 and zero spans AbstractAccess * new_aa = aa1->clone(); Array<int> * new_match_index = new Array<int>; new_match_index->resize(dims2); if (dims1 > 0) { /// ... Invert match_index match_index = edge.edge()->stridematch(); Array<int> * inverted_match_index = invert_match(match_index, dims2); int new_dim = dims1; /// ... add_dimension does ins_last for (int ii=0; ii<dims2; ++ii) { if ((*inverted_match_index)[ii] == -1) { AccessDimension * dim =aa2->dimension(ii).clone(); dim->span(constant(0)); new_aa->add_dimension(dim); (*new_match_index)[new_dim] = ii; ++new_dim; } else { (*new_match_index)[(*inverted_match_index)[ii]] = ii; } } delete inverted_match_index; } else { /// ... dims1 == 0 int new_dim = dims1; /// ... add_dimension does ins_last for (int ii=0; ii<dims2; ++ii) { AccessDimension * dim =aa2->dimension(ii).clone(); dim->span(constant(0)); new_aa->add_dimension(dim); (*new_match_index)[new_dim] = ii; ++new_dim; } } match_index = new_match_index; aa1 = new_aa; newaa1 = true; dims1 = dims2; simtype = SIM_STRIDE_EQUIV; } } else { match_index = edge.edge()->stridematch(); } /// ... Now, we know that the strides are equivalent if ((dims1 == 0) && (dims2 == 0)) { if ((aa1->start_guarded().op() == INTEGER_CONSTANT_OP) && (aa2->start_guarded().op() == INTEGER_CONSTANT_OP)) { int start1 = aa1->start_guarded().value(); int start2 = aa2->start_guarded().value(); if (start1 == start2) { /// ... both represent same location /// ... Intersect descriptor AbstractAccess * interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } interARD->poss_reduct(aa1->poss_reduct() && aa2->poss_reduct()); if (aa1->reduct_op() == aa2->reduct_op()) { interARD->reduct_op(aa1->reduct_op()); } else { interARD->reduct_op(RED_OP_NONE); } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Intersection:" << *interARD << endl; } return true; } else { /// ... accesses don't overlap if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } } else { /// ... Do the above symbolically Expression & estart1 = aa1->start_guarded(); Expression & estart2 = aa2->start_guarded(); Expression * ediff = simplify(sub(estart1.clone(), estart2.clone())); if (ediff->op() == INTEGER_CONSTANT_OP) { if (ediff->value() == 0) { /// ... Intersect descriptor AbstractAccess * interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } interARD->poss_reduct(aa1->poss_reduct() && aa2->poss_reduct()); if (aa1->reduct_op() == aa2->reduct_op()) { interARD->reduct_op(aa1->reduct_op()); } else { interARD->reduct_op(RED_OP_NONE); } if (newaa1) delete aa1; if (newaa2) delete aa2; delete ediff; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Intersection:" << *interARD << endl; } return true; } } else { /// ... accesses don't overlap if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete ediff; istats.inter_ARD.stop(); return false; } } else { Expression *zero = constant(0); Relation relz = range_acc.compare(*ediff, *zero); delete zero; if (relz.is_not_equal()) { /// ... accesses don't overlap if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete ediff; istats.inter_ARD.stop(); return false; } if (_ar_logging && _ar_logging % 2 == 0) { arlog << endl << "Not enough info" << endl; } if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); /// ... Add nothing to new_ard1 or new_ard2 if (_ar_logging && _ar_logging % 2 == 0) { arlog << "OVERESTIMATE - ARD1 & ARD2 in intersection, discard both" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete ediff; istats.inter_ARD.stop(); return true; } else { /// ... UNDERESTIMATE if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Just don't know - UNDERESTIMATE with empty intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete ediff; istats.inter_ARD.stop(); return false; } } } } if ((dims1 == 1) && (dims2 == 1)) { AccessDimension & dim1 = (AccessDimension &) aa1->dimension(0); AccessDimension & dim2 = (AccessDimension &) aa2->dimension(0); Expression & estride = dim1.stride_guarded(); if ((aa1->start_guarded().op() == INTEGER_CONSTANT_OP) && (aa2->start_guarded().op() == INTEGER_CONSTANT_OP) && (dim1.stride_guarded().op() == INTEGER_CONSTANT_OP) && (dim1.span_guarded().op() == INTEGER_CONSTANT_OP) && (dim2.span_guarded().op() == INTEGER_CONSTANT_OP)) { int stride = dim1.stride_guarded().value(); p_assert(stride, "Stride of zero not allowed"); int start1 = aa1->start_guarded().value(); int start2 = aa2->start_guarded().value(); int span1 = dim1.span_guarded().value(); int span2 = dim2.span_guarded().value(); int lastoff1 = start1 + span1; int lastoff2 = start2 + span2; if ((start2 > lastoff1) || (start1 > lastoff2)) { /// ... accesses don't overlap if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } int diff = start1 - start2; if ( abs(diff) % stride == 0 ) { if (diff > 0) { /// ... aa1 starts to the right of aa2 /// ... We know (from above) that start1 <= lastoff2 if (lastoff1 > lastoff2) { /// ... New start1 is one stride after end of aa2 /// ... New start2 is old start2 AbstractAccess * ard1clone = ard1.clone(); ard1clone->start(constant(lastoff2+stride)); int newspan1 = lastoff1-(lastoff2+stride); if (newspan1 == 0) { ard1clone->del_dimension(0); } else { ard1clone->dimension(0).span(constant(newspan1)); } new_ard1.ins_last(ard1clone); AbstractAccess * ard2clone = ard2.clone(); int newspan2 = (start1-stride)-start2; if (newspan2 == 0) { ard2clone->del_dimension(0); } else { ard2clone->dimension(0).span(constant(newspan2)); } new_ard2.ins_last(ard2clone); /// ... Intersect descriptor AbstractAccess * interARD = ard1.clone(); int newspan3 = lastoff2-start1; if (newspan3 == 0) { interARD->del_dimension(0); } else { interARD->dimension(0).span(constant(newspan3)); } switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Intersection:" << *interARD << endl; } return true; } } else if (lastoff1 == lastoff2) { /// ... aa1 is a subregion of aa2. AbstractAccess * ard2clone = ard2.clone(); int newspan1 = (start1-stride)-start2; if (newspan1 == 0) { ard2clone->del_dimension(0); } else { ard2clone->dimension(0).span(constant(newspan1)); } new_ard2.ins_last(ard2clone); AbstractAccess * interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD1 is subregion of ARD2. Intersection is ARD1. Break ARD2" << endl; } return true; } } else { /// ... lastoff1 < lastoff2 /// ... aa1 is a subregion of aa2. Nothing in new_ard1. AbstractAccess * ard2_part1 = ard2.clone(); int newspan1 = (start1-stride)-start2; if (newspan1 == 0) { ard2_part1->del_dimension(0); } else { ard2_part1->dimension(0).span(constant(newspan1)); } new_ard2.ins_last(ard2_part1); AbstractAccess * ard2_part2 = ard2.clone(); ard2_part2->start(constant(lastoff1+stride)); int newspan2 = lastoff2-(lastoff1+stride); if (newspan2 == 0) { ard2_part2->del_dimension(0); } else { ard2_part2->dimension(0).span(constant(newspan2)); } new_ard2.ins_last(ard2_part2); AbstractAccess * interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD1 is subregion of ARD2. Intersection is ARD1. Break ARD2" << endl; } return true; } } } else if (diff == 0) { /// ... aa1 and aa2 start at the same point if (lastoff1 > lastoff2) { /// ... Just 1 piece of ard1 survives AbstractAccess * ard1clone = ard1.clone(); ard1clone->start(constant(lastoff2+stride)); int newspan1 = lastoff1-(lastoff2+stride); if (newspan1 == 0) { ard1clone->del_dimension(0); } else { ard1clone->dimension(0).span(constant(newspan1)); } new_ard1.ins_last(ard1clone); /// ... intersection is aa2. aa2 disappears. AbstractAccess *interARD = ard2.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD2 is subregion of ARD1. Intersection is ARD2. Reduce ARD1" << endl; } return true; } } else if (lastoff1 == lastoff2) { /// ... ARD1 == ARD2. Both disappear into the intersection. AbstractAccess *interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } interARD->poss_reduct(aa1->poss_reduct() && aa2->poss_reduct()); if (aa1->reduct_op() == aa2->reduct_op()) { interARD->reduct_op(aa1->reduct_op()); } else { interARD->reduct_op(RED_OP_NONE); } if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD2 == ARD1. Both disappear into intersection." << endl; } return true; } } else { /// ... lastoff1 < lastoff2 /// ... Just 1 piece of ard2 survives AbstractAccess * ard2clone = ard2.clone(); ard2clone->start(constant(lastoff1+stride)); int newspan1 = lastoff2-(lastoff1+stride); if (newspan1 == 0) { ard2clone->del_dimension(0); } else { ard2clone->dimension(0).span(constant(newspan1)); } new_ard2.ins_last(ard2clone); /// ... intersection is aa1. aa1 disappears. AbstractAccess *interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD1 is subregion of ARD2. Intersection is ARD1. Reduce ARD2" << endl; } return true; } } } else { /// ... diff < 0 -> aa2 starts to the right of aa1 if (lastoff1 > lastoff2) { /// ... aa2 is a subregion of aa1. Nothing in new_ard2. AbstractAccess * ard1_part1 = ard1.clone(); int newspan1 = (start2-stride)-start1; if (newspan1 == 0) { ard1_part1->del_dimension(0); } else { ard1_part1->dimension(0).span(constant(newspan1)); } new_ard1.ins_last(ard1_part1); AbstractAccess * ard1_part2 = ard1.clone(); ard1_part2->start(constant(lastoff2+stride)); int newspan2 = lastoff1-(lastoff2+stride); if (newspan2 == 0) { ard1_part2->del_dimension(0); } else { ard1_part2->dimension(0).span(constant(newspan2)); } new_ard1.ins_last(ard1_part2); AbstractAccess * interARD = ard2.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD2 is subregion of ARD1. Intersection is ARD2. Break ARD1" << endl; } return true; } } else if (lastoff1 == lastoff2) { /// ... aa2 is a subregion of aa1. Nothing in new_ard2. AbstractAccess * ard1_part1 = ard1.clone(); int newspan1 = (start2-stride)-start1; if (newspan1 == 0) { ard1_part1->del_dimension(0); } else { ard1_part1->dimension(0).span(constant(newspan1)); } new_ard1.ins_last(ard1_part1); AbstractAccess * interARD = ard2.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD2 is subregion of ARD1. Intersection is ARD2. Break ARD1" << endl; } return true; } } else { /// ... New start2 is one stride after end of aa1 /// ... New start1 is old start1 AbstractAccess * ard1clone = ard1.clone(); int newspan1 = (start2-stride)-start1; if (newspan1 == 0) { ard1clone->del_dimension(0); } else { ard1clone->dimension(0).span(constant(newspan1)); } new_ard1.ins_last(ard1clone); AbstractAccess * ard2clone = ard2.clone(); ard2clone->start(constant(lastoff1+stride)); int newspan2 = lastoff2-(lastoff1+stride); if (newspan2 == 0) { ard2clone->del_dimension(0); } else { ard2clone->dimension(0).span(constant(newspan2)); } new_ard2.ins_last(ard2clone); /// ... Intersect descriptor AbstractAccess * interARD = ard2.clone(); int newspan3 = lastoff1-start2; if (newspan3 == 0) { interARD->del_dimension(0); } else { interARD->dimension(0).span(constant(newspan3)); } switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Intersection:" << *interARD << endl; } return true; } } } } else { /// ... Points don't overlap if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } } else { /// ... Do the same as above, only symbolically Expression & estart1 = aa1->start_guarded(); Expression & estart2 = aa2->start_guarded(); Expression & espan1 = dim1.span_guarded(); Expression & espan2 = dim2.span_guarded(); Expression * elastoff1 = simplify(add(estart1.clone(), espan1.clone())); Expression * elastoff2 = simplify(add(estart2.clone(), espan2.clone())); Relation relcheck1 = range_acc.compare(estart1, *elastoff2); Relation relcheck2 = range_acc.compare(estart2, *elastoff1); if (relcheck2.is_greater_than() || relcheck1.is_greater_than()) { /// ... accesses don't overlap if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; istats.inter_ARD.stop(); return false; } Expression * ediff = simplify(sub(estart1.clone(), estart2.clone())); Expression * zero = constant(0); bool evenly_divides; /// ... If the two dimensions involved come from singleton indexes, /// ... and we can determine the size of the declared bound of the /// ... variable, then we can test whether the difference between /// ... the base offsets is divisible by the size of the declared /// ... bound. If it is, then there is no overlap. // if (dim1.singleton() && dim2.singleton() && // dim[0].upper_exists()) { // upper = dim[0].upper_guarded().clone(); /// // if (!dim[0].lower_exists()) { // lower = constant(1); // } else { // lower = dim[0].lower_guarded().clone(); // } // Expression * dimsize = simplify(add(sub(upper, lower), constant(1))); // if (divides_diff(*dimsize, ediff, ard1, ard2, OVERESTIMATE)) { /// // if (_ar_logging && _ar_logging % 2 == 0) { // arlog << "No intersection" << endl; // } // if (newaa1) delete aa1; // if (newaa2) delete aa2; // delete dimsize; // delete ediff; // delete zero; // delete elastoff1; // delete elastoff2; // istats.inter_ARD.stop(); // return false; // } // delete dimsize; // } /// ... Check whether the stride divides the diff, and how certain we are about that if ((estride.op() == INTEGER_CONSTANT_OP) && (ediff->op() == INTEGER_CONSTANT_OP)) { if (ediff->value() % estride.value() == 0) { evenly_divides = true; } else { evenly_divides = false; } } else { if (divides_diff(estride, ediff, ard1, ard2, OVERESTIMATE)) { evenly_divides = true; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete ediff; delete zero; delete elastoff1; delete elastoff2; istats.inter_ARD.stop(); return false; } } /// ... If we weren't sure about the evenly_divides, we would have returned before this. if (evenly_divides) { Relation reldiff = range_acc.compare(*ediff,*zero); delete zero; if (reldiff.is_greater_than()) { /// ... aa1 starts to the right of aa2 Relation rel_over2 = range_acc.compare(*elastoff1, *elastoff2); /// ... We know (from above) that start1 <= lastoff2 if (rel_over2.is_greater_than()) { /// ... New start1 is one stride after end of aa2 /// ... New start2 is old start2 AbstractAccess * ard1clone = ard1.clone(); ard1clone->start(simplify(add(elastoff2->clone(),estride.clone()))); Expression * newspan1 = simplify(sub(elastoff1->clone(), add(elastoff2->clone(),estride.clone()))); if (is_integer_zero(*newspan1)) { ard1clone->del_dimension(0); } else { ard1clone->dimension(0).span(newspan1); } new_ard1.ins_last(ard1clone); AbstractAccess * ard2clone = ard2.clone(); Expression * newspan2 = simplify(sub(sub(estart1.clone(),estride.clone()), estart2.clone())); if (is_integer_zero(*newspan2)) { ard2clone->del_dimension(0); } else { ard2clone->dimension(0).span(newspan2); } new_ard2.ins_last(ard2clone); /// ... Intersect descriptor AbstractAccess * interARD = ard1.clone(); Expression * newspan3 = simplify(sub(elastoff2->clone(),estart1.clone())); if (is_integer_zero(*newspan3)) { interARD->del_dimension(0); } else { interARD->dimension(0).span(newspan3); } switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Intersection:" << *interARD << endl; } return true; } } else if (rel_over2.is_equal()) { /// ... aa1 is a subregion of aa2. aa1 disappears. AbstractAccess * ard2clone = ard2.clone(); Expression * newspan1 = simplify(sub(sub(estart1.clone(),estride.clone()), estart2.clone())); if (is_integer_zero(*newspan1)) { ard2clone->del_dimension(0); } else { ard2clone->dimension(0).span(newspan1); } new_ard2.ins_last(ard2clone); AbstractAccess * interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD1 is subregion of ARD2. Intersection is ARD1. Break ARD2" << endl; } return true; } } else if (rel_over2.is_less_than()) { /// ... lastoff1 < lastoff2 /// ... aa1 is a subregion of aa2. Nothing in new_ard1. AbstractAccess * ard2_part1 = ard2.clone(); Expression * newspan1 = simplify(sub(sub(estart1.clone(),estride.clone()), estart2.clone())); if (is_integer_zero(*newspan1)) { ard2_part1->del_dimension(0); } else { ard2_part1->dimension(0).span(newspan1); } new_ard2.ins_last(ard2_part1); AbstractAccess * ard2_part2 = ard2.clone(); ard2_part2->start(add(elastoff1->clone(),estride.clone())); Expression * newspan2 = simplify(sub(elastoff2->clone(), add(elastoff1->clone(),estride.clone()))); if (is_integer_zero(*newspan2)) { ard2_part2->del_dimension(0); } else { ard2_part2->dimension(0).span(newspan2); } new_ard2.ins_last(ard2_part2); AbstractAccess * interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD1 is subregion of ARD2. Intersection is ARD1. Break ARD2" << endl; } return true; } } else { /// ... Just don't know - use the conservative direction if (_ar_logging && _ar_logging % 2 == 0) { arlog << endl << "Not enough info" << endl; } if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); /// ... Add nothing to new_ard1 or new_ard2 if (_ar_logging && _ar_logging % 2 == 0) { arlog << "OVERESTIMATE - ARD1 & ARD2 in intersection, discard both" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; delete ediff; istats.inter_ARD.stop(); return true; } else { /// ... UNDERESTIMATE if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Just don't know - UNDERESTIMATE with empty intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; delete ediff; istats.inter_ARD.stop(); return false; } } } else if (reldiff.is_equal()) { /// ... aa1 and aa2 start at the same point Relation rel_over2 = range_acc.compare(*elastoff1, *elastoff2); if (rel_over2.is_greater_than()) { /// ... lastoff1 > lastoff2 /// ... Just 1 piece of ard1 survives AbstractAccess * ard1clone = ard1.clone(); ard1clone->start(add(elastoff2->clone(),estride.clone())); Expression * newspan1 = simplify(sub(elastoff1->clone(),add(elastoff2->clone(),estride.clone()))); if (is_integer_zero(*newspan1)) { ard1clone->del_dimension(0); } else { ard1clone->dimension(0).span(newspan1); } new_ard1.ins_last(ard1clone); /// ... intersection is aa2. aa2 disappears. AbstractAccess *interARD = ard2.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (interARD->exec_predicate_false()) { istats.inter_ARD.stop(); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD2 is subregion of ARD1. Intersection is ARD2. Reduce ARD1" << endl; } return true; } } else if (rel_over2.is_equal()) { /// ... lastoff1 == lastoff2 /// ... ARD1 == ARD2. Both disappear into the intersection. AbstractAccess *interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } interARD->poss_reduct(aa1->poss_reduct() && aa2->poss_reduct()); if (aa1->reduct_op() == aa2->reduct_op()) { interARD->reduct_op(aa1->reduct_op()); } else { interARD->reduct_op(RED_OP_NONE); } if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD2 == ARD1. Both disappear into intersection." << endl; } return true; } else if (rel_over2.is_less_than()) { /// ... lastoff1 < lastoff2 /// ... Just 1 piece of ard2 survives AbstractAccess * ard2clone = ard2.clone(); ard2clone->start(add(elastoff1->clone(),estride.clone())); Expression * newspan1 = simplify(sub(elastoff2->clone(), add(elastoff1->clone(),estride.clone()))); if (is_integer_zero(*newspan1)) { ard2clone->del_dimension(0); } else { ard2clone->dimension(0).span(newspan1); } new_ard2.ins_last(ard2clone); /// ... intersection is aa1. aa1 disappears. AbstractAccess *interARD = ard1.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD1 is subregion of ARD2. Intersection is ARD1. Reduce ARD2" << endl; } return true; } } else { /// ... Not enough information, use conservative direction if (_ar_logging && _ar_logging % 2 == 0) { arlog << endl << "Not enough info" << endl; } if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); /// ... Add nothing to new_ard1 or new_ard2 if (_ar_logging && _ar_logging % 2 == 0) { arlog << "OVERESTIMATE - ARD1 & ARD2 in intersection, discard both" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; delete ediff; istats.inter_ARD.stop(); return true; } else { /// ... UNDERESTIMATE if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Just don't know - UNDERESTIMATE with empty intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; delete ediff; istats.inter_ARD.stop(); return false; } } } else if (reldiff.is_less_than()) { /// ... aa1 starts to the left of aa2 Relation rel_over2 = range_acc.compare(*elastoff1, *elastoff2); if (rel_over2.is_greater_than()) { /// ... lastoff1 > lastoff2 /// ... aa2 is a subregion of aa1. Nothing in new_ard2. AbstractAccess * ard1_part1 = ard1.clone(); Expression * newspan1 = simplify(sub(sub(estart2.clone(),estride.clone()),estart1.clone())); if (is_integer_zero(*newspan1)) { ard1_part1->del_dimension(0); } else { ard1_part1->dimension(0).span(newspan1); } new_ard1.ins_last(ard1_part1); AbstractAccess * ard1_part2 = ard1.clone(); ard1_part2->start(add(elastoff2->clone(),estride.clone())); Expression * newspan2 = simplify(sub(elastoff1->clone(),add(elastoff2->clone(),estride.clone()))); if (is_integer_zero(*newspan2)) { ard1_part2->del_dimension(0); } else { ard1_part2->dimension(0).span(newspan2); } new_ard1.ins_last(ard1_part2); AbstractAccess * interARD = ard2.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD2 is subregion of ARD1. Intersection is ARD2. Break ARD1" << endl; } return true; } } else if (rel_over2.is_equal()) { /// ... lastoff1 == lastoff2 /// ... aa2 is a subregion of aa1. Nothing in new_ard2. AbstractAccess * ard1_part1 = ard1.clone(); Expression * newspan1 = simplify(sub(sub(estart2.clone(),estride.clone()),estart1.clone())); if (is_integer_zero(*newspan1)) { ard1_part1->del_dimension(0); } else { ard1_part1->dimension(0).span(newspan1); } new_ard1.ins_last(ard1_part1); AbstractAccess * interARD = ard2.clone(); switch (meet_op) { case AR_X: interARD->exec_predicate(ard1.exec_predicate()); break; case AR_Y: interARD->exec_predicate(ard2.exec_predicate()); break; case AR_AND: interARD->exec_predicate(repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_OR: interARD->exec_predicate(repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_NOTX_Y: interARD->exec_predicate(repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; case AR_X_NOTY: interARD->exec_predicate(repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate())); break; default: p_abort("Bad value for meet operator"); } /// ... This can't be propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging %2 == 0) { arlog << "No intersect" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (_ar_logging && _ar_logging % 2 == 0) { arlog << "ARD2 is subregion of ARD1. Intersection is ARD2. Break ARD1" << endl; } return true; } } else if (rel_over2.is_less_than()) { /// ... New start2 is one stride after end of aa1 /// ... New start1 is old start1 AbstractAccess * ard1clone = ard1.clone(); Expression * newspan1 = simplify(sub(sub(estart2.clone(),estride.clone()),estart1.clone())); if (is_integer_zero(*newspan1)) { ard1clone->del_dimension(0); } else { ard1clone->dimension(0).span(newspan1); } AbstractAccess * ard2clone = ard2.clone(); ard2clone->start(simplify(add(elastoff1->clone(),estride.clone()))); Expression * newspan2 = simplify(sub(elastoff2->clone(), add(elastoff1->clone(),estride.clone()))); if (is_integer_zero(*newspan2)) { ard2clone->del_dimension(0); } else { ard2clone->dimension(0).span(newspan2); } /// ... Intersect descriptor AbstractAccess * interARD = ard2.clone(); Expression * newspan3 = simplify(sub(elastoff1->clone(),estart2.clone())); if (is_integer_zero(*newspan3)) { interARD->del_dimension(0); } else { interARD->dimension(0).span(newspan3); } /// ... Do we know the relationship between lastoff1 and start2? Relation rel_off1_st2 = range_acc.compare(*elastoff1, estart2); if (rel_off1_st2.is_greater_equal()) { /// ... OK, there definitely is an intersection } else { /// ... We just don't know, so add a predicate to each descriptor /// ... If there is an intersection: Expression * corr = simplify(gt(elastoff1->clone(),sub(estart2.clone(),constant(1)))); PredicateRepository & repos = ard1.pgm_summarized_to()->pred_repos(); int repindx = repos.ins(corr); ard1clone->exec_predicate(repos.and_pred(ard1clone->exec_predicate(), repindx)); ard2clone->exec_predicate(repos.and_pred(ard2clone->exec_predicate(), repindx)); interARD->exec_predicate(repos.and_pred(interARD->exec_predicate(), repindx)); if (!(interARD->exec_predicate_false())) { /// ... If there is not an intersection: Expression * corr2 = simplify(lt(elastoff1->clone(),estart2.clone())); repindx = repos.ins(corr2); AbstractAccess * ard1orig = ard1.clone(); ard1orig->exec_predicate(repos.and_pred(ard1orig->exec_predicate(), repindx)); if (!(ard1orig->exec_predicate_false())) { new_ard1.ins_last(ard1orig); } AbstractAccess * ard2orig = ard2.clone(); ard2orig->exec_predicate(repos.and_pred(ard2orig->exec_predicate(), repindx)); if (!(ard2orig->exec_predicate_false())) { new_ard2.ins_last(ard2orig); } } } if (!(ard1clone->exec_predicate_false())) { new_ard1.ins_last(ard1clone); } if (!(ard2clone->exec_predicate_false())) { new_ard2.ins_last(ard2clone); } if ((!interARD->exec_predicate_false())) { switch (meet_op) { case AR_X: interARD->exec_predicate(repos.and_pred(interARD->exec_predicate(), ard1.exec_predicate())); break; case AR_Y: interARD->exec_predicate(repos.and_pred(interARD->exec_predicate(), ard2.exec_predicate())); break; case AR_AND: interARD->exec_predicate(repos.and_pred(interARD->exec_predicate(), repos.and_pred(ard1.exec_predicate(), ard2.exec_predicate()))); break; case AR_OR: interARD->exec_predicate(repos.and_pred(interARD->exec_predicate(), repos.or_pred(ard1.exec_predicate(), ard2.exec_predicate()))); break; case AR_NOTX_Y: interARD->exec_predicate(repos.and_pred(interARD->exec_predicate(), repos.notx_and_y_pred(ard1.exec_predicate(), ard2.exec_predicate()))); break; case AR_X_NOTY: interARD->exec_predicate(repos.and_pred(interARD->exec_predicate(), repos.x_and_noty_pred(ard1.exec_predicate(), ard2.exec_predicate()))); break; default: p_abort("Bad value for meet operator"); } } /// ... This can't propagate the reduction characteristic because /// ... the two ARDs aren't identical interARD->poss_reduct(false); interARD->reduct_op(RED_OP_NONE); if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); intersect.ins_last(interARD); if (interARD->exec_predicate_false()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } return false; } else { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Intersection:" << *interARD << endl; } return true; } } else { /// ... Just don't know, use conservative direction if (_ar_logging && _ar_logging % 2 == 0) { arlog << endl << "Not enough info" << endl; } if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); /// ... Add nothing to new_ard1 or new_ard2 if (_ar_logging && _ar_logging % 2 == 0) { arlog << "OVERESTIMATE - ARD1 & ARD2 in intersection, discard both" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; delete elastoff1; delete elastoff2; delete ediff; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return true; } else { /// ... UNDERESTIMATE if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Just don't know - UNDERESTIMATE with empty intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; delete ediff; istats.inter_ARD.stop(); return false; } } } else { /// ... We just don't know if (_ar_logging && _ar_logging % 2 == 0) { arlog << endl << "Not enough info" << endl; } if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); /// ... Add nothing to new_ard1 or new_ard2 if (_ar_logging && _ar_logging % 2 == 0) { arlog << "OVERESTIMATE - ARD1 & ARD2 in intersection, discard both" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; delete ediff; istats.inter_ARD.stop(); return true; } else { /// ... UNDERESTIMATE if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Just don't know - UNDERESTIMATE with empty intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; delete ediff; istats.inter_ARD.stop(); return false; } } } else { /// ... Points don't overlap if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No overlap" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } delete elastoff1; delete elastoff2; delete ediff; istats.inter_ARD.stop(); return false; } } } if ((dims1 == 2) && (dims2 == 2)) { AccessDimension & dim1_1 = (AccessDimension &) aa1->dimension(0); AccessDimension & dim1_2 = (AccessDimension &) aa1->dimension(1); AccessDimension & dim2_1 = (AccessDimension &) aa2->dimension(0); AccessDimension & dim2_2 = (AccessDimension &) aa2->dimension(1); Expression * ediff = simplify(sub(aa1->start_guarded().clone(), aa2->start_guarded().clone())); if ((ediff->op() == INTEGER_CONSTANT_OP) && (dim1_1.stride_guarded().op() == INTEGER_CONSTANT_OP) && (dim1_2.stride_guarded().op() == INTEGER_CONSTANT_OP) && (dim2_1.stride_guarded().op() == INTEGER_CONSTANT_OP) && (dim2_2.stride_guarded().op() == INTEGER_CONSTANT_OP) && (dim1_1.span_guarded().op() == INTEGER_CONSTANT_OP) && (dim1_2.span_guarded().op() == INTEGER_CONSTANT_OP) && (dim2_1.span_guarded().op() == INTEGER_CONSTANT_OP) && (dim2_2.span_guarded().op() == INTEGER_CONSTANT_OP)) { int diff = ediff->value(); int stride1_1 = dim1_1.stride_guarded().value(); int stride1_2 = dim1_2.stride_guarded().value(); int stride2_1 = dim2_1.stride_guarded().value(); int stride2_2 = dim2_2.stride_guarded().value(); int span1_1 = dim1_1.span_guarded().value(); int span1_2 = dim1_2.span_guarded().value(); int span2_1 = dim2_1.span_guarded().value(); int span2_2 = dim2_2.span_guarded().value(); if (diff > 0) { if (span2_1 + span2_2 < diff) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } } else { /// ... diff < 0 if (span1_1 + span1_2 < -diff) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } } int stride_left_inner, stride_left_outer; int stride_right_inner, stride_right_outer; int span_left_inner, span_left_outer; int span_right_inner, span_right_outer; if (diff < 0) { /// ... aa1 is to the left diff = -diff; if (stride1_1 < stride1_2) { stride_left_inner = stride1_1; stride_left_outer = stride1_2; span_left_inner = span1_1; span_left_outer = span1_2; if (stride2_1 < stride2_2) { stride_right_inner = stride2_1; stride_right_outer = stride2_2; span_right_inner = span2_1; span_right_outer = span2_2; } else { stride_right_inner = stride2_2; stride_right_outer = stride2_1; span_right_inner = span2_2; span_right_outer = span2_1; } } else { stride_left_inner = stride1_2; stride_left_outer = stride1_1; span_left_inner = span1_2; span_left_outer = span1_1; if (stride2_1 < stride2_2) { stride_right_inner = stride2_1; stride_right_outer = stride2_2; span_right_inner = span2_1; span_right_outer = span2_2; } else { stride_right_inner = stride2_2; stride_right_outer = stride2_1; span_right_inner = span2_2; span_right_outer = span2_1; } } } else { /// ... aa1 is to the right if (stride2_1 < stride2_2) { stride_left_inner = stride2_1; stride_left_outer = stride2_2; span_left_inner = span2_1; span_left_outer = span2_2; if (stride1_1 < stride1_2) { stride_right_inner = stride1_1; stride_right_outer = stride1_2; span_right_inner = span1_1; span_right_outer = span1_2; } else { stride_right_inner = stride1_2; stride_right_outer = stride1_1; span_right_inner = span1_2; span_right_outer = span1_1; } } else { stride_left_inner = stride2_2; stride_left_outer = stride2_1; span_left_inner = span2_2; span_left_outer = span2_1; if (stride1_1 < stride1_2) { stride_right_inner = stride1_1; stride_right_outer = stride1_2; span_right_inner = span1_1; span_right_outer = span1_2; } else { stride_right_inner = stride1_2; stride_right_outer = stride1_1; span_right_inner = span1_2; span_right_outer = span1_1; } } } /// ... Now do range test type check diff = diff % stride_left_outer; if ((diff > span_left_inner) && ((diff + span_right_inner) < stride_left_outer)) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } /// ... Now do GCD test type check if ((diff % stride_left_inner != 0) && ((diff + span_right_inner) < stride_left_outer)) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } } else { /// ... Do the above symbolically List<Expression> factors; Expression * new_expr = sym_factors(dim2_1.span_guarded(), factors); Expression * no_empty_LMAD; if (new_expr) { no_empty_LMAD = ge(new_expr, constant(0)); } else { no_empty_LMAD = ge(dim2_1.span_guarded().clone(), constant(0)); } Statement * s = aa2->actual_stmt(); if (s == 0) { s = aa2->summarized_to(); } if (s) { // StmtRanges & ranges = ((AIRangeDict & )(aa2->pgm_summarized_to()->range_dict_guarded()))._s_ranges(s->tag()); // ranges.extract_ranges(*no_empty_LMAD); } delete no_empty_LMAD; bool diff_less = false; Expression * zero = constant(0); Relation reldiff = range_acc.compare(*ediff, *zero); delete zero; if (reldiff.is_greater_than()) { Expression * sumspans2 = add(dim2_1.span_guarded().clone(), dim2_2.span_guarded().clone()); Relation relspan2 = range_acc.compare(*sumspans2, *ediff); delete sumspans2; if (relspan2.is_less_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } delete ediff; if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } /// ... Above, we compared dim2_2.span + dim2_1.span vs ediff. /// ... Having gotten to this point, that didn't work. There /// ... may just be some unknown variable muddying the waters. /// ... As an alternative, if we know that dim2_1 is "no overlap", /// ... and the descriptors are precisely-sorted, then we can /// ... try again, testing dim2_2.span + dim2_2.stride vs ediff /// ... (since dim2_1.span must be < dim2_2.stride, due to "no overlap"). if (!(aa2->is_imprecise()) && !(dim2_1.check_overlap())) { Expression * one = constant(1); sumspans2 = sub(add(dim2_2.span_guarded().clone(), dim2_2.stride_guarded().clone()), one); Relation relspan2 = range_acc.compare(*sumspans2, *ediff); delete sumspans2; if (relspan2.is_less_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } delete ediff; if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } } } else if (reldiff.is_less_equal()) { /// ... diff < 0 diff_less = true; Expression * sumspans1 = add(dim1_1.span_guarded().clone(), dim1_2.span_guarded().clone()); Expression * negdiff = sub(constant(0),ediff->clone()); Relation relspan1 = range_acc.compare(*sumspans1, *negdiff); delete sumspans1; if (relspan1.is_less_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } delete negdiff; delete ediff; if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } /// ... Above, we compared dim1_2.span + dim1_1.span vs ediff. /// ... Having gotten to this point, that didn't work. There /// ... may just be some unknown variable muddying the waters. /// ... As an alternative, if we know that dim1_1 is "no overlap", /// ... and the descriptors are precisely-sorted, then we can /// ... try again, testing dim1_2.span + dim1_2.stride vs ediff /// ... (since dim1_1.span must be < dim1_2.stride, due to "no overlap"). if (!(aa1->is_imprecise()) && !(dim1_1.check_overlap())) { Expression * one = constant(1); sumspans1 = sub(add(dim1_2.span_guarded().clone(), dim1_2.stride_guarded().clone()), one); Relation relspan1 = range_acc.compare(*sumspans1, *negdiff); delete sumspans1; if (relspan1.is_less_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } delete negdiff; delete ediff; if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } } delete negdiff; } Expression * estride_left_inner = 0; Expression * estride_left_outer = 0; Expression * estride_right_inner = 0; Expression * estride_right_outer = 0; Expression * espan_left_inner = 0; Expression * espan_left_outer = 0; Expression * espan_right_inner = 0; Expression * espan_right_outer = 0; if (diff_less) { /// ... aa1 is to the left ediff = sub(constant(0),ediff); Relation rel_stride1 = range_acc.compare(dim1_1.stride_guarded(), dim1_2.stride_guarded()); if (rel_stride1.is_less_than()) { estride_left_inner = dim1_1.stride_guarded().clone(); estride_left_outer = dim1_2.stride_guarded().clone(); espan_left_inner = dim1_1.span_guarded().clone(); espan_left_outer = dim1_2.span_guarded().clone(); Relation rel_stride2 = range_acc.compare(dim2_1.stride_guarded(), dim2_2.stride_guarded()); if (rel_stride2.is_less_than()) { estride_right_inner = dim2_1.stride_guarded().clone(); estride_right_outer = dim2_2.stride_guarded().clone(); espan_right_inner = dim2_1.span_guarded().clone(); espan_right_outer = dim2_2.span_guarded().clone(); } else if (rel_stride2.is_greater_than()) { estride_right_inner = dim2_2.stride_guarded().clone(); estride_right_outer = dim2_1.stride_guarded().clone(); espan_right_inner = dim2_2.span_guarded().clone(); espan_right_outer = dim2_1.span_guarded().clone(); } } else if (rel_stride1.is_greater_than()) { estride_left_inner = dim1_2.stride_guarded().clone(); estride_left_outer = dim1_1.stride_guarded().clone(); espan_left_inner = dim1_2.span_guarded().clone(); espan_left_outer = dim1_1.span_guarded().clone(); Relation rel_stride2 = range_acc.compare(dim2_1.stride_guarded(), dim2_2.stride_guarded()); if (rel_stride2.is_less_than()) { estride_right_inner = dim2_1.stride_guarded().clone(); estride_right_outer = dim2_2.stride_guarded().clone(); espan_right_inner = dim2_1.span_guarded().clone(); espan_right_outer = dim2_2.span_guarded().clone(); } else if ( rel_stride2.is_greater_than()) { estride_right_inner = dim2_2.stride_guarded().clone(); estride_right_outer = dim2_1.stride_guarded().clone(); espan_right_inner = dim2_2.span_guarded().clone(); espan_right_outer = dim2_1.span_guarded().clone(); } } } else { /// ... aa1 is to the right Relation rel_stride2 = range_acc.compare(dim2_1.stride_guarded(), dim2_2.stride_guarded()); if (rel_stride2.is_less_than()) { estride_left_inner = dim2_1.stride_guarded().clone(); estride_left_outer = dim2_2.stride_guarded().clone(); espan_left_inner = dim2_1.span_guarded().clone(); espan_left_outer = dim2_2.span_guarded().clone(); Relation rel_stride1 = range_acc.compare(dim1_1.span_guarded(), dim2_2.span_guarded()); if (rel_stride1.is_less_than()) { estride_right_inner = dim1_1.stride_guarded().clone(); estride_right_outer = dim1_2.stride_guarded().clone(); espan_right_inner = dim1_1.span_guarded().clone(); espan_right_outer = dim1_2.span_guarded().clone(); } else if (rel_stride2.is_greater_than()) { estride_right_inner = dim1_2.stride_guarded().clone(); estride_right_outer = dim1_1.stride_guarded().clone(); espan_right_inner = dim1_2.span_guarded().clone(); espan_right_outer = dim1_1.span_guarded().clone(); } } else if (rel_stride2.is_greater_than()) { estride_left_inner = dim2_2.stride_guarded().clone(); estride_left_outer = dim2_1.stride_guarded().clone(); espan_left_inner = dim2_2.span_guarded().clone(); espan_left_outer = dim2_1.span_guarded().clone(); Relation rel_stride1 = range_acc.compare(dim1_1.stride_guarded(), dim1_2.stride_guarded()); if (rel_stride1.is_less_than()) { estride_right_inner = dim1_1.stride_guarded().clone(); estride_right_outer = dim1_2.stride_guarded().clone(); espan_right_inner = dim1_1.span_guarded().clone(); espan_right_outer = dim1_2.span_guarded().clone(); } else if (rel_stride1.is_greater_than()) { estride_right_inner = dim1_2.stride_guarded().clone(); estride_right_outer = dim1_1.stride_guarded().clone(); espan_right_inner = dim1_2.span_guarded().clone(); espan_right_outer = dim1_1.span_guarded().clone(); } } } /// ... Now check for an interleaved access pattern /// ... How to implement this??? diff = diff % stride_left_outer; /// ... Do the range test type check if (espan_left_inner && espan_right_inner && estride_left_outer) { Relation rel_left = range_acc.compare(*ediff, *espan_left_inner); Expression * right_extent = add(ediff->clone(), espan_right_inner->clone()); Relation rel_right = range_acc.compare(*right_extent, *estride_left_outer); delete right_extent; if (rel_left.is_greater_than() && rel_right.is_less_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } delete ediff; if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } /// ... Do the GCD test type check if (! divides_diff(*estride_left_inner, ediff, *aa1, *aa2, OVERESTIMATE) && rel_right.is_less_than()) { if (_ar_logging && _ar_logging % 2 == 0) { arlog << "No intersection" << endl; } delete ediff; if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } } } delete ediff; /// ... ??? } /// ... Just don't know - use conservative direction if (_ar_logging && _ar_logging % 2 == 0) { arlog << endl << "Not enough info" << endl; } if (direction == OVERESTIMATE) { intersect.ins_last(ard1.clone()); intersect.ins_last(ard2.clone()); /// ... Add nothing to new_ard1 or new_ard2 if (_ar_logging && _ar_logging % 2 == 0) { arlog << "OVERESTIMATE - ARD1 & ARD2 in intersection, discard both" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return true; } else { /// ... UNDERESTIMATE if (_ar_logging && _ar_logging % 2 == 0) { arlog << "Just don't know - UNDERESTIMATE with empty intersection" << endl; } if (newaa1) delete aa1; if (newaa2) delete aa2; if (_ar_logging && _ar_logging % 2 == 0) { arlog << "New ARD1:" << new_ard1 << endl; arlog << "New ARD2:" << new_ard2 << endl; } istats.inter_ARD.stop(); return false; } istats.inter_ARD.stop(); } /// calc_stride_span_match - /// Do a complete matching of the dimensions of two descriptors. Record /// the match in the stride_match and span_match arrays. void calc_stride_span_match(AbstractAccess & aa1, AbstractAccess & aa2, RangeAccessor & range_acc, Array<int> & stride_match1, Array<int> & stride_match2, Array<bool> & span_match1, Array<bool> & span_match2) { int ndims1 = aa1.number_of_dimensions(); int ndims2 = aa2.number_of_dimensions(); /// ... Initialize all match arrays for (int ii=0; ii<ndims1; ++ii) { stride_match1[ii] = -1; span_match1[ii] = false; } for (int ii=0; ii<ndims2; ++ii) { stride_match2[ii] = -1; span_match2[ii] = false; } /// ... Check the two descriptors for stride-equivalence UBiGraphIterator ubi( ndims1, ndims2 ); for ( ; ubi.valid(); ++ubi) { UBiEdge & edge = ubi.current(); int lodim = edge.node_1( ); int hidim = edge.node_2( ); if ((stride_match1[lodim] == -1) && (stride_match2[hidim] == -1)) { /// ... Check stride for match const Relation & relstr = range_acc.compare(aa1.dimension(lodim).stride_guarded(), aa2.dimension(hidim).stride_guarded()); if (relstr.is_equal()) { stride_match1[lodim] = hidim; stride_match2[hidim] = lodim; } } } /// ... Check span for match for (int ii=0; ii<ndims1; ++ii) { int lodim = ii; int hidim = stride_match1[ii]; if (hidim == -1) continue; /// ... No matching dimension const Relation & relsp = range_acc.compare(aa1.dimension(lodim).span_guarded(), aa2.dimension(hidim).span_guarded()); if (relsp.is_equal()) { span_match1[lodim] = true; span_match2[hidim] = true; } } } //static Boolean //_is_relational_op (const Expression & expr) //{ /// switch (expr.op()) { /// case EQ_OP: /// case NE_OP: /// case LT_OP: /// case LE_OP: /// case GT_OP: /// case GE_OP: // return True; /// default: // return False; /// } //} /// Take the match of ARD1 to ARD2 indicated by match_index and return a /// match array from ARD2 to ARD1. Array<int> * invert_match(Array<int> * match_index, int new_dims) { Array<int> * inverted_match_index = new Array<int>; inverted_match_index->resize(new_dims); /// ... Invert match_index for (int ii=0; ii<new_dims; ++ii) { (*inverted_match_index)[ii] = -1; } for (int ii=0; ii<match_index->entries(); ++ii) { if ((*match_index)[ii] != -1) (*inverted_match_index)[(*match_index)[ii]] = ii; } return inverted_match_index; } /// Respond whether the predicate of ARD1 implies that the predicate of ARD2 is true bool ar_implies(AbstractAccess & aa1, AbstractAccess & aa2) { if (aa2.exec_predicate_true()) return true; /// ... Here, we know that aa2 has a predicate and it's not .TRUE. if (aa1.exec_predicate_true()) return false; /// ... Here, we know that both predicates exist and neither are .TRUE. if (aa1.exec_predicate() == aa2.exec_predicate()) return true; /// ... Both descriptors have predicates /// ... aa1's predicate is the implier; aa2's predicate is the implied PredicateRepository & repos = aa1.pgm_summarized_to()->pred_repos(); /// ... 1. Transform x .NE. y into (x .LT. y) .OR. (x .GT. y) Expression * implier = repos.predicate(repos.transform_not_equal(aa1.exec_predicate())); Expression * implied = repos.predicate(repos.transform_not_equal(aa2.exec_predicate())); /// ... 2. Attempt to prove that implied subsumes implier bool subsume = ar_subsume(*implier, *implied); return subsume; } /// Attempt to prove that implier => implied. Assume that the two /// expressions have been simplified. Better inference techniques /// can be added here to increase the precision of the result. For /// instance, if we are checking whether MARK2 implies N .GT. 0, /// we might follow an SSA link for MARK2 back to its definition, /// which might be: /// /// MARK0 = .FALSE. /// IF (N .GT. 0) MARK1 = .TRUE. /// MARK2 = PHI(MARK0, MARK1) /// /// In this case, /// MARK2 being .TRUE. would directly imply that N .GT. 0. bool ar_subsume(Expression & implier, Expression & implied) { bool any = false; bool any2 = false; bool all = true; bool all2 = true; switch (implied.op()) { case AND_OP: for (Iterator<Expression> iter_implied = implied.arg_list(); iter_implied.valid(); ++iter_implied) { if (!ar_subsume(implier, iter_implied.current())) { all = false; break; } } return all; case OR_OP: for (Iterator<Expression> iter_implied = implied.arg_list(); iter_implied.valid(); ++iter_implied) { if (ar_subsume(implier, iter_implied.current())) { any = true; break; } } return any; case LOGICAL_CONSTANT_OP: if (implied.str_data() == ".TRUE.") return true; else return false; case EQ_OP: case NE_OP: case LT_OP: case LE_OP: case GT_OP: case GE_OP: switch (implier.op()) { case AND_OP: for (Iterator<Expression> iter_implier = implier.arg_list(); iter_implier.valid(); ++iter_implier) { if (ar_subsume(iter_implier.current(), implied)) { any2 = true; break; } } return any2; case OR_OP: for (Iterator<Expression> iter_implier = implier.arg_list(); iter_implier.valid(); ++iter_implier) { if (!ar_subsume(iter_implier.current(), implied)) { all2 = false; break; } } return all2; case LOGICAL_CONSTANT_OP: return false; case ID_OP: case ARRAY_REF_OP: return false; case EQ_OP: case NE_OP: case LT_OP: case LE_OP: case GT_OP: case GE_OP: if (subsume_relation(implier, implied)) { return true; } else { return false; } case NOT_OP: return false; default: p_abort("Unexpected operator in ar_subsume: implier"); } case ARRAY_REF_OP: switch (implier.op()) { case ARRAY_REF_OP: if ((implier.base_variable_ref() == implied.base_variable_ref()) && (implier.subscript() == implied.subscript())) { return true; } else { return false; } case AND_OP: for (Iterator<Expression> iter_implier = implier.arg_list(); iter_implier.valid(); ++iter_implier) { if (ar_subsume(iter_implier.current(), implied)) { any2 = true; break; } } return any2; case OR_OP: for (Iterator<Expression> iter_implier = implier.arg_list(); iter_implier.valid(); ++iter_implier) { if (!ar_subsume(iter_implier.current(), implied)) { all2 = false; break; } } return all2; default: return false; } case ID_OP: switch (implier.op()) { case ID_OP: if (implier.base_variable_ref() == implied.base_variable_ref()) { return true; } else { return false; } case AND_OP: for (Iterator<Expression> iter_implier = implier.arg_list(); iter_implier.valid(); ++iter_implier) { if (ar_subsume(iter_implier.current(), implied)) { any2 = true; break; } } return any2; case OR_OP: for (Iterator<Expression> iter_implier = implier.arg_list(); iter_implier.valid(); ++iter_implier) { if (!ar_subsume(iter_implier.current(), implied)) { all2 = false; break; } } return all2; default: return false; } case NOT_OP: /// ... Does B imply .NOT.A? Only if A implies .NOT. B switch (implier.op()) { case ID_OP: /// ... Is this A => .NOT. A? or B => .NOT. A? if (implied.expr_guarded().op() == ID_OP) { return false; } return false; case NOT_OP: /// ... Is this .NOT. A => .NOT. A? if ((implied.expr_guarded().op() == ID_OP) && (implier.expr_guarded().op() == ID_OP)) { return &(implier.expr_guarded().symbol()) == &(implier.expr_guarded().symbol()); } return false; case AND_OP: for (Iterator<Expression> iter_implier = implier.arg_list(); iter_implier.valid(); ++iter_implier) { if (ar_subsume(iter_implier.current(), implied)) { any2 = true; break; } } return any2; case OR_OP: for (Iterator<Expression> iter_implier = implier.arg_list(); iter_implier.valid(); ++iter_implier) { if (!ar_subsume(iter_implier.current(), implied)) { all2 = false; break; } } return all2; default: return false; } default: p_abort("Unexpected operator in ar_subsume: implied"); } return false; } /// subsume_relation - /// Does the implied_subtree expression subsume (completely cover) the /// implier_subtree? The roots of the subtrees used as parameters here are both /// relational operators. Do what is appropriate given the operators. bool subsume_relation(const Expression & implier_subtree, const Expression & implied_subtree) { Expression * implier_left; Expression * implied_left; if (! (is_relational_op(implier_subtree.op()) && is_relational_op(implied_subtree.op())) ) { return false; } const Expression & plier_left = implier_subtree.left_guarded(); const Expression & plier_right = implier_subtree.right_guarded(); const Expression & plied_left = implied_subtree.left_guarded(); const Expression & plied_right = implied_subtree.right_guarded(); if ((plier_left.type().data_type() == CHARACTER_TYPE) || (plier_right.type().data_type() == CHARACTER_TYPE) || (plied_left.type().data_type() == CHARACTER_TYPE) || (plied_right.type().data_type() == CHARACTER_TYPE)) { if ((plier_left.type().data_type() == CHARACTER_TYPE) && (plier_right.type().data_type() == CHARACTER_TYPE) && (plied_left.type().data_type() == CHARACTER_TYPE) && (plied_right.type().data_type() == CHARACTER_TYPE)) { return implier_subtree == implied_subtree; /// ... A .EQ. B => A .EQ. B } else { return false; } } if (!is_integer_zero(plier_right)) { implier_left = simplify(sub(plier_left.clone(), plier_right.clone())); } else { implier_left = plier_left.clone(); } if (!is_integer_zero(plied_right)) { implied_left = simplify(sub(plied_left.clone(), plied_right.clone())); } else { implied_left = plied_left.clone(); } Expression * diff = 0; bool cover = false; switch (implied_subtree.op()) { case LT_OP: switch (implier_subtree.op()) { case LT_OP: diff = simplify(sub(implied_left->clone(), implier_left->clone())); if (is_integer_constant(*diff)) { if (diff->value() <= 0) cover = true; else cover = false; } else { if (*implied_left == *implier_left) { /// ... to handle cases the simplifier can't cover = true; } else { cover = false; /// ... Just don't know } } break; case LE_OP: diff = simplify(sub(implied_left->clone(), implier_left->clone())); if (is_integer_constant(*diff)) { if (diff->value() < 0) cover = true; else cover = false; } else cover = false; /// ... Just don't know break; case GT_OP: diff =