Clan
0.8.0
|
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <osl/macros.h>
#include <osl/int.h>
#include <osl/relation.h>
#include <clan/macros.h>
#include <clan/options.h>
#include <clan/relation.h>
Go to the source code of this file.
Functions | |
int | clan_parser_nb_ld (void) |
void | clan_parser_add_ld (void) |
void | clan_relation_tag_array (osl_relation_p relation, int array) |
osl_relation_p | clan_relation_build_context (int nb_parameters, clan_options_p options) |
osl_relation_p | clan_relation_scattering (int *vector, int depth, int precision) |
void | clan_relation_new_output_vector (osl_relation_p relation, osl_vector_p vector) |
void | clan_relation_new_output_scalar (osl_relation_p relation, int scalar) |
void | clan_relation_compact (osl_relation_p relation, int nb_parameters) |
osl_relation_p | clan_relation_greater (osl_relation_p min, osl_relation_p max, int strict) |
static void | clan_relation_negate_inequality (osl_relation_p relation, int row) |
static osl_relation_p | clan_relation_extract_constraint (osl_relation_p relation, int row) |
static int | clan_relation_is_equality (osl_relation_p relation, int row) |
static void | clan_relation_tag_inequality (osl_relation_p relation, int row) |
static void | clan_relation_tag_equality (osl_relation_p relation, int row) |
static osl_relation_p | clan_relation_constraint_not (osl_relation_p relation, int row) |
osl_relation_p | clan_relation_not (osl_relation_p relation) |
void | clan_relation_and (osl_relation_p dest, osl_relation_p src) |
int | clan_relation_existential (osl_relation_p relation) |
void | clan_relation_oppose_row (osl_relation_p r, int row) |
static void | clan_relation_extract_bounding (osl_relation_p r, osl_relation_p *bound, osl_relation_p *notbound, int depth, int lower) |
static void | clan_relation_to_expressions (osl_relation_p r, int depth) |
osl_relation_p | clan_relation_stride (osl_relation_p r, int depth, int stride) |
static void | clan_relation_gaussian_elimination (osl_relation_p relation, int pivot_row, int pivot_column) |
static void | clan_relation_simplify_parts (osl_relation_p relation) |
void | clan_relation_simplify (osl_relation_p relation) |
void | clan_relation_loop_context (osl_relation_p condition, osl_relation_p initialization, int depth) |
void clan_parser_add_ld | ( | void | ) |
Definition at line 4555 of file parser.c.
References CLAN_DEBUG, CLAN_debug, CLAN_error, CLAN_MAX_LOCAL_DIMS, clan_parser_nb_ld(), parser_if_depth, parser_loop_depth, and parser_nb_local_dims.
Referenced by clan_relation_stride(), and yyparse().
int clan_parser_nb_ld | ( | void | ) |
Definition at line 4571 of file parser.c.
References parser_if_depth, parser_loop_depth, and parser_nb_local_dims.
Referenced by clan_parser_add_ld(), clan_relation_stride(), and yyparse().
void clan_relation_and | ( | osl_relation_p | dest, |
osl_relation_p | src | ||
) |
clan_relation_and function: this function inserts the src constraints rows into every parts of dest. If src is an union, the function creates exactly the right number of new unions.
dest | modified relation which contains the result. |
src | relation to be inserted. |
Definition at line 580 of file relation.c.
Referenced by clan_relation_not(), clan_relation_stride(), and yyparse().
osl_relation_p clan_relation_build_context | ( | int | nb_parameters, |
clan_options_p | options | ||
) | [read] |
clan_relation_build_context function: this function builds a context relation with 'nb_parameters' parameters. Depending on the bounded_context option, the context has no contraint or each parameter is set to be >= -1.
[in] | nb_parameters | The number of parameters for the context. |
[in] | options | The global options of Clan. |
Definition at line 93 of file relation.c.
References clan_options::bounded_context, and clan_options::precision.
Referenced by yyparse().
void clan_relation_compact | ( | osl_relation_p | relation, |
int | nb_parameters | ||
) |
clan_relation_compact function: This function compacts a relation such that it uses the right number of columns (during construction we used CLAN_MAX_DEPTH, CLAN_MAX_LOCAL_DIMS and CLAN_MAX_PARAMETERS to define relation and vector sizes). It modifies directly the relation provided as parameter.
[in,out] | relation | The relation to compact. |
[in] | nb_parameters | The true number of parameters in the SCoP. |
Definition at line 253 of file relation.c.
References CLAN_MAX_DEPTH, and CLAN_MAX_PARAMETERS.
Referenced by clan_relation_list_compact(), and clan_statement_compact().
static osl_relation_p clan_relation_constraint_not | ( | osl_relation_p | relation, |
int | row | ||
) | [static] |
clan_relation_constraint_not function: this function returns the negative form of one constraint in a relation (seen as a constraint set).
[in] | relation | The relation set where is the constraint to negate. |
[in] | row | The row number of the constraint to negate. |
Definition at line 508 of file relation.c.
References clan_relation_extract_constraint(), clan_relation_is_equality(), clan_relation_negate_inequality(), and clan_relation_tag_inequality().
Referenced by clan_relation_not().
int clan_relation_existential | ( | osl_relation_p | relation | ) |
clan_relation_existential function: this function returns 1 if the relation involves an existential quantifier (its coefficient is not zero), 0 otherwise.
[in] | relation | The relation to check. |
Definition at line 621 of file relation.c.
References CLAN_MAX_DEPTH, and CLAN_MAX_LOCAL_DIMS.
Referenced by yyparse().
static void clan_relation_extract_bounding | ( | osl_relation_p | r, |
osl_relation_p * | bound, | ||
osl_relation_p * | notbound, | ||
int | depth, | ||
int | lower | ||
) | [static] |
clan_relation_extract_bounding function: this function separates the constraints of a given relation part (not an union) into two constraints sets: one which contains the constraints contributing to one bound of the loop iterator at a given depth and another one which contains all the remaining constraints. Equalities contributing to the bound are separated into two inequalities.
[in] | r | The constraint set to separate. |
[out] | bound | The constraints contributing to the bound (output). |
[out] | notbound | The constraints not contributing to the bound (output). |
[in] | depth | The loop depth of the bound. |
[in] | lower | 1 for the lower bound, 0 for the upper bound. |
Definition at line 676 of file relation.c.
References CLAN_error, CLAN_MAX_DEPTH, clan_relation_extract_constraint(), and clan_relation_oppose_row().
Referenced by clan_relation_stride().
static osl_relation_p clan_relation_extract_constraint | ( | osl_relation_p | relation, |
int | row | ||
) | [static] |
clan_relation_extract_constraint function: this function creates and returns a new relation from a single constraint of a relation. The constraint corresponds to a specified row of the constraint matrix of the first element of the specified relation union.
[in] | relation | The input relation. |
[in] | row | The row corresponding to the constraint to extract. |
Definition at line 430 of file relation.c.
Referenced by clan_relation_constraint_not(), clan_relation_extract_bounding(), and clan_relation_stride().
static void clan_relation_gaussian_elimination | ( | osl_relation_p | relation, |
int | pivot_row, | ||
int | pivot_column | ||
) | [static] |
clan_relation_gaussian_elimination function: this function eliminates the coefficients of a given column (pivot_column) of a relation matrix using a given pivot (the pivot itself is not eliminated). This function updates the relation directly. The correct elimination of columns elements (except the pivot) is guaranteed only if the pivot row corresponds to an equality. Otherwise, this fuction will do its best to eliminate the other columns elements, but the resulting relation will not be equivalent to the input.
[in,out] | relation | Relation where to eliminate a column (modified). |
[in] | pivot_row | Row coordinate of the pivot. |
[in] | pivot_column | Column coordinate of the pivot. |
Definition at line 914 of file relation.c.
Referenced by clan_relation_loop_context(), and clan_relation_simplify().
osl_relation_p clan_relation_greater | ( | osl_relation_p | min, |
osl_relation_p | max, | ||
int | strict | ||
) |
clan_relation_greater function: this function generates a relation corresponding to the equivalent constraint set of two linear expressions sets involved in a condition "greater (or equal) to". min and max are two linear expression sets, e.g. (a, b, c) for min and (d, e) for max, where a, b, c, d and e are linear expressions. This function creates the constraint set corresponding to, e.g., min(a, b, c) > max(d, e), i.e.: (a > d && a > e && b > d && b > e && c > d && c > e). It may also create the constraint set corresponding to min(a, b, c) >= max(d, e). The relations max and min are not using the OpenScop/PolyLib format: each row corresponds to a linear expression as usual but the first element is not devoted to the equality/inequality marker but to store the value of the ceild or floord divisor. Hence, each row may correspond to a ceil of a linear expression divided by an integer in min or to a floor of a linear expression divided by an integer in max.
[in] | min | Set of (ceild) linear expressions corresponding to the minimum of the (ceild) linear expressions. |
[in] | max | Set of (floord) linear expressions corresponding to the maximum of the (floord) linear expressions. |
[in] | strict | 1 if the condition is min > max, 0 if it is min >= max. |
Definition at line 332 of file relation.c.
References CLAN_error.
Referenced by clan_relation_stride(), and yyparse().
static int clan_relation_is_equality | ( | osl_relation_p | relation, |
int | row | ||
) | [static] |
clan_relation_is_equality function: this function returns 1 if a given row of a given relation corresponds to an equality constraint, 0 otherwise (which means it corresponds to an inequality constraint).
[in] | relation | The input relation. |
[in] | row | The row corresponding to the constraint to check. |
Definition at line 459 of file relation.c.
Referenced by clan_relation_constraint_not().
void clan_relation_loop_context | ( | osl_relation_p | condition, |
osl_relation_p | initialization, | ||
int | depth | ||
) |
clan_relation_loop_context function: this function adds the constraints to ensure that the loop iterator initial value respects the loop condition. This set of constraints is called the "loop context". Without such a context, a loop like the following: for (i = 0; i > 2; i++) would just translate to the constraints i >= 0 && i > 2 which is obviously wrong. Hence this function computes the set of constraints of the loop condition with respect to the initial value (in our example this would be 0 > 2) and adds it to the loop condition constraints. This function modifies the loop condition provided as input.
[in,out] | condition | The set of constraints corresponding to the loop condition (updated). |
[in] | initialization | Lower bound constraints. |
[in] | depth | Current loop depth. |
Definition at line 1162 of file relation.c.
References clan_relation_gaussian_elimination(), and clan_relation_tag_equality().
Referenced by yyparse().
static void clan_relation_negate_inequality | ( | osl_relation_p | relation, |
int | row | ||
) | [static] |
clan_relation_negate_inequality function: this function replaces an inequality constraint in a relation with its negation (e.g., i >= 0 will become i < 0). Note that it does not check that the constraint is actually an inequality.
[in,out] | relation | The relation where to oppose a constraint. |
[in] | row | The row corresponding to the constraint to oppose. |
Definition at line 405 of file relation.c.
Referenced by clan_relation_constraint_not().
void clan_relation_new_output_scalar | ( | osl_relation_p | relation, |
int | scalar | ||
) |
clan_relation_new_output_scalar function: this function adds a new output dimension and a new constraint corresponding to the new output dimension to an existing relation. The new output dimension is added after the existing output dimensions. It is supposed to be equal to a scalar value passed as an argument. The input relation is direcly updated.
[in,out] | relation | The relation to add a new output dimension. |
[in] | scalar | The scalar the new output dimension is equal to. |
Definition at line 220 of file relation.c.
References CLAN_error.
Referenced by yyparse().
void clan_relation_new_output_vector | ( | osl_relation_p | relation, |
osl_vector_p | vector | ||
) |
clan_relation_new_output_vector function: this function adds a new output dimension and a new constraint corresponding to the new output dimension to an existing relation. The new output dimension is added after the existing output dimensions. It is supposed to be equal to the vector expression passed as an argument. The input relation is direcly updated.
[in,out] | relation | The relation to add a new output dimension. |
[in] | vector | The expression the new output dimension is equal to. |
Definition at line 175 of file relation.c.
References CLAN_error.
Referenced by yyparse().
osl_relation_p clan_relation_not | ( | osl_relation_p | relation | ) |
clan_relation_not function: this function returns the negative form of a relation (union).
relation | The relation to oppose. |
Definition at line 545 of file relation.c.
References clan_relation_and(), and clan_relation_constraint_not().
Referenced by yyparse().
void clan_relation_oppose_row | ( | osl_relation_p | r, |
int | row | ||
) |
clan_relation_oppose_row function: this function multiplies by -1 every element (except the equality/inequality marker) of a given row in a given relation part.
[in,out] | r | The relation to oppose a row. |
[in] | row | The row number to oppose. |
Definition at line 647 of file relation.c.
References CLAN_error.
Referenced by clan_relation_extract_bounding(), clan_relation_stride(), and clan_relation_to_expressions().
osl_relation_p clan_relation_scattering | ( | int * | vector, |
int | depth, | ||
int | precision | ||
) | [read] |
clan_relation_scattering function: this function builds the scattering relation for the clan_statement_t structures thanks to the parser current state of parser_scattering (rank) and parser_depth (depth). The input scattering vector has 2depth+1 elements. Each even element gives the "position" of the statement for every loop depth (see Feautrier's demonstration of existence of a schedule for any SCoP or CLooG's manual for original scattering function to understand if necessary). Each This function just "expands" this vector to a (2*n+1)-dimensional schedule for a statement at depth n and returns it. Each odd element gives the loop direction: 1 for forward (meaning the loop stride is positive) -1 for backward (the loop stride is negative).
[in] | vector | The statement position / loop direction vector. |
[in] | depth | The depth of the statement. |
[in] | precision | The precision of the relation elements. |
Definition at line 133 of file relation.c.
References CLAN_MAX_PARAMETERS.
Referenced by yyparse().
void clan_relation_simplify | ( | osl_relation_p | relation | ) |
clan_relation_simplify function: this function removes some duplicated constraints in a lazy way: there is no guarantee that it will remove duplicated constraints, it will just try and remove trivial duplicates. Hey, no polyhedral library there, so this is just trivial stuff.
[in,out] | relation | The relation to simplify (modified). |
Definition at line 1054 of file relation.c.
References clan_relation_gaussian_elimination(), and clan_relation_simplify_parts().
Referenced by clan_scop_simplify().
static void clan_relation_simplify_parts | ( | osl_relation_p | relation | ) | [static] |
clan_relation_simplify_parts function: this function removes some duplicated union parts in a lazy way: there is no guarantee that it will remove duplicated constraints, it will just try and remove trivial duplicates.
[in,out] | relation | The relation to simplify (modified). |
Definition at line 1024 of file relation.c.
Referenced by clan_relation_simplify().
osl_relation_p clan_relation_stride | ( | osl_relation_p | r, |
int | depth, | ||
int | stride | ||
) |
clan_relation_stride function: this function computes and returns a relation built from an input relation modified by the contribution of a loop stride at a given depth. Basically, the input relation corresponds to an iteration domain with a loop stride of 1 for the input depth. It returns the new iteration domain when we take into account a non-unit stride at this depth.
[in] | r | The relation without the stride. |
[in] | depth | The depth of the strided loop to take into account. |
[in] | stride | The loop stride value. |
Definition at line 788 of file relation.c.
References CLAN_error, CLAN_MAX_DEPTH, clan_parser_add_ld(), clan_parser_nb_ld(), clan_relation_and(), clan_relation_extract_bounding(), clan_relation_extract_constraint(), clan_relation_greater(), clan_relation_oppose_row(), and clan_relation_to_expressions().
Referenced by yyparse().
void clan_relation_tag_array | ( | osl_relation_p | relation, |
int | array | ||
) |
clan_relation_tag_array function: this function tags a relation to explicit it is describing the array index of a given array. This means using OpenScop representation that the very first output dimension will correspond to the constraint dim = array_id. It updates directly the relation provided as parameter. A new row and a new column are inserted to the existing relation and the number of output dimensions is incremented.
[in,out] | relation | The relation to tag. |
[in] | array | The array number. |
Definition at line 71 of file relation.c.
References CLAN_error.
Referenced by yyparse().
static void clan_relation_tag_equality | ( | osl_relation_p | relation, |
int | row | ||
) | [static] |
clan_relation_tag_equality function: this function tags a given constraint of a given relation as being an equality == 0. This means in the PolyLib format, to set to 0 the very first entry of the constraint row. It modifies directly the relation provided as an argument.
relation | The relation which includes a constraint to be tagged. |
row | The row corresponding to the constraint to tag. |
Definition at line 492 of file relation.c.
References CLAN_error.
Referenced by clan_relation_loop_context().
static void clan_relation_tag_inequality | ( | osl_relation_p | relation, |
int | row | ||
) | [static] |
clan_relation_tag_inequality function: this function tags a given constraint of a given relation as being an inequality >=0. This means in the PolyLib format, to set to 1 the very first entry of the constraint row. It modifies directly the relation provided as an argument.
relation | The relation which includes a constraint to be tagged. |
row | The row corresponding to the constraint to tag. |
Definition at line 475 of file relation.c.
References CLAN_error.
Referenced by clan_relation_constraint_not().
static void clan_relation_to_expressions | ( | osl_relation_p | r, |
int | depth | ||
) | [static] |
clan_relation_to_expressions function: this function translates a set of inequalities involving the coefficient of the loop iterator at depth "depth" to a set of expressions which would compare to the iterator alone, hence not involving the loop iterator anymore. E.g., an inequality "j - i + 3 >= 0" for iterator "j" will be converted to "i - 3" (j >= i - 3) and "-j - i + 3 >= 0" will be converted to "-i + 3" (j <= -i + 3). If the coefficient of the iterator is not +/-1, it is stored in the equality/inequality marker.
[in] | r | The inequality set to convert (not an union). |
[in] | depth | Loop depth of the iterator to remove. |
Definition at line 754 of file relation.c.
References CLAN_error, and clan_relation_oppose_row().
Referenced by clan_relation_stride().