/* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2010 INRIA Saclay * Copyright 2014 Ecole Normale Superieure * Copyright 2017 Sven Verdoolaege * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, K.U.Leuven, Departement * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France */ #include <isl_ctx_private.h> #include <isl_map_private.h> #include <isl/space.h> #include <isl_seq.h> #include <isl_mat_private.h> #include <isl_vec_private.h> #include <isl_space_private.h> #include <isl_val_private.h> isl_ctx *isl_mat_get_ctx(__isl_keep isl_mat *mat) { … } /* Return a hash value that digests "mat". */ uint32_t isl_mat_get_hash(__isl_keep isl_mat *mat) { … } __isl_give isl_mat *isl_mat_alloc(isl_ctx *ctx, unsigned n_row, unsigned n_col) { … } __isl_give isl_mat *isl_mat_extend(__isl_take isl_mat *mat, unsigned n_row, unsigned n_col) { … } __isl_give isl_mat *isl_mat_sub_alloc6(isl_ctx *ctx, isl_int **row, unsigned first_row, unsigned n_row, unsigned first_col, unsigned n_col) { … } __isl_give isl_mat *isl_mat_sub_alloc(__isl_keep isl_mat *mat, unsigned first_row, unsigned n_row, unsigned first_col, unsigned n_col) { … } void isl_mat_sub_copy(struct isl_ctx *ctx, isl_int **dst, isl_int **src, unsigned n_row, unsigned dst_col, unsigned src_col, unsigned n_col) { … } void isl_mat_sub_neg(struct isl_ctx *ctx, isl_int **dst, isl_int **src, unsigned n_row, unsigned dst_col, unsigned src_col, unsigned n_col) { … } __isl_give isl_mat *isl_mat_copy(__isl_keep isl_mat *mat) { … } __isl_give isl_mat *isl_mat_dup(__isl_keep isl_mat *mat) { … } __isl_give isl_mat *isl_mat_cow(__isl_take isl_mat *mat) { … } __isl_null isl_mat *isl_mat_free(__isl_take isl_mat *mat) { … } isl_size isl_mat_rows(__isl_keep isl_mat *mat) { … } isl_size isl_mat_cols(__isl_keep isl_mat *mat) { … } /* Check that "col" is a valid column position for "mat". */ static isl_stat check_col(__isl_keep isl_mat *mat, int col) { … } /* Check that "row" is a valid row position for "mat". */ static isl_stat check_row(__isl_keep isl_mat *mat, int row) { … } /* Check that there are "n" columns starting at position "first" in "mat". */ static isl_stat check_col_range(__isl_keep isl_mat *mat, unsigned first, unsigned n) { … } /* Check that there are "n" rows starting at position "first" in "mat". */ static isl_stat check_row_range(__isl_keep isl_mat *mat, unsigned first, unsigned n) { … } int isl_mat_get_element(__isl_keep isl_mat *mat, int row, int col, isl_int *v) { … } /* Extract the element at row "row", oolumn "col" of "mat". */ __isl_give isl_val *isl_mat_get_element_val(__isl_keep isl_mat *mat, int row, int col) { … } __isl_give isl_mat *isl_mat_set_element(__isl_take isl_mat *mat, int row, int col, isl_int v) { … } __isl_give isl_mat *isl_mat_set_element_si(__isl_take isl_mat *mat, int row, int col, int v) { … } /* Replace the element at row "row", column "col" of "mat" by "v". */ __isl_give isl_mat *isl_mat_set_element_val(__isl_take isl_mat *mat, int row, int col, __isl_take isl_val *v) { … } __isl_give isl_mat *isl_mat_diag(isl_ctx *ctx, unsigned n_row, isl_int d) { … } /* Create an "n_row" by "n_col" matrix with zero elements. */ __isl_give isl_mat *isl_mat_zero(isl_ctx *ctx, unsigned n_row, unsigned n_col) { … } __isl_give isl_mat *isl_mat_identity(isl_ctx *ctx, unsigned n_row) { … } /* Is "mat" a (possibly scaled) identity matrix? */ isl_bool isl_mat_is_scaled_identity(__isl_keep isl_mat *mat) { … } __isl_give isl_vec *isl_mat_vec_product(__isl_take isl_mat *mat, __isl_take isl_vec *vec) { … } __isl_give isl_vec *isl_mat_vec_inverse_product(__isl_take isl_mat *mat, __isl_take isl_vec *vec) { … } __isl_give isl_vec *isl_vec_mat_product(__isl_take isl_vec *vec, __isl_take isl_mat *mat) { … } __isl_give isl_mat *isl_mat_aff_direct_sum(__isl_take isl_mat *left, __isl_take isl_mat *right) { … } static void exchange(__isl_keep isl_mat *M, __isl_keep isl_mat **U, __isl_keep isl_mat **Q, unsigned row, unsigned i, unsigned j) { … } static void subtract(__isl_keep isl_mat *M, __isl_keep isl_mat **U, __isl_keep isl_mat **Q, unsigned row, unsigned i, unsigned j, isl_int m) { … } static void oppose(__isl_keep isl_mat *M, __isl_keep isl_mat **U, __isl_keep isl_mat **Q, unsigned row, unsigned col) { … } /* Given matrix M, compute * * M U = H * M = H Q * * with U and Q unimodular matrices and H a matrix in column echelon form * such that on each echelon row the entries in the non-echelon column * are non-negative (if neg == 0) or non-positive (if neg == 1) * and strictly smaller (in absolute value) than the entries in the echelon * column. * If U or Q are NULL, then these matrices are not computed. */ __isl_give isl_mat *isl_mat_left_hermite(__isl_take isl_mat *M, int neg, __isl_give isl_mat **U, __isl_give isl_mat **Q) { … } /* Use row "row" of "mat" to eliminate column "col" from all other rows. */ static __isl_give isl_mat *eliminate(__isl_take isl_mat *mat, int row, int col) { … } /* Perform Gaussian elimination on the rows of "mat", but start * from the final row and the final column. * Any zero rows that result from the elimination are removed. * * In particular, for each column from last to first, * look for the last row with a non-zero coefficient in that column, * move it last (but before other rows moved last in previous steps) and * use it to eliminate the column from the other rows. */ __isl_give isl_mat *isl_mat_reverse_gauss(__isl_take isl_mat *mat) { … } /* Negate the lexicographically negative rows of "mat" such that * all rows in the result are lexicographically non-negative. */ __isl_give isl_mat *isl_mat_lexnonneg_rows(__isl_take isl_mat *mat) { … } /* Given a matrix "H" is column echelon form, what is the first * zero column? That is how many initial columns are non-zero? * Start looking at column "first_col" and only consider * the columns to be of size "n_row". * "H" is assumed to be non-NULL. * * Since "H" is in column echelon form, the first non-zero entry * in a column is always in a later position compared to the previous column. */ static int hermite_first_zero_col(__isl_keep isl_mat *H, int first_col, int n_row) { … } /* Return the rank of "mat", or isl_size_error in case of error. */ isl_size isl_mat_rank(__isl_keep isl_mat *mat) { … } __isl_give isl_mat *isl_mat_right_kernel(__isl_take isl_mat *mat) { … } __isl_give isl_mat *isl_mat_lin_to_aff(__isl_take isl_mat *mat) { … } /* Given two matrices M1 and M2, return the block matrix * * [ M1 0 ] * [ 0 M2 ] */ __isl_give isl_mat *isl_mat_diagonal(__isl_take isl_mat *mat1, __isl_take isl_mat *mat2) { … } static int row_first_non_zero(isl_int **row, unsigned n_row, unsigned col) { … } static int row_abs_min_non_zero(isl_int **row, unsigned n_row, unsigned col) { … } static isl_stat inv_exchange(__isl_keep isl_mat **left, __isl_keep isl_mat **right, unsigned i, unsigned j) { … } static void inv_oppose( __isl_keep isl_mat *left, __isl_keep isl_mat *right, unsigned row) { … } static void inv_subtract(__isl_keep isl_mat *left, __isl_keep isl_mat *right, unsigned row, unsigned i, isl_int m) { … } /* Compute inv(left)*right */ __isl_give isl_mat *isl_mat_inverse_product(__isl_take isl_mat *left, __isl_take isl_mat *right) { … } void isl_mat_col_scale(__isl_keep isl_mat *mat, unsigned col, isl_int m) { … } void isl_mat_col_combine(__isl_keep isl_mat *mat, unsigned dst, isl_int m1, unsigned src1, isl_int m2, unsigned src2) { … } __isl_give isl_mat *isl_mat_right_inverse(__isl_take isl_mat *mat) { … } __isl_give isl_mat *isl_mat_transpose(__isl_take isl_mat *mat) { … } __isl_give isl_mat *isl_mat_swap_cols(__isl_take isl_mat *mat, unsigned i, unsigned j) { … } __isl_give isl_mat *isl_mat_swap_rows(__isl_take isl_mat *mat, unsigned i, unsigned j) { … } /* Calculate the product of two matrices. * * This function is optimized for operand matrices that contain many zeros and * skips multiplications where we know one of the operands is zero. */ __isl_give isl_mat *isl_mat_product(__isl_take isl_mat *left, __isl_take isl_mat *right) { … } /* Replace the variables x in the rows q by x' given by x = M x', * with M the matrix mat. * * If the number of new variables is greater than the original * number of variables, then the rows q have already been * preextended. If the new number is smaller, then the coefficients * of the divs, which are not changed, need to be shifted down. * The row q may be the equalities, the inequalities or the * div expressions. In the latter case, has_div is true and * we need to take into account the extra denominator column. */ static int preimage(struct isl_ctx *ctx, isl_int **q, unsigned n, unsigned n_div, int has_div, struct isl_mat *mat) { … } /* Replace the variables x in bset by x' given by x = M x', with * M the matrix mat. * * If there are fewer variables x' then there are x, then we perform * the transformation in place, which means that, in principle, * this frees up some extra variables as the number * of columns remains constant, but we would have to extend * the div array too as the number of rows in this array is assumed * to be equal to extra. */ __isl_give isl_basic_set *isl_basic_set_preimage( __isl_take isl_basic_set *bset, __isl_take isl_mat *mat) { … } __isl_give isl_set *isl_set_preimage( __isl_take isl_set *set, __isl_take isl_mat *mat) { … } /* Replace the variables x starting at "first_col" in the rows "rows" * of some coefficient matrix by x' with x = M x' with M the matrix mat. * That is, replace the corresponding coefficients c by c M. */ isl_stat isl_mat_sub_transform(isl_int **row, unsigned n_row, unsigned first_col, __isl_take isl_mat *mat) { … } void isl_mat_print_internal(__isl_keep isl_mat *mat, FILE *out, int indent) { … } void isl_mat_dump(__isl_keep isl_mat *mat) { … } __isl_give isl_mat *isl_mat_drop_cols(__isl_take isl_mat *mat, unsigned col, unsigned n) { … } __isl_give isl_mat *isl_mat_drop_rows(__isl_take isl_mat *mat, unsigned row, unsigned n) { … } __isl_give isl_mat *isl_mat_insert_cols(__isl_take isl_mat *mat, unsigned col, unsigned n) { … } __isl_give isl_mat *isl_mat_insert_zero_cols(__isl_take isl_mat *mat, unsigned first, unsigned n) { … } __isl_give isl_mat *isl_mat_add_zero_cols(__isl_take isl_mat *mat, unsigned n) { … } __isl_give isl_mat *isl_mat_insert_rows(__isl_take isl_mat *mat, unsigned row, unsigned n) { … } __isl_give isl_mat *isl_mat_add_rows(__isl_take isl_mat *mat, unsigned n) { … } __isl_give isl_mat *isl_mat_insert_zero_rows(__isl_take isl_mat *mat, unsigned row, unsigned n) { … } __isl_give isl_mat *isl_mat_add_zero_rows(__isl_take isl_mat *mat, unsigned n) { … } void isl_mat_col_submul(__isl_keep isl_mat *mat, int dst_col, isl_int f, int src_col) { … } void isl_mat_col_add(__isl_keep isl_mat *mat, int dst_col, int src_col) { … } void isl_mat_col_mul(__isl_keep isl_mat *mat, int dst_col, isl_int f, int src_col) { … } /* Add "f" times column "src_col" to column "dst_col" of "mat" and * return the result. */ __isl_give isl_mat *isl_mat_col_addmul(__isl_take isl_mat *mat, int dst_col, isl_int f, int src_col) { … } /* Negate column "col" of "mat" and return the result. */ __isl_give isl_mat *isl_mat_col_neg(__isl_take isl_mat *mat, int col) { … } /* Negate row "row" of "mat" and return the result. */ __isl_give isl_mat *isl_mat_row_neg(__isl_take isl_mat *mat, int row) { … } __isl_give isl_mat *isl_mat_unimodular_complete(__isl_take isl_mat *M, int row) { … } __isl_give isl_mat *isl_mat_concat(__isl_take isl_mat *top, __isl_take isl_mat *bot) { … } isl_bool isl_mat_is_equal(__isl_keep isl_mat *mat1, __isl_keep isl_mat *mat2) { … } __isl_give isl_mat *isl_mat_from_row_vec(__isl_take isl_vec *vec) { … } /* Return a copy of row "row" of "mat" as an isl_vec. */ __isl_give isl_vec *isl_mat_get_row(__isl_keep isl_mat *mat, unsigned row) { … } __isl_give isl_mat *isl_mat_vec_concat(__isl_take isl_mat *top, __isl_take isl_vec *bot) { … } __isl_give isl_mat *isl_mat_move_cols(__isl_take isl_mat *mat, unsigned dst_col, unsigned src_col, unsigned n) { … } /* Return the gcd of the elements in row "row" of "mat" in *gcd. * Return isl_stat_ok on success and isl_stat_error on failure. */ isl_stat isl_mat_row_gcd(__isl_keep isl_mat *mat, int row, isl_int *gcd) { … } void isl_mat_gcd(__isl_keep isl_mat *mat, isl_int *gcd) { … } /* Return the result of scaling "mat" by a factor of "m". */ __isl_give isl_mat *isl_mat_scale(__isl_take isl_mat *mat, isl_int m) { … } __isl_give isl_mat *isl_mat_scale_down(__isl_take isl_mat *mat, isl_int m) { … } __isl_give isl_mat *isl_mat_scale_down_row(__isl_take isl_mat *mat, int row, isl_int m) { … } __isl_give isl_mat *isl_mat_normalize(__isl_take isl_mat *mat) { … } __isl_give isl_mat *isl_mat_normalize_row(__isl_take isl_mat *mat, int row) { … } /* Number of initial non-zero columns. */ int isl_mat_initial_non_zero_cols(__isl_keep isl_mat *mat) { … } /* Return a basis for the space spanned by the rows of "mat". * Any basis will do, so simply perform Gaussian elimination and * remove the empty rows. */ __isl_give isl_mat *isl_mat_row_basis(__isl_take isl_mat *mat) { … } /* Return rows that extend a basis of "mat1" to one * that covers both "mat1" and "mat2". * The Hermite normal form of the concatenation of the two matrices is * * [ Q1 ] * [ M1 ] = [ H1 0 0 ] [ Q2 ] * [ M2 ] = [ H2 H3 0 ] [ Q3 ] * * The number of columns in H1 and H3 determine the number of rows * in Q1 and Q2. Q1 is a basis for M1, while Q2 extends this basis * to also cover M2. */ __isl_give isl_mat *isl_mat_row_basis_extension( __isl_take isl_mat *mat1, __isl_take isl_mat *mat2) { … } /* Are the rows of "mat1" linearly independent of those of "mat2"? * That is, is there no linear dependence among the combined rows * that is not already present in either "mat1" or "mat2"? * In other words, is the rank of "mat1" and "mat2" combined equal * to the sum of the ranks of "mat1" and "mat2"? */ isl_bool isl_mat_has_linearly_independent_rows(__isl_keep isl_mat *mat1, __isl_keep isl_mat *mat2) { … }
Codebase Browser
llvm