GCC Middle and Back End API Reference

Data Structures  
struct  datadep_stats 
struct  data_ref_loc_d 
Typedefs  
typedef struct data_ref_loc_d  data_ref_loc 
Variables  
static struct datadep_stats  dependence_stats 
typedef struct data_ref_loc_d data_ref_loc 
Describes a location of a memory reference.

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 pr346351.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(), and max_stmt_executions().

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/.../ssachrec33.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/.../ssachrec35.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, and datadep_stats::num_same_subscript_function.

static 
@verbatim
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, 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(), non_affine_dependence_relation(), operand_equal_p(), and SUB_DISTANCE.

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 weakzero 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 weakzero 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, 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 "gcdtest".
The "gcdtest" 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().

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(), 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][i1]; // 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][i1]; // 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 
@verbatim
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.
TODO  If the test is after the exit, we may decrease the number of iterations by one.
References affine_fn_cst(), and conflict_fn().
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().
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 readread 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 readread 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 readread 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(), and loop::num.

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(), 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, and initialize_data_dependence_relation().
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(), and split_constant_offset().

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 basicblock 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 accessfunction.
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 bandaid, mark the access so we can specialcase it in dr_may_alias_p.
Canonicalize DR_BASE_OBJECT to MEM_REF form.
References analyze_scalar_evolution(), component_ref_field_offset(), and instantiate_scev().
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 datarefs) 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 crossiteration aliases are considered.
If we are not processing a loop nest but scalar code we do not need to care about possible crossiteration dependences and thus can process the full original reference. Do so, similar to how loop invariant motion applies extra offsetbased disambiguation.
If we had an evolution in a MEM_REF BASE_OBJECT we do not know the size of the baseobject. So we cannot do any offset/overlap based analysis but have to rely on pointsto information only.
Otherwise DR_BASE_OBJECT is an access that covers the whole object that is being subsetted in the loop nest.
Referenced by build_poly_dr().

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.

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, 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(), and evolution_function_is_univariate_p().
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, 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 datareferences 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.
Referenced by graphite_can_represent_expr().

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 
@verbatim
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 baseobjects 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, compute_overlap_steps_for_affine_univar(), conflict_fn_not_known(), dump_file, dump_flags, get_chrec_loop(), HOST_WIDE_INT, int_cst_value(), and max_stmt_executions_int().

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, 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 compute_overlap_steps_for_affine_univar(), get_chrec_loop(), HOST_WIDE_INT, int_cst_value(), and max_stmt_executions_int().

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(), signed_type_for_types(), 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 DR_UNCONSTRAINED_BASE, and ptr_derefs_may_alias_p().

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.
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.

static 
Referenced by analyze_miv_subscript(), analyze_siv_subscript_cst_affine(), and gcd_of_steps_may_divide_p().