access_util.h File Referencefile access_util.h access regions utility functions More...
Go to the source code of this file.
|
Enumerations |
| enum | AR_MEET {
AR_X,
AR_Y,
AR_OR,
AR_AND,
AR_X_NOTY,
AR_NOTX_Y
} |
| enum | AR_CONSERVATIVE {
UNDERESTIMATE,
OVERESTIMATE
} |
| enum | AR_CERTAINTY {
AR_YES,
AR_NO,
AR_UNSURE
} |
Functions |
| void | print_access_region_statistics (ostream &o, const RefList< AbstractAccess > &list, Statement &stmt, Symbol &sym) |
| void | print_access_region_statistics (ostream &o, const List< AbstractAccess > &list, Statement &stmt, Symbol &sym) |
| void | init_ar_statistics (AR_Stats &stats) |
| void | collect_ar_statistics (AbstractAccess &access_region, AR_Stats &stats, Symbol &sym) |
| void | print_ar_stats_line (ostream &o, Statement &stmt, AR_Stats &stats) |
| 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) |
| | low-level intersection routine
|
| bool | ar_intersect (List< AbstractAccess > &list1, AR_CONSERVATIVE direction, IPAStats &istats) |
| | 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)
|
| bool | ar_intersect (List< AbstractAccess > &list1, int ard1, RefList< AbstractAccess > &discard1, List< AbstractAccess > &list2, int ard2, SimBiGraph &sbg, SimEdge &edge, IPAStats &istats) |
| bool | ar_intersect (List< AbstractAccess > &list1, int ard1, RefList< AbstractAccess > &discard1, List< AbstractAccess > &list2, int ard2, RefList< AbstractAccess > &discard2, SimBiGraph &sg, SimEdge &edge, List< AbstractAccess > &intersect, AR_CONSERVATIVE direction, AR_MEET meet_op, IPAStats &istats) |
| | ar_intersect - Attempt to remove the overlapping portion from the descriptors in list1 and list2.
|
| void | ar_intersect (List< AbstractAccess > &list1, List< AbstractAccess > &list2, AR_CONSERVATIVE direction, List< AbstractAccess > &result, IPAStats &istats) |
| | 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_subtract (List< AbstractAccess > &list1, List< AbstractAccess > &list2, AR_CONSERVATIVE direction, List< AbstractAccess > &result) |
| | 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) |
| | 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
|
| bool | ar_plausible_execution (List< AbstractAccess > &list) |
| | Determine whether any descriptors have a non-.FALSE. exec predicate.
|
| bool | ar_plausible_execution (AbstractAccess &aa) |
| | Determine whether this descriptor has a non-.FALSE. exec predicate.
|
| bool | ar_subregion (AbstractAccess &ar1, AbstractAccess &ar2, SimEdge &edge, AR_CONSERVATIVE direction, Array< int > *match=0) |
| | ar_subregion is ard1 a subregion of ard2 ?
|
| void | ar_append (List< AbstractAccess > &list1, List< AbstractAccess > &list2, IPAStats &istats) |
| | append list2 to list1
|
| 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) |
| | 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 (List< AbstractAccess > &list1, AbstractAccess *ard) |
| | append ard to list
|
| AbstractAccess * | compute_abstract_access (const Expression &expr, Statement *stmt, AR_TYPE artype) |
| SimilarityType | contig_type (SimilarityType oldtype) |
| void | check_access_patterns (Program &prog, ProgramUnit &pgm) |
| void | simplify_descriptors (List< AbstractAccess > &, IPAStats &istats) |
| void | simplify_descriptors_scalar (List< AbstractAccess > &, IPAStats &) |
| | The only job here is to eliminate ARDs whose predicates are the same.
|
| SimTypeOfChange | ar_aggregate (SimEdge &edge, SimGraph &sg, List< AbstractAccess > &list) |
| SimTypeOfChange | contiguous_aggregation (RangeAccessor *range_acc, AbstractAccess *edge1, AbstractAccess *edge2, int smaller_offset, int dim_less_index, int dim_grt_index) |
| | Test the contiguous-region conditions.
|
| RefList< AbstractAccess > * | ar_interleave (SimGraphIterator &sgit, SimGraph &sg) |
| void | add_to_chain (AbstractAccess *node1, AbstractAccess *node2, List< RefList< AbstractAccess > > &chain_list) |
| | Add a link node1->node2 to the chain(s) in the List of RefLists.
|
| 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) |
| | calc_stride_span_match - Do a complete matching of the dimensions of two descriptors.
|
| Array< int > * | invert_match (Array< int > *match_index, int new_dims) |
| | Take the match of ARD1 to ARD2 indicated by match_index and return a match array from ARD2 to ARD2.
|
| bool | ar_implies (AbstractAccess &aa1, AbstractAccess &aa2) |
| | Respond whether the predicate of ARD1 implies that the predicate of ARD2 is true.
|
| bool | ar_offsets_match (AbstractAccess &descr1, AbstractAccess &descr2) |
| bool | ar_predicates_equal (AbstractAccess &aa1, AbstractAccess &aa2) |
| | Are the predicates of the two descriptors equivalent?
|
| bool | ar_predicates_negation (AbstractAccess &aa1, AbstractAccess &aa2) |
| | Are the predicates of the two descriptors negations of each other?
|
| Expression * | and_predicate (Expression *ex1, Expression *ex2, Expression *ex3=0) |
| Expression * | or_predicate (Expression *ex1, Expression *ex2, Expression *ex3=0) |
| bool | ar_subsume (Expression &implier, Expression &implied) |
| | Attempt to prove that implier => implied.
|
| bool | subsume_relation (const Expression &implier_subtree, const Expression &implied_subtree) |
| | 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.
|
| Expression * | transform_not_equal (Expression *expr) |
| | transform_not_equal - Transform x .NE.
|
| bool | test_linkedness (const Expression &expr1, const Expression &expr2) |
| void | elim_equivalent_descrs (List< AbstractAccess > &list, IPAStats &istats) |
| | The only job here is to eliminate equivalent ARDs.
|
| bool | ar_descriptors_equal (AbstractAccess &ard1, AbstractAccess &ard2) |
| | Check for two descriptors being equivalent.
|
| bool | ar_descriptor_member (List< AbstractAccess > &list, AbstractAccess &lmad) |
| | Check whether the given LMAD is already in the given list.
|
| int | ar_effort_limit () |
| void | ar_replace_with_approx (List< AbstractAccess > &list) |
| | Replace the LMADs on the given list with a single, approximate LMAD.
|
| bool | divides_diff (Expression &expr, Expression *diff, AbstractAccess &ard1, AbstractAccess &ard2, AR_CONSERVATIVE direction) |
| bool | is_singleton (Symbol &index, Expression &expr) |
| | is_singleton - Determine whether the given loop index is a "singleton index" in the given array reference expression.
|
Detailed Description
file access_util.h access regions utility functions
Polaris access_util.h - See also:
- access_util.h
access_util.cc
Definition in file access_util.h.
Enumeration Type Documentation
|
|
- Enumeration values:
-
| AR_X |
|
| AR_Y |
|
| AR_OR |
|
| AR_AND |
|
| AR_X_NOTY |
|
| AR_NOTX_Y |
|
Definition at line 25 of file access_util.h. |
|
|
- Enumeration values:
-
| UNDERESTIMATE |
|
| OVERESTIMATE |
|
Definition at line 34 of file access_util.h. |
Function Documentation
| void init_ar_statistics |
( |
AR_Stats & |
stats |
) |
|
|
|
|
Definition at line 73 of file access_util.cc.
References AR_Stats::base_dc, AR_Stats::both_same_dims, AR_Stats::callee_1, AR_Stats::callee_grtr_dims, AR_Stats::caller_1, AR_Stats::caller_grtr_dims, AR_Stats::diagonal, AR_Stats::exact, AR_Stats::greater_declared_dim, AR_Stats::inexact, AR_Stats::less_declared_dim, AR_Stats::match_declared_dim, AR_Stats::maxnest, AR_Stats::minnest, AR_Stats::monotonic_unknown, AR_Stats::nonaffine, AR_Stats::print, AR_Stats::proc_boundary, AR_Stats::proven_monotonic, AR_Stats::proven_nonmonotonic, AR_Stats::subscr_subscr, AR_Stats::total, AR_Stats::total_dims, AR_Stats::totalnest, and AR_Stats::triangular.
Referenced by print_access_region_statistics(). |
|
|
... dims in calling context
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; }
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 exact = access_region.accuracy() == ACCU_EXACT;
if (exact) { stats.exact++; } else { stats.inexact++; }
p_assert(access_region.actual_exists(), "No actual expression registered"); p_assert((access_region.actual_guarded().op() == ARRAY_REF_OP) ||
... Go through the set of dimensionalities
... Check for uniqueness
... Check for uniqueness only considering dimensions (ignoring start expr)
... Check for uniqueness only considering strides
... Check for uniqueness considering all-but-one dimensions
... Check for uniqueness considering start and all-but-one dimension
Definition at line 120 of file access_util.cc.
References _ar_match_dims, _ar_prtstats, Accreg_set::ar, Accreg_set::count, Dimcount::count, Dimcount::dims, ENTRY_STMT, Accreg_set::next, Dimcount::next, Statement::stmt_class(), and switch_value().
Referenced by print_access_region_statistics(). |
|
|
low-level intersection routine
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.
... silvius: try this first.
... If either predicate is .FALSE., then there can be no intersection
... Can't do much. Just check if mins against maxes.
... no intersection
... assume intersection
... Add nothing to new_ard1 or new_ard2
... UNDERESTIMATE
... Take care of the _SEMI cases.
... 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
... Add match elements for new dimensions
... dims2 == 0
... aa1 has fewer dimensions ... Make a new descriptor for aa1 with strides equivalent to those in aa2 and zero spans
... Invert match_index
... add_dimension does ins_last
... dims1 == 0
... add_dimension does ins_last
... Now, we know that the strides are equivalent
... both represent same location
... Intersect descriptor
... accesses don't overlap
... Do the above symbolically
... Intersect descriptor
... accesses don't overlap
... accesses don't overlap
... Add nothing to new_ard1 or new_ard2
... UNDERESTIMATE
... accesses don't overlap
... aa1 starts to the right of aa2 ... We know (from above) that start1 <= lastoff2
... New start1 is one stride after end of aa2 ... New start2 is old start2
... Intersect descriptor
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... aa1 is a subregion of aa2.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... lastoff1 < lastoff2
... aa1 is a subregion of aa2. Nothing in new_ard1.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... aa1 and aa2 start at the same point
... Just 1 piece of ard1 survives
... intersection is aa2. aa2 disappears.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... ARD1 == ARD2. Both disappear into the intersection.
... lastoff1 < lastoff2 ... Just 1 piece of ard2 survives
... intersection is aa1. aa1 disappears.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... diff < 0 -> aa2 starts to the right of aa1
... aa2 is a subregion of aa1. Nothing in new_ard2.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... aa2 is a subregion of aa1. Nothing in new_ard2.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... New start2 is one stride after end of aa1 ... New start1 is old start1
... Intersect descriptor
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... Points don't overlap
... Do the same as above, only symbolically
... accesses don't overlap
... 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.
... Check whether the stride divides the diff, and how certain we are about that
... If we weren't sure about the evenly_divides, we would have returned before this.
... aa1 starts to the right of aa2
... We know (from above) that start1 <= lastoff2
... New start1 is one stride after end of aa2 ... New start2 is old start2
... Intersect descriptor
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... aa1 is a subregion of aa2. aa1 disappears.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... lastoff1 < lastoff2
... aa1 is a subregion of aa2. Nothing in new_ard1.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... Just don't know - use the conservative direction
... Add nothing to new_ard1 or new_ard2
... UNDERESTIMATE
... aa1 and aa2 start at the same point
... lastoff1 > lastoff2
... Just 1 piece of ard1 survives
... intersection is aa2. aa2 disappears.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... lastoff1 == lastoff2
... ARD1 == ARD2. Both disappear into the intersection.
... lastoff1 < lastoff2 ... Just 1 piece of ard2 survives
... intersection is aa1. aa1 disappears.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... Not enough information, use conservative direction
... Add nothing to new_ard1 or new_ard2
... UNDERESTIMATE
... aa1 starts to the left of aa2
... lastoff1 > lastoff2
... aa2 is a subregion of aa1. Nothing in new_ard2.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... lastoff1 == lastoff2
... aa2 is a subregion of aa1. Nothing in new_ard2.
... This can't be propagate the reduction characteristic because ... the two ARDs aren't identical
... New start2 is one stride after end of aa1 ... New start1 is old start1
... Intersect descriptor
... Do we know the relationship between lastoff1 and start2?
... OK, there definitely is an intersection
... We just don't know, so add a predicate to each descriptor ... If there is an intersection:
... If there is not an intersection:
... This can't propagate the reduction characteristic because ... the two ARDs aren't identical
... Just don't know, use conservative direction
... Add nothing to new_ard1 or new_ard2
... UNDERESTIMATE
... We just don't know
... Add nothing to new_ard1 or new_ard2
... UNDERESTIMATE
... Points don't overlap
... diff < 0
... aa1 is to the left
... aa1 is to the right
... Now do range test type check
... Now do GCD test type check
... Do the above symbolically
... 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").
... diff < 0
... 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").
... aa1 is to the left
... aa1 is to the right
... Now check for an interleaved access pattern ... How to implement this??? diff = diff stride_left_outer; ... Do the range test type check
... Do the GCD test type check
... ???
... Just don't know - use conservative direction
... Add nothing to new_ard1 or new_ard2
... UNDERESTIMATE
Definition at line 2581 of file access_util.cc.
References _ar_logging, AbstractAccess::actual_stmt(), add(), AbstractAccess::add_dimension(), PredicateRepository::and_pred(), AR_AND, AR_NOTX_Y, AR_OR, AR_X, AR_X_NOTY, AR_Y, arlog, AccessDimension::check_overlap(), Expression::clone(), AccessDimension::clone(), AbstractAccess::clone(), Expression::compare(), constant(), AbstractAccess::del_dimension(), AbstractAccess::dimension(), divides_diff(), AbstractAccess::exec_predicate(), AbstractAccess::exec_predicate_false(), ge(), gt(), PredicateRepository::ins(), INTEGER_CONSTANT_OP, invert_match(), Relation::is_equal(), Relation::is_greater_equal(), Relation::is_greater_than(), AbstractAccess::is_imprecise(), is_integer_zero(), Relation::is_less_equal(), Relation::is_less_than(), Relation::is_not_equal(), lt(), PredicateRepository::notx_and_y_pred(), AbstractAccess::number_of_dimensions(), Expression::op(), PredicateRepository::or_pred(), OVERESTIMATE, AbstractAccess::pgm_summarized_to(), AbstractAccess::poss_reduct(), ProgramUnit::range_dict_guarded(), RED_OP_NONE, AbstractAccess::reduct_op(), Array< T >::resize(), SIM_DIM_EQUIV_SEMI, SIM_EQUIV_SEMI, SIM_NOT_SIMILAR, SIM_STRIDE_EQUIV, SIM_STRIDE_EQUIV_SEMI, simplify(), AccessDimension::span(), AccessDimension::span_guarded(), AbstractAccess::start(), AbstractAccess::start_guarded(), AccessDimension::stride_guarded(), sub(), AbstractAccess::summarized_to(), sym_factors(), Statement::tag(), Expression::type(), UNDERESTIMATE, Expression::value(), and PredicateRepository::x_and_noty_pred().
Referenced by ar_intersect(). |
|
|
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
... Use AND as the Meet operator since this is for straightline code
Definition at line 573 of file access_util.cc.
References _ar_logging, AR_AND, ar_plausible_execution(), arlog, SimGraphIterator::current(), intersect_ARDs(), SimEdge::node_1(), SimEdge::node_2(), AbstractAccess::pgm_summarized_to(), SimBiGraph::range_acc(), ProgramUnit::range_dict_guarded(), range_stmt(), AbstractAccess::summarized_to(), and SimGraphIterator::valid(). |
| 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 |
|
) |
|
|
|
|
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.
Definition at line 2475 of file access_util.cc.
References ar_append(), ar_descriptor_member(), intersect_ARDs(), and List< T >::valid(). |
|
|
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)
... Use AND as the Meet operator, since this is for straight-line code
... discard the indicated descriptors
Definition at line 473 of file access_util.cc.
References _ar_logging, AbstractAccess::actual_stmt(), AR_AND, ar_descriptor_member(), arlog, SimBiGraphIterator::current(), SimBiGraphIterator::current_list1(), SimBiGraphIterator::current_list2(), RefList< T >::del(), List< T >::entries(), List< T >::grab(), RefList< T >::ins_last(), intersect_ARDs(), SimBiGraphIterator::list1_valid(), SimBiGraphIterator::list2_valid(), RefList< T >::member(), SimBiGraphIterator::next_list1_node(), SimBiGraphIterator::next_list2_node(), AbstractAccess::pgm_summarized_to(), SimBiGraph::range_acc(), ProgramUnit::range_dict_guarded(), range_stmt(), AbstractAccess::summarized_to(), and RefList< T >::valid(). |
|
|
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
... if lastoffset[A] < baseoffset[B]
Definition at line 1165 of file access_util.cc.
References _ar_logging, ar_subregion(), arlog, SimBiGraph::clone(), SimBiGraphIterator::current(), SimBiGraphIterator::current_list1(), SimBiGraphIterator::current_list2(), Relation::is_less_than(), SimBiGraphIterator::list1_valid(), SimBiGraphIterator::list2_valid(), SimBiGraphIterator::next_list1_node(), SimBiGraphIterator::next_list2_node(), OVERESTIMATE, AbstractAccess::pgm_summarized_to(), SimBiGraph::range_acc(), ProgramUnit::range_dict_guarded(), range_stmt(), SIM_EQUIV, AbstractAccess::summarized_to(), and SimEdge::type(). |
|
|
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
... if lastoffset[A] < baseoffset[B]
Definition at line 1246 of file access_util.cc.
References _ar_logging, ar_subregion(), arlog, SimBiGraphIterator::current(), SimBiGraphIterator::current_list1(), SimBiGraphIterator::current_list2(), RefList< T >::del(), RefList< T >::ins_first(), Relation::is_less_than(), SimBiGraphIterator::list1_valid(), SimBiGraphIterator::list2_valid(), SimBiGraphIterator::next_list1_node(), SimBiGraphIterator::next_list2_node(), AbstractAccess::pgm_summarized_to(), SimBiGraph::range_acc(), ProgramUnit::range_dict_guarded(), range_stmt(), SIM_EQUIV, AbstractAccess::summarized_to(), SimEdge::type(), UNDERESTIMATE, and RefList< T >::valid(). |
|
|
Determine whether any descriptors have a non-.FALSE. exec predicate.
execution predicates. If not, the routine returns "false". If so, the routine returns "true".
Definition at line 6465 of file access_util.cc.
References ar_plausible_execution(). |
|
|
Determine whether this descriptor has a non-.FALSE. exec predicate.
Definition at line 6478 of file access_util.cc. |
|
|
ar_subregion is ard1 a subregion of ard2 ?
... 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
... Now we know aa2 is left of aa1
... When aa2 is 1-dimensional, stride 1, if ... aa1 fits totally inside aa2, then it is a subregion
... If pred(ARD1) implies pred(ARD2), then check the regions for subregion-ness
... Take care of the _SEMI cases.
... Copy ARD1
... Invert match_index
... Check whether we can determine subregion-ness immediately
... 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.
... No match in ARD1 for dim ii in ARD2
... 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
... add_dimension does ins_last
... Copy ARD2
... Add dimensions from ARD1 which were not matched, set spans to 0
... If all spans of ard1 are less or equal to the associated spans of ard2 ... we have a subregion
... 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
... If we get to this point, we just don't know, so let the ... conservative direction determine how we respond.
... direction == OVERESTIMATE
Definition at line 630 of file access_util.cc.
References _ar_logging, add(), AbstractAccess::add_dimension(), ar_implies(), AR_YES, arlog, AccessDimension::clone(), Expression::clone(), AbstractAccess::clone(), Expression::compare(), RangeAccessor::compare(), constant(), AbstractAccess::dimension(), expr_divides(), INTEGER_CONSTANT_OP, invert_match(), Relation::is_equal(), Relation::is_greater_equal(), Relation::is_greater_than(), is_integer_one(), Relation::is_less_equal(), Relation::is_less_than(), AbstractAccess::lastoffset(), AbstractAccess::number_of_dimensions(), Expression::op(), AbstractAccess::pgm_summarized_to(), SimBiGraph::range_acc(), ProgramUnit::range_dict_guarded(), range_stmt(), Array< T >::resize(), SIM_DIM_EQUIV_SEMI, SIM_EQUIV, SIM_EQUIV_SEMI, SIM_STRIDE_EQUIV, SIM_STRIDE_EQUIV_SEMI, simplify(), AccessDimension::span(), AccessDimension::span_guarded(), AbstractAccess::start_guarded(), AccessDimension::stride_guarded(), sub(), AbstractAccess::summarized_to(), UNDERESTIMATE, and Expression::value().
Referenced by ar_subtract(), and simplify_descriptors(). |
|
|
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
... Add the actual expression to the rep
... Set the byte size of the descriptor.
Definition at line 1080 of file access_util.cc.
References ACCU_EXACT, AbstractAccess::add_actual(), AR_READ, AR_WRITE, ARRAY_REF_OP, AbstractAccess::byte_size(), constant(), FUNCTION_CLASS, linearize_zero_registered(), AbstractAccess::no_overlap(), AbstractAccess::read_only(), Type::size(), Symbol::sym_class(), Symbol::type(), VARIABLE_CLASS, and AbstractAccess::write_first().
Referenced by InlineObject::remap_arg_names(). |
|
|
Definition at line 1127 of file access_util.cc.
References SIM_DIM_EQUIV, SIM_DIM_EQUIV_SEMI, SIM_DIM_EQUIV_UP, SIM_EQUIV, SIM_EQUIV_SEMI, SIM_NOT_SIMILAR, SIM_STRIDE_EQUIV, SIM_STRIDE_EQUIV_SEMI, SIM_STRIDE_EQUIV_UP, and SIM_UNKNOWN.
Referenced by SimBiGraphIterator::record_change(), and SimGraphIterator::record_change(). |
|
|
... eliminate all descriptors with .FALSE. execution predicates
... Build similarity graph: ... Match up all combinations of descriptors
... First, eliminate all but one in the same equivalence class
... If the descriptors are structurally equivalent and neither ... have execution predicates:
... adjust similarity graph
... Set predicate .TRUE. for remaining descriptor ... adjust similarity graph
... Form the OR of the predicates
... ar_subregion uses "ar_implies" to see if ... descr1's exec predicate implies descr2's exec predicate
... Let the user tell us how much effort to apply ... to the interleaving test.
... Check for interleaving pattern among STRIDE_EQUIVALENT descriptors
... New combined descriptor
... Remove eliminated nodes from list and graph
... Check for contiguous aggregation
... adjust similarity graph
Definition at line 1364 of file access_util.cc.
References _ar_aggregate, _ar_coalesce, _ar_interleave, _ar_logging, ar_aggregate(), ar_effort_limit(), ar_interleave(), ar_predicates_equal(), ar_predicates_negation(), ar_subregion(), arlog, Expression::clone(), AbstractAccess::coalesce(), Iterator< T >::current(), SimGraphIterator::current(), SimGraphIterator::delete_node(), elim_equivalent_descrs(), RefList< T >::entries(), AbstractAccess::exec_predicate(), PredicateRepository::ins(), SimGraphIterator::mark_unknown(), SimEdge::node_1(), SimEdge::node_2(), or(), AbstractAccess::pgm_summarized_to(), ProgramUnit::pred_repos(), PredicateRepository::predicate(), SimGraph::print_similarities(), SimGraphIterator::record_change(), SimGraphIterator::reset(), SIM_COALESCE_NODE1, SIM_COALESCE_NODE2, SIM_CONTIG_NODE1, SIM_CONTIG_NODE2, SIM_EQUIV, SIM_EQUIVALENCE, SIM_NOCHANGE, SIM_SUBREG_NODE2, simplify(), SimEdge::type(), UNDERESTIMATE, Iterator< T >::valid(), and SimGraphIterator::valid(). |
|
|
... Take care of the _SEMI cases.
... This represented the descriptor which has dimension(s) added (if any)
... Copy ARD1
... Get the match from ARD2 to ARD1
... Add dimensions from ARD2 which were not matched, set spans to 0
... add_dimension does ins_last
... silvius: this is a memory leak
... Copy ARD2
... Add dimensions from ARD1 which were not matched, set spans to 0
... silvius: this is a memory leak
... Common point for Dimension-equivalent and Stride-equivalent descriptors
... First, determine the descriptor with the lesser offset ... If can't decide, can't go further for either type of relationship
... start1 < start2
... start2 <= start1
... cannot decide
... For Stride-equivalent descriptors, check for all-but-one matching ... and determine which dimension does not match.
... all spans but one match - try to aggregate
... 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.
Definition at line 1872 of file access_util.cc.
References _ar_logging, AbstractAccess::add_dimension(), arlog, AccessDimension::clone(), AbstractAccess::clone(), RangeAccessor::compare(), constant(), contiguous_aggregation(), AbstractAccess::dimension(), INTEGER_CONSTANT_OP, Relation::is_greater_equal(), Relation::is_less_than(), AbstractAccess::number_of_dimensions(), Expression::op(), SIM_CONTIG_NODE1, SIM_CONTIG_NODE2, SIM_DIM_EQUIV, SIM_DIM_EQUIV_SEMI, SIM_EQUIV, SIM_EQUIV_SEMI, SIM_EQUIVALENCE, SIM_NOCHANGE, SIM_NOT_SIMILAR, SIM_STRIDE_EQUIV, SIM_STRIDE_EQUIV_SEMI, AccessDimension::span(), AbstractAccess::start_guarded(), and Expression::value().
Referenced by simplify_descriptors(). |
|
|
Test the contiguous-region conditions.
... We can aggregate the two descriptors
... Modify descriptor with smaller offset
... Remove the actual pointer, because now it represents >1 sites ... Calculating the overlap characteristic
... Transfer overlap-check notations from dim_grt to dim_less
... Calc_overlap where necessary
... dim_grt is a subregion of dim_less, don't change span
cerr<<"\n descr1 = "<<*desc_less; cerr<<"\n descr2 = "<<*desc_grt;
... We can aggregate the two descriptors
cerr<<"\n sum = "<<*sum;
... silvius: ... maybe start2=start1+span1+stride
... Modify descriptor with smaller offset
... Remove the actual pointer, because now it represents >1 sites ... Calculating the overlap characteristic
... Does not change the overlap characteristic
... Say it will take a runtime test
... Transfer overlap-check notations from dim_grt to dim_less
... Calc_overlap where necessary
... dim_grt is a subregion of dim_less, don't change span
... cannot be sure, don't do anything
... Don't know, no change
Definition at line 2186 of file access_util.cc.
References _ar_logging, add(), AR_YES, arlog, AccessDimension::check_overlap(), Expression::clone(), Expression::compare(), Iterator< T >::current(), expr_divides(), INTEGER_CONSTANT_OP, Relation::is_equal(), Relation::is_greater_equal(), Relation::is_greater_than(), Relation::is_less_equal(), Relation::is_less_than(), Relation::is_not_equal(), Expression::op(), SIM_CONTIG_NODE1, SIM_CONTIG_NODE2, SIM_NOCHANGE, simplify(), AccessDimension::singleton(), AccessDimension::span(), AccessDimension::span_guarded(), AccessDimension::stride_guarded(), sub(), sum(), Iterator< T >::valid(), and Expression::value().
Referenced by ar_aggregate(). |
|
|
... Build chains of equidistant offsets
... First use a cheap comparison to find it
... Then, if necessary, use a range comparison
... If the current distance wasn't added to an existing chain, ... start a new chain
... Now, find the longest single chain and use that for interleaving.
... Return the longest chain
... drop through
... Add a new dimension to descriptor with smallest offset ... to represent all descriptors on the list.
... In "combined", save the info that dimensions need overlap checking
... Calc_overlap where necessary
Definition at line 1555 of file access_util.cc.
References _ar_logging, add_to_chain(), ar_predicates_equal(), arlog, AbstractAccess::calc_overlap(), AccessDimension::check_overlap(), Expression::clone(), RangeAccessor::compare(), constant(), Iterator< T >::current(), RefList< T >::entries(), Map< S, T >::ins(), RefList< T >::ins_first(), List< T >::ins_first(), RefList< T >::ins_last(), INTEGER_CONSTANT_OP, Relation::is_equal(), AbstractAccess::is_imprecise(), AbstractAccess::iter_dims(), mul(), NEG_EXPR, SimEdge::node_1(), SimEdge::node_2(), Expression::op(), AbstractAccess::set_check_overlap(), RangeComparator::signz(), SIM_DIM_EQUIV, simplify(), AbstractAccess::start_guarded(), sub(), SimEdge::type(), Iterator< T >::valid(), List< T >::valid(), and Expression::value().
Referenced by simplify_descriptors(). |
|
|
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.
... First, look for node1 at the end of a RefList
... Check whether node2 is at the beginning of a list
... Append list2 to list1
... Didn't find node2, so add node2 to RefList
... If we didn't find node1, check this time for node2 at the beginning of a RefList
... Check whether node2 is at the end of a list
... Prepend list2 to list1
... Didn't find node1, so add node1 to RefList
... If found neither node1 nor node2 in the lists, then we must begin a new RefList, containing ... those two nodes.
Definition at line 1759 of file access_util.cc.
References RefList< T >::entries(), RefList< T >::ins_first(), RefList< T >::ins_last(), and RefList< T >::valid().
Referenced by ar_interleave(). |
| Array<int>* invert_match |
( |
Array< int > * |
match_index, |
|
|
int |
new_dims |
|
) |
|
|
|
|
Respond whether the predicate of ARD1 implies that the predicate of ARD2 is true.
... Here, we know that aa2 has a predicate and it's not .TRUE.
... Here, we know that both predicates exist and neither are .TRUE.
... Both descriptors have predicates ... aa1's predicate is the implier; aa2's predicate is the implied
... 1. Transform x .NE. y into (x .LT. y) .OR. (x .GT. y)
... 2. Attempt to prove that implied subsumes implier
Definition at line 5312 of file access_util.cc.
References ar_subsume(), PredicateRepository::predicate(), and PredicateRepository::transform_not_equal().
Referenced by ar_subregion(). |
|
|
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.
... Does B imply .NOT.A? Only if A implies .NOT. B
... Is this A => .NOT. A? or B => .NOT. A?
... Is this .NOT. A => .NOT. A?
Definition at line 5356 of file access_util.cc.
References AND_OP, ar_subsume(), ARRAY_REF_OP, EQ_OP, GE_OP, GT_OP, ID_OP, LE_OP, LOGICAL_CONSTANT_OP, LT_OP, NE_OP, NOT_OP, OR_OP, and subsume_relation().
Referenced by ar_implies(), and ar_subsume(). |
|
|
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.
... A .EQ. B => A .EQ. B
... to handle cases the simplifier can't
... Just don't know
... Just don't know
... to handle cases the simplifier can't
... Just don't know
... Just don't know
... Try both ways
... Just don't know
... to handle cases the simplifier can't
... Just don't know
... to handle cases the simplifier can't
... Just don't know
... Try both ways
... to handle cases the simplifier can't
... Just don't know
... to handle cases the simplifier can't
... Just don't know
... to handle cases the simplifier can't
... Just don't know
... Try both ways
... to handle cases the simplifier can't
... Just don't know
... to handle cases the simplifier can't
... Just don't know
... Just don't know
... to handle cases the simplifier can't
... Just don't know
... Just don't know
... Try both ways
... Just don't know
... No way an EQ_OP can cover any of these
... Try both ways
... to handle cases the simplifier can't
... Just don't know
Definition at line 5547 of file access_util.cc.
References CHARACTER_TYPE, Expression::clone(), Type::data_type(), EQ_OP, GE_OP, GT_OP, is_integer_constant(), is_integer_zero(), is_relational_op(), LE_OP, Expression::left_guarded(), LT_OP, Expression::right_guarded(), simplify(), sub(), Expression::type(), unary_minus(), and Expression::value().
Referenced by ar_subsume(). |
|
|
... silvius:
... AR_UNSURE: use conservative direction to determine result
... Fall-back position is to say it divides, but therefore ... the desireable result is to say it does not divide, and ... that result looks likely, since for it to divide, the non-constant ... expression would have to divide a particular value, so ... make a runtime test to give that condition, and say it does not divide.
... direction == UNDERESTIMATE
... Fall-back position is to say it does not divide, but therefore ... the desireable result is to say it does divide, and ... that result looks unlikely, since for it to divide, the non-constant ... expression would have to divide a particular constant, so ... just let the fall-back position happen without a runtime test.
Definition at line 6325 of file access_util.cc.
References and(), AR_NO, AR_YES, Expression::clone(), AbstractAccess::clone(), Expression::compare(), constant(), div(), expr_divides(), Relation::is_greater_than(), is_integer_zero(), Relation::is_less_than(), mul(), ne(), OVERESTIMATE, SimBiGraph::range_acc(), range_stmt(), simplify(), and unary_minus().
Referenced by intersect_ARDs(). |
|
|
is_singleton - Determine whether the given loop index is a "singleton index" in the given array reference expression.
A singleton index means that in whichever subscript position expression the loop index appears, no other loop index appears there. This routine currently computes something a little stricter than that - it finds where the index appears with no other variables of any type. This routine could relax its restriction, given a good test whether a given variable is a loop index or not.
Definition at line 6427 of file access_util.cc.
References Expression::arg_list(), ARRAY_REF_OP, Expression::base_variable_ref(), e, is_id(), and List< T >::valid(). |
|