#include "config.h"#include "system.h"#include "coretypes.h"#include "tree.h"#include "gimple-pretty-print.h"#include "gimple.h"#include "tree-ssa-loop-niter.h"#include "tree-ssa-loop.h"#include "tree-ssa.h"#include "cfgloop.h"#include "tree-data-ref.h"#include "tree-scalar-evolution.h"#include "dumpfile.h"#include "langhooks.h"#include "tree-affine.h"#include "params.h"
Data Structures | |
| struct | datadep_stats |
| struct | data_ref_loc_d |
Macros | |
| #define | FLOOR_DIV(x, y) ((x) / (y)) |
Typedefs | |
| typedef struct data_ref_loc_d | data_ref_loc |
Variables | |
| static struct datadep_stats | dependence_stats |
Macro Definition Documentation
| #define FLOOR_DIV | ( | x, | |
| y | |||
| ) | ((x) / (y)) |
Typedef Documentation
| typedef struct data_ref_loc_d data_ref_loc |
Describes a location of a memory reference.
Function Documentation
|
static |
Returns true when all the access functions of A are affine or constant with respect to LOOP_NEST.
|
static |
Adds a unit distance vector to DDR when there is a 0 overlap. This is the case for example when access functions are the same and equal to a constant, as in:
| loop_1 | A[3] = ... | ... = A[3] | endloop_1
in which case the distance vectors are (0) and (1).
Referenced by add_multivariate_self_dist().
|
static |
Helper function for the case where DDR_A and DDR_B are the same multivariate access function with a constant step. For an example see pr34635-1.c.
Polynomials with more than 2 variables are not handled yet. When the evolution steps are parameters, it is not possible to represent the dependence using classical distance vectors.
For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2).
References add_distance_for_zero_overlaps(), add_other_self_distances(), constant_access_functions(), DDR_NB_LOOPS, lambda_vector_new(), and save_dist_v().
|
static |
Helper function for the case where DDR_A and DDR_B are the same access functions.
The evolution step is not constant: it varies in the outer loop, so this cannot be represented by a distance vector. For example in pr34635.c the evolution is {0, +, {0, +, 4}_1}_2.
Referenced by add_multivariate_self_dist().
|
static |
Add a distance of 1 on all the loops outer than INDEX. If we haven't yet determined a distance for this outer loop, push a new distance vector composed of the previous distance, and a distance of 1 for this outer loop. Example:
| loop_1 | loop_2 | A[10] | endloop_2 | endloop_1
Saved vectors are of the form (dist_in_1, dist_in_2). First, we save (0, 1), then we have to save (1, 0).
For each outer loop where init_v is not set, the accesses are in dependence of distance 1 in the loop.
|
static |
Returns constant affine function with value CST.
Referenced by analyze_miv_subscript(), chrec_is_positive(), and lambda_matrix_row_exchange().
|
static |
Frees affine function FN.
References conflict_function::n, and NO_DEPENDENCE.
|
static |
Returns the difference of affine functions FNA and FNB.
References conflict_function::n, and NOT_KNOWN.
|
static |
Applies operation OP on affine functions FNA and FNB, and returns the result.
|
static |
Returns the sum of affine functions FNA and FNB.
|
static |
Returns affine function with single variable, CST + COEF * x_DIM.
References chrec_dont_know, double_int_fits_to_tree_p(), double_int_to_tree(), max_stmt_executions(), and unsigned_type_node.
|
static |
Returns the base of the affine function FN.
|
static |
Returns true if FN is a constant.
|
static |
Returns true if FNA == FNB.
References integer_zerop().
|
static |
Returns true if FN is the zero constant function.
|
static |
Entry point (for testing only). Analyze all the data references and the dependence relations in LOOP.
The data references are computed first.
A relation on these nodes is represented by a complete graph. Some of the relations could be of no interest, thus the relations can be computed on demand.
In the following function we compute all the relations. This is just a first implementation that is here for:
- for showing how to ask for the dependence relations,
- for the debugging the whole dependence graph,
- for the dejagnu testcases and maintenance.
It is possible to ask only for a part of the graph, avoiding to compute the whole dependence graph. The computed dependences are stored in a knowledge base (KB) such that later queries don't recompute the same information. The implementation of this KB is transparent to the optimizer, and thus the KB can be changed with a more efficient implementation, or the KB could be disabled.
Compute DDs on the whole function.
|
static |
Analyze a MIV (Multiple Index Variable) subscript with respect to LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and CHREC_B. For k >= 0, the following property is verified:
CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).
Access functions are the same: all the elements are accessed
in the same order.
For the moment, the following is verified:
evolution_function_is_affine_multivariate_p (chrec_a,
loop_nest->num) testsuite/.../ssa-chrec-33.c
{{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
The difference is 1, and all the evolution steps are multiples
of 2, consequently there are no overlapping elements. testsuite/.../ssa-chrec-35.c
{0, +, 1}_2 vs. {0, +, 1}_3
the overlapping elements are respectively located at iterations:
{0, +, 1}_x and {0, +, 1}_x,
in other words, we have the equality:
{0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
Other examples:
{{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
{0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
{{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
{{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)When the analysis is too difficult, answer "don't know".
References affine_fn_cst(), chrec_dont_know, conflict_fn(), dependence_stats, integer_zero_node, and datadep_stats::num_same_subscript_function.
|
static |
Determines the iterations for which CHREC_A is equal to CHREC_B in with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with two functions that describe the iterations that contain conflicting elements.
Remark: For an integer k >= 0, the following equality is true:
CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
If they are the same chrec, and are affine, they overlap on every iteration.
If they aren't the same, and aren't affine, we can't do anything yet.
References chrec_contains_undetermined(), chrec_known, CHREC_VARIABLE, DDR_LOOP_NEST, DDR_NB_LOOPS, DDR_NUM_SUBSCRIPTS, DDR_SUBSCRIPT, DR_ACCESS_FN, finalize_ddr_dependent(), index_in_loop_nest(), int_cst_value(), lambda_vector_new(), MIN, non_affine_dependence_relation(), operand_equal_p(), SUB_DISTANCE, and TREE_CODE.
|
static |
Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and CHREC_B. For k >= 0, the following property is verified:
CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).
|
static |
Analyze a SIV (Single Index Variable) subscript where CHREC_A is a constant, and CHREC_B is an affine function. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and CHREC_B. For k >= 0, the following property is verified:
CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).
Special case overlap in the first iteration.
Example:
chrec_a = 12
chrec_b = {10, +, 1} Perform weak-zero siv test to see if overlap is
outside the loop bounds. When the step does not divide the difference, there are
no overlaps. Example:
chrec_a = 12
chrec_b = {10, +, -1}
In this case, chrec_a will not overlap with chrec_b. Example:
chrec_a = 3
chrec_b = {10, +, -1} Perform weak-zero siv test to see if overlap is
outside the loop bounds. When the step does not divide the difference, there
are no overlaps. Example:
chrec_a = 3
chrec_b = {4, +, 1}
In this case, chrec_a will not overlap with chrec_b.
References conflict_fn_no_dependence(), dependence_stats, integer_zero_node, and datadep_stats::num_siv_independent.
|
static |
Determines the overlapping elements due to accesses CHREC_A and CHREC_B, that are affine functions. This function cannot handle symbolic evolution functions, ie. when initial conditions are parameters, because it uses lambda matrices of integers.
The accessed index overlaps for each iteration in the loop.
For determining the initial intersection, we have to solve a
Diophantine equation. This is the most time consuming part.
For answering to the question: "Is there a dependence?" we have
to prove that there exists a solution to the Diophantine
equation, and that the solution is in the iteration domain,
i.e. the solution is positive or zero, and that the solution
happens before the upper bound loop.nb_iterations. Otherwise
there is no dependence. This function outputs a description of
the iterations that hold the intersections.
Don't do all the hard work of solving the Diophantine equation
when we already know the solution: for example,
| {3, +, 1}_1
| {3, +, 4}_2
| gamma = 3 - 3 = 0.
Then the first overlap occurs during the first iterations:
| {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
U.A = S
Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
but that is a quite strange case. Instead of ICEing, answer
don't know. The classic "gcd-test".
The "gcd-test" has determined that there is no integer
solution, i.e. there is no dependence. Both access functions are univariate. This includes SIV and MIV cases.
Both functions should have the same evolution sign.
The solutions are given by:
|
| [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
| [u21 u22] [y0]
For a given integer t. Using the following variables,
| i0 = u11 * gamma / gcd_alpha_beta
| j0 = u12 * gamma / gcd_alpha_beta
| i1 = u21
| j1 = u22
the solutions are:
| x0 = i0 + i1 * t,
| y0 = j0 + j1 * t. There is no solution.
FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
falls in here, but for the moment we don't look at the
upper bound of the iteration domain. (X0, Y0) is a solution of the Diophantine equation:
"chrec_a (X0) = chrec_b (Y0)". (X1, Y1) is the smallest positive solution of the eq
"chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
first conflict occurs. If the overlap occurs outside of the bounds of the
loop, there is no dependence. FIXME: For the moment, the upper bound of the
iteration domain for i and j is not checked.
References conflict_fn_no_dependence(), and integer_zero_node.
|
static |
Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the relation between the elements accessed twice by CHREC_A and CHREC_B. For k >= 0, the following property is verified:
CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).
The difference is equal to zero: the accessed index
overlaps for each iteration in the loop.
The accesses do not overlap.
We're not sure whether the indexes overlap. For the moment,
conservatively answer "don't know".
References build_int_cst(), chrec_apply(), chrec_contains_undetermined(), chrec_fold_minus(), chrec_is_positive(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, evolution_function_is_affine_p(), get_chrec_loop(), number_of_latch_executions(), and tree_int_cst_sgn().
|
static |
Compute the classic per loop direction vector. DDR is the data dependence relation to build a vector from.
|
static |
Compute the classic per loop distance vector. DDR is the data dependence relation to build a vector from. Return false when fail to represent the data dependence as a distance vector.
Save the 0 vector.
Save the distance vector if we initialized one.
Verify a basic constraint: classic distance vectors should
always be lexicographically positive.
Data references are collected in the order of execution of
the program, thus for the following loop
| for (i = 1; i < 100; i++)
| for (j = 1; j < 100; j++)
| {
| t = T[j+1][i-1]; // A
| T[j][i] = t + 2; // B
| }
references are collected following the direction of the wind:
A then B. The data dependence tests are performed also
following this order, such that we're looking at the distance
separating the elements accessed by A from the elements later
accessed by B. But in this example, the distance returned by
test_dep (A, B) is lexicographically negative (-1, 1), that
means that the access A occurs later than B with respect to
the outer loop, ie. we're actually looking upwind. In this
case we solve test_dep (B, A) looking downwind to the
lexicographically positive solution, that returns the
distance vector (1, -1). In this case there is a dependence forward for all the
outer loops:
| for (k = 1; k < 100; k++)
| for (i = 1; i < 100; i++)
| for (j = 1; j < 100; j++)
| {
| t = T[j+1][i-1]; // A
| T[j][i] = t + 2; // B
| }
the vectors are:
(0, 1, -1)
(1, 1, -1)
(1, -1, 1) There is a distance of 1 on all the outer loops: Example:
there is a dependence of distance 1 on loop_1 for the array A.
| loop_1
| A[5] = ...
| endloop
|
static |
Return false when fail to represent the data dependence as a distance vector. INIT_B is set to true when a component has been added to the distance vector DIST_V. INDEX_CARRY is then set to the index in DIST_V that carries the dependence.
This is the subscript coupling test. If we have already recorded a distance for this loop (a distance coming from another subscript), it should be the same. For example, in the following code, there is no dependence:
| loop i = 0, N, 1 | T[i+1][i] = ... | ... = T[i][i] | endloop
This can be for example an affine vs. constant dependence
(T[i] vs. T[3]) that is not an affine dependence and is
not representable as a distance vector.
|
static |
Returns true when analyze_subscript_affine_affine can be used for determining the dependence relation between chrec_a and chrec_b, that contain symbols. This function modifies chrec_a and chrec_b such that the analysis result is the same, and such that they don't contain symbols, and then can safely be passed to the analyzer.
Example: The analysis of the following tuples of evolutions produce the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1 vs. {0, +, 1}_1
{x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1) {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
FIXME: For the moment not handled. Might be refined later.
|
static |
Returns the address ADDR of an object in a canonical shape (without nop casts, and with type of pointer to the object).
The base address may be obtained by casting from integer, in that case keep the cast.
|
static |
Determine whether the CHREC is always positive/negative. If the expression cannot be statically analyzed, return false, otherwise set the answer into VALUE.
FIXME – overflows.
Otherwise the chrec is under the form: "{-197, +, 2}_1",
and the proof consists in showing that the sign never
changes during the execution of the loop, from 0 to
loop->nb_iterations.
References affine_fn_cst(), conflict_fn(), integer_one_node, and integer_zero_node.
Referenced by analyze_ziv_subscript().
|
static |
If all the functions in CF are the same, returns one of them, otherwise returns NULL.
References signed_type_for(), and TYPE_PRECISION.
| void compute_affine_dependence | ( | struct data_dependence_relation * | ddr, |
| struct loop * | loop_nest | ||
| ) |
This computes the affine dependence relation between A and B with respect to LOOP_NEST. CHREC_KNOWN is used for representing the independence between two accesses, while CHREC_DONT_KNOW is used for representing the unknown relation.
Note that it is possible to stop the computation of the dependence relation the first time we detect a CHREC_KNOWN element for a given subscript.
Analyze only when the dependence relation is not yet known.
Dump the dependences from the first algorithm.
Save the result of the first DD analyzer.
Reset the information.
Compute the same information using Omega.
Check that we get the same information.
As a last case, if the dependence cannot be determined, or if
the dependence is considered too difficult to determine, answer
"don't know".
Referenced by ddr_consistent_p().
| bool compute_all_dependences | ( | vec< data_reference_p > | datarefs, |
| vec< ddr_p > * | dependence_relations, | ||
| vec< loop_p > | loop_nest, | ||
| bool | compute_self_and_rr | ||
| ) |
Compute in DEPENDENCE_RELATIONS the data dependence graph for all the data references in DATAREFS, in the LOOP_NEST. When COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self relations. Return true when successful, i.e. data references number is small enough to be handled.
Insert a single relation into dependence_relations: chrec_dont_know.
| bool compute_data_dependences_for_bb | ( | basic_block | bb, |
| bool | compute_self_and_read_read_dependences, | ||
| vec< data_reference_p > * | datarefs, | ||
| vec< ddr_p > * | dependence_relations | ||
| ) |
Returns true when the data dependences for the basic block BB have been computed, false otherwise. DATAREFS is initialized to all the array elements contained in this basic block, DEPENDENCE_RELATIONS contains the relations between the data references. Compute read-read and self relations if COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.
| bool compute_data_dependences_for_loop | ( | struct loop * | loop, |
| bool | compute_self_and_read_read_dependences, | ||
| vec< loop_p > * | loop_nest, | ||
| vec< data_reference_p > * | datarefs, | ||
| vec< ddr_p > * | dependence_relations | ||
| ) |
Returns true when the data dependences have been computed, false otherwise. Given a loop nest LOOP, the following vectors are returned: DATAREFS is initialized to all the array elements contained in this loop, DEPENDENCE_RELATIONS contains the relations between the data references. Compute read-read and self relations if COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.
If the loop nest is not well formed, or one of the data references is not computable, give up without spending time to compute other dependences.
|
static |
Solves the special case of a Diophantine equation where CHREC_A is an affine bivariate function, and CHREC_B is an affine univariate function. For example,
| {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
has the following overlapping functions:
| x (t, u, v) = {{0, +, 1336}_t, +, 1}_v | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
FORNOW: This is a specialized implementation for a case occurring in a common benchmark. Implement the general algorithm.
|
static |
Solves the special case of the Diophantine equation: | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the number of iterations that loops X and Y run. The overlaps will be constructed as evolutions in dimension DIM.
Referenced by initialize_matrix_A(), and lambda_vector_equal().
|
static |
Determine for each subscript in the data dependence relation DDR the distance.
References chrec_contains_symbols_defined_in_loop(), handled_component_p(), INDIRECT_REF_P, loop::num, TREE_CODE, and TREE_OPERAND.
|
static |
Creates a conflict function with N dimensions. The affine functions in each dimension follow.
Referenced by analyze_miv_subscript(), chrec_is_positive(), and lambda_matrix_row_exchange().
|
static |
Returns the conflict function for "independent".
References aff_comb_cannot_overlap_p(), aff_combination_add(), aff_combination_scale(), double_int_minus_one, DR_REF, and get_inner_reference_aff().
Referenced by analyze_siv_subscript_cst_affine(), and analyze_subscript_affine_affine().
|
static |
Returns the conflict function for "unknown".
References DR_BASE_OBJECT.
Referenced by gcd_of_steps_may_divide_p(), and initialize_matrix_A().
|
static |
Return true when the DDR contains only constant access functions.
Referenced by add_multivariate_self_dist().
|
read |
Analyzes memory reference MEMREF accessed in STMT. The reference is read if IS_READ is true, write otherwise. Returns the data_reference description of MEMREF. NEST is the outermost loop in which the reference should be instantiated, LOOP is the loop in which the data reference should be analyzed.
|
static |
Return true when DDR contains the same information as that stored in DIR_VECTS and in DIST_VECTS, return false otherwise.
If dump_file is set, output there.
Distance vectors are not ordered in the same way in the DDR
and in the DIST_VECTS: search for a matching vector. Direction vectors are not ordered in the same way in the DDR
and in the DIR_VECTS: search for a matching vector.
References compute_affine_dependence(), DR_IS_WRITE, FOR_EACH_VEC_ELT, initialize_data_dependence_relation(), NULL, and PARAM_VALUE.
| DEBUG_FUNCTION void debug | ( | ) |
Unified dump into FILE all the data references from DATAREFS.
Unified dump function for a DATA_REFERENCE structure.
References debug.
| DEBUG_FUNCTION void debug_data_dependence_relation | ( | ) |
Debug version.
References dump_data_dependence_relations().
| DEBUG_FUNCTION void debug_data_dependence_relations | ( | ) |
Dump to STDERR all the dependence relations from DDRS.
References DDR_NB_LOOPS, and print_lambda_vector().
| DEBUG_FUNCTION void debug_data_reference | ( | ) |
Print to STDERR the data_reference DR.
References DR_STMT, and print_gimple_stmt().
| DEBUG_FUNCTION void debug_data_references | ( | ) |
Dump into STDERR all the data references from DATAREFS.
References dump_data_reference().
| DEBUG_FUNCTION void debug_ddrs | ( | ) |
References build_int_cst(), fold_convert, split_constant_offset(), and ssizetype.
|
inlinestatic |
Return the direction for a given distance. FIXME: Computing dir this way is suboptimal, since dir can catch cases that dist is unable to represent.
References init_omega_eq_with_af(), and int_cst_value().
|
static |
Extracts the alias analysis information from the memory reference DR.
|
static |
Determines the base object and the list of indices of memory reference DR, analyzed in LOOP and instantiated in loop nest NEST.
If analyzing a basic-block there are no indices to analyze and thus no access functions.
REALPART_EXPR and IMAGPART_EXPR can be handled like accesses into a two element array with a constant index. The base is then just the immediate underlying object.
Analyze access functions of dimensions we know to be independent.
For COMPONENT_REFs of records (but not unions!) use the
FIELD_DECL offset as constant access function so we can
disambiguate a[i].f1 and a[i].f2. If we have an unhandled component we could not translate
to an access function stop analyzing. We have determined
our base object in this case. If the address operand of a MEM_REF base has an evolution in the analyzed nest, add it as an additional independent access-function.
Fold the MEM_REF offset into the evolutions initial
value to make more bases comparable. ??? This is still not a suitable base object for
dr_may_alias_p - the base object needs to be an
access that covers the object as whole. With
an evolution in the pointer this cannot be
guaranteed.
As a band-aid, mark the access so we can special-case
it in dr_may_alias_p. Canonicalize DR_BASE_OBJECT to MEM_REF form.
References analyze_scalar_evolution(), BITS_PER_UNIT, bitsize_int, bitsizetype, component_ref_field_offset(), DECL_FIELD_BIT_OFFSET, fold_convert, instantiate_scev(), size_binop, TREE_CODE, TREE_OPERAND, and TREE_TYPE.
| bool dr_analyze_innermost | ( | ) |
Analyzes the behavior of the memory reference DR in the innermost loop or basic block that contains it. Returns true if analysis succeed or false otherwise.
| bool dr_equal_offsets_p | ( | struct data_reference * | dra, |
| struct data_reference * | drb | ||
| ) |
Check if DRA and DRB have equal offsets.
|
static |
Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical expressions.
| bool dr_may_alias_p | ( | const struct data_reference * | a, |
| const struct data_reference * | b, | ||
| bool | loop_nest | ||
| ) |
Returns false if we can prove that data references A and B do not alias, true otherwise. If LOOP_NEST is false no cross-iteration aliases are considered.
If we are not processing a loop nest but scalar code we do not need to care about possible cross-iteration dependences and thus can process the full original reference. Do so, similar to how loop invariant motion applies extra offset-based disambiguation.
If we had an evolution in a MEM_REF BASE_OBJECT we do not know the size of the base-object. So we cannot do any offset/overlap based analysis but have to rely on points-to information only.
Otherwise DR_BASE_OBJECT is an access that covers the whole object that is being subsetted in the loop nest.
|
static |
Dumps the affine function described by FN to the file OUTF.
|
static |
Dumps the conflict function CF to the file OUTF.
|
static |
Dump function for a DATA_DEPENDENCE_RELATION structure.
Referenced by init_omega_for_ddr().
Dump into FILE all the dependence relations from DDRS.
Referenced by debug_data_dependence_relation().
| void dump_data_reference | ( | FILE * | outf, |
| struct data_reference * | dr | ||
| ) |
Dump function for a DATA_REFERENCE structure.
Referenced by debug_data_references().
|
static |
Dump into FILE all the data references from DATAREFS.
|
static |
Dumps the data dependence relations DDRS in FILE.
References NULL_TREE.
|
static |
Dumps the distance and direction vectors in FILE. DDRS contains the dependence relations, and VECT_SIZE is the size of the dependence vectors, or in other words the number of loops in the considered nest.
|
static |
Dump function for a SUBSCRIPT structure.
|
inlinestatic |
Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap description.
References conflict_function::fns, gcc_assert, MAX_DIM, and conflict_function::n.
Referenced by analyze_overlapping_iterations().
| tree find_data_references_in_bb | ( | struct loop * | loop, |
| basic_block | bb, | ||
| vec< data_reference_p > * | datarefs | ||
| ) |
Search the data references in LOOP, and record the information into DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise.
| tree find_data_references_in_loop | ( | struct loop * | loop, |
| vec< data_reference_p > * | datarefs | ||
| ) |
Search the data references in LOOP, and record the information into DATAREFS. Returns chrec_dont_know when failing to analyze a difficult case, returns NULL_TREE otherwise.
TODO: This function should be made smarter so that it can handle address arithmetic as if they were array accesses, etc.
| bool find_data_references_in_stmt | ( | struct loop * | nest, |
| gimple | stmt, | ||
| vec< data_reference_p > * | datarefs | ||
| ) |
Stores the data references in STMT to DATAREFS. If there is an unanalyzable reference, returns false, otherwise returns true. NEST is the outermost loop of the loop nest in which the references should be analyzed.
Referenced by create_rdg_cd_edges().
| bool find_loop_nest | ( | ) |
Return false when the LOOP is not well nested. Otherwise return true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will contain the loops from the outermost to the innermost, as they will appear in the classic distance vector.
Referenced by partition_contains_all_rw().
|
static |
Recursive helper function.
Inner loops of the nest should not contain siblings. Example: when there are two consecutive loops,
| loop_0 | loop_1 | A[{0, +, 1}_1] | endloop_1 | loop_2 | A[{0, +, 1}_2] | endloop_2 | endloop_0
the dependence relation cannot be captured by the distance abstraction.
|
static |
Frees memory used by the conflict function F.
References evolution_function_is_constant_p(), evolution_function_is_univariate_p(), and TREE_CODE.
| void free_data_ref | ( | ) |
Frees data reference DR.
| void free_data_refs | ( | ) |
Free the memory used by the data references from DATAREFS.
Referenced by cond_if_else_store_replacement_1(), stmts_from_loop(), and try_combine_chains().
| void free_dependence_relation | ( | ) |
Free the memory used by a data dependence relation DDR.
| void free_dependence_relations | ( | ) |
Free the memory used by the data dependence relations from DEPENDENCE_RELATIONS.
Referenced by try_combine_chains().
|
static |
Frees memory used by SUBSCRIPTS.
|
static |
Returns false if we can prove that the greatest common divisor of the steps of CHREC does not divide CST, false otherwise.
References chrec_contains_undetermined(), conflict_fn_not_known(), dependence_stats, dump_file, dump_flags, NULL_TREE, loop::num, datadep_stats::num_subscript_tests, datadep_stats::num_subscript_undetermined, and print_generic_expr().
|
static |
Stores the locations of memory references in STMT to REFERENCES. Returns true if STMT clobbers memory, false otherwise.
ASM_EXPR and CALL_EXPR may embed arbitrary side effects. As we cannot model data-references to not spelled out accesses give up if they may occur.
Allow IFN_GOMP_SIMD_LANE in their own loops.
| bool graphite_find_data_references_in_stmt | ( | loop_p | nest, |
| loop_p | loop, | ||
| gimple | stmt, | ||
| vec< data_reference_p > * | datarefs | ||
| ) |
Stores the data references in STMT to DATAREFS. If there is an unanalyzable reference, returns false, otherwise returns true. NEST is the outermost loop of the loop nest in which the references should be instantiated, LOOP is the loop in which the references should be analyzed.
|
static |
Initializes an equation for an OMEGA problem using the information contained in the ACCESS_FUN. Returns true when the operation succeeded.
PB is the omega constraint system. EQ is the number of the equation to be initialized. OFFSET is used for shifting the variables names in the constraints: a constrain is composed of 2 * the number of variables surrounding dependence accesses. OFFSET is set either to 0 for the first n variables, then it is set to n. ACCESS_FUN is expected to be an affine chrec.
Compute the innermost loop index.
Referenced by dir_from_dist().
|
static |
Sets up the Omega dependence problem for the data dependence relation DDR. Returns false when the constraint system cannot be built, ie. when the test answers "don't know". Returns true otherwise, and when independence has been proved (using one of the trivial dependence test), set MAYBE_DEPENDENT to false, otherwise set MAYBE_DEPENDENT to true.
Example: for setting up the dependence system corresponding to the conflicting accesses
| loop_i | loop_j | A[i, i+1] = ... | ... A[2*j, 2*(i + j)] | endloop_j | endloop_i
the following constraints come from the iteration domain:
0 <= i <= Ni 0 <= i + di <= Ni 0 <= j <= Nj 0 <= j + dj <= Nj
where di, dj are the distance variables. The constraints representing the conflicting elements are:
i = 2 * (j + dj) i + 1 = 2 * (i + di + j + dj)
For asking that the resulting distance vector (di, dj) be lexicographically positive, we insert the constraint "di >= 0". If "di = 0" in the solution, we fix that component to zero, and we look at the inner loops: we set a new problem where all the outer loop distances are zero, and fix this inner component to be positive. When one of the components is positive, we save that distance, and set a new problem where the distance on this loop is zero, searching for other distances in the inner loops. Here is the classic example that illustrates that we have to set for each inner loop a new problem:
| loop_1 | loop_2 | A[10] | endloop_2 | endloop_1
we have to save two distances (1, 0) and (0, 1).
Given two array references, refA and refB, we have to set the dependence problem twice, refA vs. refB and refB vs. refA, and we cannot do a single test, as refB might occur before refA in the inner loops, and the contrary when considering outer loops: ex.
| loop_0 | loop_1 | loop_2 | T[{1,+,1}_2][{1,+,1}_1] // refA | T[{2,+,1}_2][{0,+,1}_1] // refB | endloop_2 | endloop_1 | endloop_0
refB touches the elements in T before refA, and thus for the same loop_0 refB precedes refA: ie. the distance vector (0, 1, -1) but for successive loop_0 iterations, we have (1, -1, 1)
The Omega solver expects the distance variables ("di" in the previous example) to come first in the constraint system (as variables to be protected, or "safe" variables), the constraint system is built using the following layout:
"cst | distance vars | index vars".
Save the 0 vector.
Save the dependences carried by outer loops.
Omega expects the protected variables (those that have to be kept after elimination) to appear first in the constraint system. These variables are the distance variables. In the following initialization we declare NB_LOOPS safe variables, and the total number of variables for the constraint system is 2*NB_LOOPS.
Stop computation if not decidable, or no dependence.
References dump_data_dependence_relation(), and dump_file.
|
static |
Helper function, same as init_omega_for_ddr but specialized for data references A and B.
Insert an equality per subscript.
There is no dependence.
Insert inequalities: constraints corresponding to the iteration domain, i.e. the loops surrounding the references "loop_x" and the distance variables "dx". The layout of the OMEGA representation is as follows: - coef[0] is the constant - coef[1..nb_loops] are the protected variables that will not be removed by the solver: the "dx" - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
0 <= loop_x
0 <= loop_x + dx
loop_x <= nb_iters
loop_x + dx <= nb_iters
A step "dx" bigger than nb_iters is not feasible, so
add "0 <= nb_iters + dx", and "dx <= nb_iters".
Referenced by omega_setup_subscript().
|
read |
Initialize a data dependence relation between data accesses A and B. NB_LOOPS is the number of loops surrounding the references: the size of the classic distance/direction vectors.
If the data references do not alias, then they are independent.
The case where the references are exactly the same.
If the references do not access the same object, we do not know whether they alias or not.
If the base of the object is not invariant in the loop nest, we cannot analyze it. TODO – in fact, it would suffice to record that there may be arbitrary dependences in the loops where the base object varies.
If the number of dimensions of the access to not agree we can have a pointer access to a component of the array element type and an array access while the base-objects are still the same. Punt.
References chrec_dont_know, and DDR_ARE_DEPENDENT.
Referenced by ddr_consistent_p().
|
static |
Helper recursive function for initializing the matrix A. Returns the initial value of CHREC.
Handle ~X as -1 - X.
References chrec_dont_know, CHREC_LEFT, CHREC_RIGHT, compute_overlap_steps_for_affine_univar(), conflict_fn_not_known(), dump_file, dump_flags, get_chrec_loop(), HOST_WIDE_INT, int_cst_value(), max_stmt_executions_int(), and MIN.
|
static |
|
inlinestatic |
Returns true iff A divides B.
|
static |
Copy the elements of M x N matrix MAT1 to MAT2.
|
static |
Store the N x N identity matrix in MAT.
|
static |
Given an M x N integer matrix A, this function determines an M x M unimodular matrix U, and an M x N echelon matrix S such that "U.A = S". This decomposition is also known as "right Hermite".
Ref: Algorithm 2.1 page 33 in "Loop Transformations for Restructuring Compilers" Utpal Banerjee.
|
static |
Add a multiple of row R1 of matrix MAT with N columns to row R2: R2 = R2 + CONST1 * R1.
|
static |
Swap rows R1 and R2 in matrix MAT.
References affine_fn_cst(), chrec_dont_know, conflict_fn(), eq_evolutions_p(), HOST_WIDE_INT, integer_zero_node, and obstack.
|
static |
Negate row R1 of matrix MAT which has N columns.
|
static |
Copy the elements of vector VEC1 with length SIZE to VEC2.
|
static |
Return true if two vectors are equal.
References CHREC_RIGHT, compute_overlap_steps_for_affine_univar(), get_chrec_loop(), HOST_WIDE_INT, int_cst_value(), max_stmt_executions_int(), and MIN.
|
static |
Return the first nonzero element of vector VEC1 between START and N. We must have START <= N. Returns N if VEC1 is the zero vector.
|
static |
Multiply vector VEC1 of length SIZE by a constant CONST1, and store the result in VEC2.
|
static |
Negate vector VEC1 with length SIZE and store it in VEC2.
|
static |
Similar to max_stmt_executions_int, but returns the bound as a tree, and only if it fits to the int type. If this is not the case, or the bound on the number of iterations of LOOP could not be derived, returns chrec_dont_know.
References chrec_convert(), chrec_fold_minus(), initial_condition(), NULL, signed_type_for_types(), TREE_TYPE, and type().
|
inlinestatic |
The dependence relation DDR cannot be represented by a distance vector.
Referenced by analyze_overlapping_iterations().
|
static |
Returns true if the address of OBJ is invariant in LOOP.
Index of the ARRAY_REF was zeroed in analyze_indices, thus we only need to check the stride and the lower bound of the reference.
References build_fold_addr_expr, DR_UNCONSTRAINED_BASE, ptr_derefs_may_alias_p(), TREE_CODE, and TREE_OPERAND.
|
static |
As explained in the comments preceding init_omega_for_ddr, we have to set up a system for each loop level, setting outer loops variation to zero, and current loop variation to positive or zero. Save each lexico positive distance vector.
Set a new problem for each loop in the nest. The basis is the problem that we have initialized until now. On top of this we add new constraints.
For all the outer loops "loop_j", add "dj = 0".
For "loop_i", add "0 <= di".
Reduce the constraint system, and test that the current
problem is feasible. Reinitialize problem...
..., but this time "di = 1".
Save the lexicographically positive distance vector.
References chrec_known, and DDR_ARE_DEPENDENT.
|
static |
This is called for each subscript of a tuple of data references: insert an equality for representing the conflicts.
When the fun_a - fun_b is not constant, the dependence is not captured by the classic distance vector representation.
ZIV test.
There is no dependence.
There is probably a dependence, but the system of constraints cannot be built: answer "don't know".
GCD test.
There is no dependence.
References DDR_A, DDR_B, DDR_NB_LOOPS, dir_equal, init_omega_for_ddr_1(), lambda_vector_new(), omega_alloc_problem(), omega_free_problem(), same_access_functions(), save_dir_v(), and save_dist_v().
|
static |
Print a vector of direction vectors.
|
static |
Print the classic direction vector DIRV to OUTF.
|
static |
Print a vector of distance vectors.
|
inlinestatic |
Print out a vector VEC of length N to OUTFILE.
Referenced by debug_data_dependence_relations().
|
static |
Helper function for uniquely inserting direction vectors.
References DDR_AFFINE_P.
Referenced by omega_setup_subscript().
|
static |
Helper function for uniquely inserting distance vectors.
Referenced by add_multivariate_self_dist(), and omega_setup_subscript().
|
static |
Returns a signed integer type with the largest precision from TA and TB.
Referenced by max_stmt_executions_tree().
|
static |
Returns true iff CHREC_A and CHREC_B are dependent on an index variable, i.e., if the SIV (Single Index Variable) test is true.
| void split_constant_offset | ( | ) |
Expresses EXP as VAR + OFF, where off is a constant. The type of OFF will be ssizetype.
References build_fold_addr_expr, POINTER_TYPE_P, STRIP_NOPS, TREE_CODE, TREE_OPERAND, and TREE_TYPE.
Referenced by debug_ddrs().
|
static |
Helper function for split_constant_offset. Expresses OP0 CODE OP1 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero constant of type ssizetype, and returns true. If we cannot do this with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false is returned.
FALLTHROUGH
If variable length types are involved, punt, otherwise casts
might be converted into ARRAY_REFs in gimplify_conversion.
To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
possibly no longer appears in current GIMPLE, might resurface.
This perhaps could run
if (CONVERT_EXPR_P (var0))
{
gimplify_conversion (&var0);
Attempt to fill in any within var0 found ARRAY_REF's element size from corresponding op embedded ARRAY_REF, if unsuccessful, just punt. }
We must not introduce undefined overflow, and we must not change the value.
Hence we're okay if the inner type doesn't overflow to start with
(pointer or signed), the outer type also is an integer or pointer
and the outer precision is at least as large as the inner.
|
static |
Computes the conflicting iterations in LOOP_NEST, and initialize DDR.
|
static |
Helper function. Returns true when there is a dependence between data references DRA and DRB.
If there is any undetermined conflict function we have to give a conservative answer in case we cannot prove that no dependence exists when analyzing another subscript.
When there is a subscript with no dependence we can stop.
References eqn_d::coef, copy(), DDR_LOOP_NEST, DDR_NB_LOOPS, omega_pb_d::eqs, omega_pb_d::geqs, eqn_d::key, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_add_zero_eq(), omega_add_zero_geq(), omega_alloc_problem(), omega_black, omega_copy_problem(), omega_false, omega_simplify_problem(), omega_unknown, and omega_pb_d::subs.
| void tree_check_data_deps | ( | void | ) |
Computes all the data dependences and check that the results of several analyzers are the same.
Referenced by make_pass_vectorize().
|
inlinestatic |
Returns true iff A divides B.
|
inlinestatic |
This section contains the classic Banerjee tests. Returns true iff CHREC_A and CHREC_B are not dependent on any index variables, i.e., if the ZIV (Zero Index Variable) test is true.
References gcc_assert, and integer_zero_node.
Variable Documentation
|
static |
Referenced by analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), and gcd_of_steps_may_divide_p().
