Clan  0.8.0
Functions
relation.c File Reference
#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>
Include dependency graph for relation.c:

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)

Function Documentation

void clan_parser_add_ld ( void  )
int clan_parser_nb_ld ( void  )
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.

Parameters:
destmodified relation which contains the result.
srcrelation 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.

Parameters:
[in]nb_parametersThe number of parameters for the context.
[in]optionsThe global options of Clan.
Returns:
A context relation with 'nb_parameters' parameters.

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.

Parameters:
[in,out]relationThe relation to compact.
[in]nb_parametersThe 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).

Parameters:
[in]relationThe relation set where is the constraint to negate.
[in]rowThe row number of the constraint to negate.
Returns:
A new relation containing the negation of the constraint.

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.

Parameters:
[in]relationThe relation to check.
Returns:
1 if the relation uses an existential quantifier, 0 otherwise.

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.

Parameters:
[in]rThe constraint set to separate.
[out]boundThe constraints contributing to the bound (output).
[out]notboundThe constraints not contributing to the bound (output).
[in]depthThe loop depth of the bound.
[in]lower1 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.

Parameters:
[in]relationThe input relation.
[in]rowThe row corresponding to the constraint to extract.
Returns:
A new relation with the extracted constraint only.

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.

Parameters:
[in,out]relationRelation where to eliminate a column (modified).
[in]pivot_rowRow coordinate of the pivot.
[in]pivot_columnColumn 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.

Parameters:
[in]minSet of (ceild) linear expressions corresponding to the minimum of the (ceild) linear expressions.
[in]maxSet of (floord) linear expressions corresponding to the maximum of the (floord) linear expressions.
[in]strict1 if the condition is min > max, 0 if it is min >= max.
Returns:
A set of linear constraints corresponding to min > (or >=) 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).

Parameters:
[in]relationThe input relation.
[in]rowThe row corresponding to the constraint to check.
Returns:
1 if the constraint is an equality, 0 if it is an inequality.

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.

Parameters:
[in,out]conditionThe set of constraints corresponding to the loop condition (updated).
[in]initializationLower bound constraints.
[in]depthCurrent 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.

Parameters:
[in,out]relationThe relation where to oppose a constraint.
[in]rowThe 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.

Parameters:
[in,out]relationThe relation to add a new output dimension.
[in]scalarThe 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.

Parameters:
[in,out]relationThe relation to add a new output dimension.
[in]vectorThe 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).

Parameters:
relationThe relation to oppose.
Returns:
A new relation corresponding to the negative form of the input.

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.

Parameters:
[in,out]rThe relation to oppose a row.
[in]rowThe 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).

Parameters:
[in]vectorThe statement position / loop direction vector.
[in]depthThe depth of the statement.
[in]precisionThe 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.

Parameters:
[in,out]relationThe 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.

Parameters:
[in,out]relationThe 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.

Parameters:
[in]rThe relation without the stride.
[in]depthThe depth of the strided loop to take into account.
[in]strideThe 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.

Parameters:
[in,out]relationThe relation to tag.
[in]arrayThe 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.

Parameters:
relationThe relation which includes a constraint to be tagged.
rowThe 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.

Parameters:
relationThe relation which includes a constraint to be tagged.
rowThe 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.

Parameters:
[in]rThe inequality set to convert (not an union).
[in]depthLoop 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().