| File: | polly/lib/External/isl/isl_mat.c |
| Location: | line 1280, column 2 |
| Description: | Use of memory after it is freed |
| 1 | /* | |||
| 2 | * Copyright 2008-2009 Katholieke Universiteit Leuven | |||
| 3 | * Copyright 2014 Ecole Normale Superieure | |||
| 4 | * | |||
| 5 | * Use of this software is governed by the MIT license | |||
| 6 | * | |||
| 7 | * Written by Sven Verdoolaege, K.U.Leuven, Departement | |||
| 8 | * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium | |||
| 9 | * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France | |||
| 10 | */ | |||
| 11 | ||||
| 12 | #include <isl_ctx_private.h> | |||
| 13 | #include <isl_map_private.h> | |||
| 14 | #include <isl/space.h> | |||
| 15 | #include <isl_seq.h> | |||
| 16 | #include <isl_mat_private.h> | |||
| 17 | #include <isl_vec_private.h> | |||
| 18 | #include <isl_space_private.h> | |||
| 19 | #include <isl_val_private.h> | |||
| 20 | #include <isl/deprecated/mat_int.h> | |||
| 21 | ||||
| 22 | isl_ctx *isl_mat_get_ctx(__isl_keep isl_mat *mat) | |||
| 23 | { | |||
| 24 | return mat ? mat->ctx : NULL((void*)0); | |||
| 25 | } | |||
| 26 | ||||
| 27 | struct isl_mat *isl_mat_alloc(struct isl_ctx *ctx, | |||
| 28 | unsigned n_row, unsigned n_col) | |||
| 29 | { | |||
| 30 | int i; | |||
| 31 | struct isl_mat *mat; | |||
| 32 | ||||
| 33 | mat = isl_alloc_type(ctx, struct isl_mat)((struct isl_mat *)isl_malloc_or_die(ctx, sizeof(struct isl_mat ))); | |||
| 34 | if (!mat) | |||
| 35 | return NULL((void*)0); | |||
| 36 | ||||
| 37 | mat->row = NULL((void*)0); | |||
| 38 | mat->block = isl_blk_alloc(ctx, n_row * n_col); | |||
| 39 | if (isl_blk_is_error(mat->block)) | |||
| 40 | goto error; | |||
| 41 | mat->row = isl_alloc_array(ctx, isl_int *, n_row)((isl_int * *)isl_malloc_or_die(ctx, (n_row)*sizeof(isl_int * ))); | |||
| 42 | if (n_row && !mat->row) | |||
| 43 | goto error; | |||
| 44 | ||||
| 45 | for (i = 0; i < n_row; ++i) | |||
| 46 | mat->row[i] = mat->block.data + i * n_col; | |||
| 47 | ||||
| 48 | mat->ctx = ctx; | |||
| 49 | isl_ctx_ref(ctx); | |||
| 50 | mat->ref = 1; | |||
| 51 | mat->n_row = n_row; | |||
| 52 | mat->n_col = n_col; | |||
| 53 | mat->max_col = n_col; | |||
| 54 | mat->flags = 0; | |||
| 55 | ||||
| 56 | return mat; | |||
| 57 | error: | |||
| 58 | isl_blk_free(ctx, mat->block); | |||
| 59 | free(mat); | |||
| 60 | return NULL((void*)0); | |||
| 61 | } | |||
| 62 | ||||
| 63 | struct isl_mat *isl_mat_extend(struct isl_mat *mat, | |||
| 64 | unsigned n_row, unsigned n_col) | |||
| 65 | { | |||
| 66 | int i; | |||
| 67 | isl_int *old; | |||
| 68 | isl_int **row; | |||
| 69 | ||||
| 70 | if (!mat) | |||
| 71 | return NULL((void*)0); | |||
| 72 | ||||
| 73 | if (mat->max_col >= n_col && mat->n_row >= n_row) { | |||
| 74 | if (mat->n_col < n_col) | |||
| 75 | mat->n_col = n_col; | |||
| 76 | return mat; | |||
| 77 | } | |||
| 78 | ||||
| 79 | if (mat->max_col < n_col) { | |||
| 80 | struct isl_mat *new_mat; | |||
| 81 | ||||
| 82 | if (n_row < mat->n_row) | |||
| 83 | n_row = mat->n_row; | |||
| 84 | new_mat = isl_mat_alloc(mat->ctx, n_row, n_col); | |||
| 85 | if (!new_mat) | |||
| 86 | goto error; | |||
| 87 | for (i = 0; i < mat->n_row; ++i) | |||
| 88 | isl_seq_cpy(new_mat->row[i], mat->row[i], mat->n_col); | |||
| 89 | isl_mat_free(mat); | |||
| 90 | return new_mat; | |||
| 91 | } | |||
| 92 | ||||
| 93 | mat = isl_mat_cow(mat); | |||
| 94 | if (!mat) | |||
| 95 | goto error; | |||
| 96 | ||||
| 97 | old = mat->block.data; | |||
| 98 | mat->block = isl_blk_extend(mat->ctx, mat->block, n_row * mat->max_col); | |||
| 99 | if (isl_blk_is_error(mat->block)) | |||
| 100 | goto error; | |||
| 101 | row = isl_realloc_array(mat->ctx, mat->row, isl_int *, n_row)((isl_int * *)isl_realloc_or_die(mat->ctx, mat->row, (n_row )*sizeof(isl_int *))); | |||
| 102 | if (n_row && !row) | |||
| 103 | goto error; | |||
| 104 | mat->row = row; | |||
| 105 | ||||
| 106 | for (i = 0; i < mat->n_row; ++i) | |||
| 107 | mat->row[i] = mat->block.data + (mat->row[i] - old); | |||
| 108 | for (i = mat->n_row; i < n_row; ++i) | |||
| 109 | mat->row[i] = mat->block.data + i * mat->max_col; | |||
| 110 | mat->n_row = n_row; | |||
| 111 | if (mat->n_col < n_col) | |||
| 112 | mat->n_col = n_col; | |||
| 113 | ||||
| 114 | return mat; | |||
| 115 | error: | |||
| 116 | isl_mat_free(mat); | |||
| 117 | return NULL((void*)0); | |||
| 118 | } | |||
| 119 | ||||
| 120 | __isl_give isl_mat *isl_mat_sub_alloc6(isl_ctx *ctx, isl_int **row, | |||
| 121 | unsigned first_row, unsigned n_row, unsigned first_col, unsigned n_col) | |||
| 122 | { | |||
| 123 | int i; | |||
| 124 | struct isl_mat *mat; | |||
| 125 | ||||
| 126 | mat = isl_alloc_type(ctx, struct isl_mat)((struct isl_mat *)isl_malloc_or_die(ctx, sizeof(struct isl_mat ))); | |||
| 127 | if (!mat) | |||
| 128 | return NULL((void*)0); | |||
| 129 | mat->row = isl_alloc_array(ctx, isl_int *, n_row)((isl_int * *)isl_malloc_or_die(ctx, (n_row)*sizeof(isl_int * ))); | |||
| 130 | if (n_row && !mat->row) | |||
| 131 | goto error; | |||
| 132 | for (i = 0; i < n_row; ++i) | |||
| 133 | mat->row[i] = row[first_row+i] + first_col; | |||
| 134 | mat->ctx = ctx; | |||
| 135 | isl_ctx_ref(ctx); | |||
| 136 | mat->ref = 1; | |||
| 137 | mat->n_row = n_row; | |||
| 138 | mat->n_col = n_col; | |||
| 139 | mat->block = isl_blk_empty(); | |||
| 140 | mat->flags = ISL_MAT_BORROWED(1 << 0); | |||
| 141 | return mat; | |||
| 142 | error: | |||
| 143 | free(mat); | |||
| 144 | return NULL((void*)0); | |||
| 145 | } | |||
| 146 | ||||
| 147 | __isl_give isl_mat *isl_mat_sub_alloc(__isl_keep isl_mat *mat, | |||
| 148 | unsigned first_row, unsigned n_row, unsigned first_col, unsigned n_col) | |||
| 149 | { | |||
| 150 | if (!mat) | |||
| 151 | return NULL((void*)0); | |||
| 152 | return isl_mat_sub_alloc6(mat->ctx, mat->row, first_row, n_row, | |||
| 153 | first_col, n_col); | |||
| 154 | } | |||
| 155 | ||||
| 156 | void isl_mat_sub_copy(struct isl_ctx *ctx, isl_int **dst, isl_int **src, | |||
| 157 | unsigned n_row, unsigned dst_col, unsigned src_col, unsigned n_col) | |||
| 158 | { | |||
| 159 | int i; | |||
| 160 | ||||
| 161 | for (i = 0; i < n_row; ++i) | |||
| 162 | isl_seq_cpy(dst[i]+dst_col, src[i]+src_col, n_col); | |||
| 163 | } | |||
| 164 | ||||
| 165 | void isl_mat_sub_neg(struct isl_ctx *ctx, isl_int **dst, isl_int **src, | |||
| 166 | unsigned n_row, unsigned dst_col, unsigned src_col, unsigned n_col) | |||
| 167 | { | |||
| 168 | int i; | |||
| 169 | ||||
| 170 | for (i = 0; i < n_row; ++i) | |||
| 171 | isl_seq_neg(dst[i]+dst_col, src[i]+src_col, n_col); | |||
| 172 | } | |||
| 173 | ||||
| 174 | struct isl_mat *isl_mat_copy(struct isl_mat *mat) | |||
| 175 | { | |||
| 176 | if (!mat) | |||
| 177 | return NULL((void*)0); | |||
| 178 | ||||
| 179 | mat->ref++; | |||
| 180 | return mat; | |||
| 181 | } | |||
| 182 | ||||
| 183 | struct isl_mat *isl_mat_dup(struct isl_mat *mat) | |||
| 184 | { | |||
| 185 | int i; | |||
| 186 | struct isl_mat *mat2; | |||
| 187 | ||||
| 188 | if (!mat) | |||
| 189 | return NULL((void*)0); | |||
| 190 | mat2 = isl_mat_alloc(mat->ctx, mat->n_row, mat->n_col); | |||
| 191 | if (!mat2) | |||
| 192 | return NULL((void*)0); | |||
| 193 | for (i = 0; i < mat->n_row; ++i) | |||
| 194 | isl_seq_cpy(mat2->row[i], mat->row[i], mat->n_col); | |||
| 195 | return mat2; | |||
| 196 | } | |||
| 197 | ||||
| 198 | struct isl_mat *isl_mat_cow(struct isl_mat *mat) | |||
| 199 | { | |||
| 200 | struct isl_mat *mat2; | |||
| 201 | if (!mat) | |||
| 202 | return NULL((void*)0); | |||
| 203 | ||||
| 204 | if (mat->ref == 1 && !ISL_F_ISSET(mat, ISL_MAT_BORROWED)(!!(((mat)->flags) & ((1 << 0))))) | |||
| 205 | return mat; | |||
| 206 | ||||
| 207 | mat2 = isl_mat_dup(mat); | |||
| 208 | isl_mat_free(mat); | |||
| 209 | return mat2; | |||
| 210 | } | |||
| 211 | ||||
| 212 | __isl_null isl_mat *isl_mat_free(__isl_take isl_mat *mat) | |||
| 213 | { | |||
| 214 | if (!mat) | |||
| 215 | return NULL((void*)0); | |||
| 216 | ||||
| 217 | if (--mat->ref > 0) | |||
| 218 | return NULL((void*)0); | |||
| 219 | ||||
| 220 | if (!ISL_F_ISSET(mat, ISL_MAT_BORROWED)(!!(((mat)->flags) & ((1 << 0))))) | |||
| 221 | isl_blk_free(mat->ctx, mat->block); | |||
| 222 | isl_ctx_deref(mat->ctx); | |||
| 223 | free(mat->row); | |||
| 224 | free(mat); | |||
| 225 | ||||
| 226 | return NULL((void*)0); | |||
| 227 | } | |||
| 228 | ||||
| 229 | int isl_mat_rows(__isl_keep isl_mat *mat) | |||
| 230 | { | |||
| 231 | return mat ? mat->n_row : -1; | |||
| 232 | } | |||
| 233 | ||||
| 234 | int isl_mat_cols(__isl_keep isl_mat *mat) | |||
| 235 | { | |||
| 236 | return mat ? mat->n_col : -1; | |||
| 237 | } | |||
| 238 | ||||
| 239 | int isl_mat_get_element(__isl_keep isl_mat *mat, int row, int col, isl_int *v) | |||
| 240 | { | |||
| 241 | if (!mat) | |||
| 242 | return -1; | |||
| 243 | if (row < 0 || row >= mat->n_row) | |||
| 244 | isl_die(mat->ctx, isl_error_invalid, "row out of range",do { isl_handle_error(mat->ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 245); return -1; } while (0) | |||
| 245 | return -1)do { isl_handle_error(mat->ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 245); return -1; } while (0); | |||
| 246 | if (col < 0 || col >= mat->n_col) | |||
| 247 | isl_die(mat->ctx, isl_error_invalid, "column out of range",do { isl_handle_error(mat->ctx, isl_error_invalid, "column out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 248); return -1; } while (0) | |||
| 248 | return -1)do { isl_handle_error(mat->ctx, isl_error_invalid, "column out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 248); return -1; } while (0); | |||
| 249 | isl_int_set(*v, mat->row[row][col])isl_sioimath_set((*v), *(mat->row[row][col])); | |||
| 250 | return 0; | |||
| 251 | } | |||
| 252 | ||||
| 253 | /* Extract the element at row "row", oolumn "col" of "mat". | |||
| 254 | */ | |||
| 255 | __isl_give isl_val *isl_mat_get_element_val(__isl_keep isl_mat *mat, | |||
| 256 | int row, int col) | |||
| 257 | { | |||
| 258 | isl_ctx *ctx; | |||
| 259 | ||||
| 260 | if (!mat) | |||
| 261 | return NULL((void*)0); | |||
| 262 | ctx = isl_mat_get_ctx(mat); | |||
| 263 | if (row < 0 || row >= mat->n_row) | |||
| 264 | isl_die(ctx, isl_error_invalid, "row out of range",do { isl_handle_error(ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 265); return ((void*)0); } while (0) | |||
| 265 | return NULL)do { isl_handle_error(ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 265); return ((void*)0); } while (0); | |||
| 266 | if (col < 0 || col >= mat->n_col) | |||
| 267 | isl_die(ctx, isl_error_invalid, "column out of range",do { isl_handle_error(ctx, isl_error_invalid, "column out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 268); return ((void*)0); } while (0) | |||
| 268 | return NULL)do { isl_handle_error(ctx, isl_error_invalid, "column out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 268); return ((void*)0); } while (0); | |||
| 269 | return isl_val_int_from_isl_int(ctx, mat->row[row][col]); | |||
| 270 | } | |||
| 271 | ||||
| 272 | __isl_give isl_mat *isl_mat_set_element(__isl_take isl_mat *mat, | |||
| 273 | int row, int col, isl_int v) | |||
| 274 | { | |||
| 275 | mat = isl_mat_cow(mat); | |||
| 276 | if (!mat) | |||
| 277 | return NULL((void*)0); | |||
| 278 | if (row < 0 || row >= mat->n_row) | |||
| 279 | isl_die(mat->ctx, isl_error_invalid, "row out of range",do { isl_handle_error(mat->ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 280); goto error; } while (0) | |||
| 280 | goto error)do { isl_handle_error(mat->ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 280); goto error; } while (0); | |||
| 281 | if (col < 0 || col >= mat->n_col) | |||
| 282 | isl_die(mat->ctx, isl_error_invalid, "column out of range",do { isl_handle_error(mat->ctx, isl_error_invalid, "column out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 283); goto error; } while (0) | |||
| 283 | goto error)do { isl_handle_error(mat->ctx, isl_error_invalid, "column out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 283); goto error; } while (0); | |||
| 284 | isl_int_set(mat->row[row][col], v)isl_sioimath_set((mat->row[row][col]), *(v)); | |||
| 285 | return mat; | |||
| 286 | error: | |||
| 287 | isl_mat_free(mat); | |||
| 288 | return NULL((void*)0); | |||
| 289 | } | |||
| 290 | ||||
| 291 | __isl_give isl_mat *isl_mat_set_element_si(__isl_take isl_mat *mat, | |||
| 292 | int row, int col, int v) | |||
| 293 | { | |||
| 294 | mat = isl_mat_cow(mat); | |||
| 295 | if (!mat) | |||
| 296 | return NULL((void*)0); | |||
| 297 | if (row < 0 || row >= mat->n_row) | |||
| 298 | isl_die(mat->ctx, isl_error_invalid, "row out of range",do { isl_handle_error(mat->ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 299); goto error; } while (0) | |||
| 299 | goto error)do { isl_handle_error(mat->ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 299); goto error; } while (0); | |||
| 300 | if (col < 0 || col >= mat->n_col) | |||
| 301 | isl_die(mat->ctx, isl_error_invalid, "column out of range",do { isl_handle_error(mat->ctx, isl_error_invalid, "column out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 302); goto error; } while (0) | |||
| 302 | goto error)do { isl_handle_error(mat->ctx, isl_error_invalid, "column out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 302); goto error; } while (0); | |||
| 303 | isl_int_set_si(mat->row[row][col], v)isl_sioimath_set_si((mat->row[row][col]), v); | |||
| 304 | return mat; | |||
| 305 | error: | |||
| 306 | isl_mat_free(mat); | |||
| 307 | return NULL((void*)0); | |||
| 308 | } | |||
| 309 | ||||
| 310 | /* Replace the element at row "row", column "col" of "mat" by "v". | |||
| 311 | */ | |||
| 312 | __isl_give isl_mat *isl_mat_set_element_val(__isl_take isl_mat *mat, | |||
| 313 | int row, int col, __isl_take isl_val *v) | |||
| 314 | { | |||
| 315 | if (!v) | |||
| 316 | return isl_mat_free(mat); | |||
| 317 | if (!isl_val_is_int(v)) | |||
| 318 | isl_die(isl_val_get_ctx(v), isl_error_invalid,do { isl_handle_error(isl_val_get_ctx(v), isl_error_invalid, "expecting integer value" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 319); goto error; } while (0) | |||
| 319 | "expecting integer value", goto error)do { isl_handle_error(isl_val_get_ctx(v), isl_error_invalid, "expecting integer value" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 319); goto error; } while (0); | |||
| 320 | mat = isl_mat_set_element(mat, row, col, v->n); | |||
| 321 | isl_val_free(v); | |||
| 322 | return mat; | |||
| 323 | error: | |||
| 324 | isl_val_free(v); | |||
| 325 | return isl_mat_free(mat); | |||
| 326 | } | |||
| 327 | ||||
| 328 | __isl_give isl_mat *isl_mat_diag(isl_ctx *ctx, unsigned n_row, isl_int d) | |||
| 329 | { | |||
| 330 | int i; | |||
| 331 | struct isl_mat *mat; | |||
| 332 | ||||
| 333 | mat = isl_mat_alloc(ctx, n_row, n_row); | |||
| 334 | if (!mat) | |||
| 335 | return NULL((void*)0); | |||
| 336 | for (i = 0; i < n_row; ++i) { | |||
| 337 | isl_seq_clr(mat->row[i], i); | |||
| 338 | isl_int_set(mat->row[i][i], d)isl_sioimath_set((mat->row[i][i]), *(d)); | |||
| 339 | isl_seq_clr(mat->row[i]+i+1, n_row-(i+1)); | |||
| 340 | } | |||
| 341 | ||||
| 342 | return mat; | |||
| 343 | } | |||
| 344 | ||||
| 345 | __isl_give isl_mat *isl_mat_identity(isl_ctx *ctx, unsigned n_row) | |||
| 346 | { | |||
| 347 | if (!ctx) | |||
| 348 | return NULL((void*)0); | |||
| 349 | return isl_mat_diag(ctx, n_row, ctx->one); | |||
| 350 | } | |||
| 351 | ||||
| 352 | /* Is "mat" a (possibly scaled) identity matrix? | |||
| 353 | */ | |||
| 354 | int isl_mat_is_scaled_identity(__isl_keep isl_mat *mat) | |||
| 355 | { | |||
| 356 | int i; | |||
| 357 | ||||
| 358 | if (!mat) | |||
| 359 | return -1; | |||
| 360 | if (mat->n_row != mat->n_col) | |||
| 361 | return 0; | |||
| 362 | ||||
| 363 | for (i = 0; i < mat->n_row; ++i) { | |||
| 364 | if (isl_seq_first_non_zero(mat->row[i], i) != -1) | |||
| 365 | return 0; | |||
| 366 | if (isl_int_ne(mat->row[0][0], mat->row[i][i])(isl_sioimath_cmp(*(mat->row[0][0]), *(mat->row[i][i])) != 0)) | |||
| 367 | return 0; | |||
| 368 | if (isl_seq_first_non_zero(mat->row[i] + i + 1, | |||
| 369 | mat->n_col - (i + 1)) != -1) | |||
| 370 | return 0; | |||
| 371 | } | |||
| 372 | ||||
| 373 | return 1; | |||
| 374 | } | |||
| 375 | ||||
| 376 | struct isl_vec *isl_mat_vec_product(struct isl_mat *mat, struct isl_vec *vec) | |||
| 377 | { | |||
| 378 | int i; | |||
| 379 | struct isl_vec *prod; | |||
| 380 | ||||
| 381 | if (!mat || !vec) | |||
| 382 | goto error; | |||
| 383 | ||||
| 384 | isl_assert(mat->ctx, mat->n_col == vec->size, goto error)do { if (mat->n_col == vec->size) break; do { isl_handle_error (mat->ctx, isl_error_unknown, "Assertion \"" "mat->n_col == vec->size" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 384); goto error; } while (0); } while (0); | |||
| 385 | ||||
| 386 | prod = isl_vec_alloc(mat->ctx, mat->n_row); | |||
| 387 | if (!prod) | |||
| 388 | goto error; | |||
| 389 | ||||
| 390 | for (i = 0; i < prod->size; ++i) | |||
| 391 | isl_seq_inner_product(mat->row[i], vec->el, vec->size, | |||
| 392 | &prod->block.data[i]); | |||
| 393 | isl_mat_free(mat); | |||
| 394 | isl_vec_free(vec); | |||
| 395 | return prod; | |||
| 396 | error: | |||
| 397 | isl_mat_free(mat); | |||
| 398 | isl_vec_free(vec); | |||
| 399 | return NULL((void*)0); | |||
| 400 | } | |||
| 401 | ||||
| 402 | __isl_give isl_vec *isl_mat_vec_inverse_product(__isl_take isl_mat *mat, | |||
| 403 | __isl_take isl_vec *vec) | |||
| 404 | { | |||
| 405 | struct isl_mat *vec_mat; | |||
| 406 | int i; | |||
| 407 | ||||
| 408 | if (!mat || !vec) | |||
| 409 | goto error; | |||
| 410 | vec_mat = isl_mat_alloc(vec->ctx, vec->size, 1); | |||
| 411 | if (!vec_mat) | |||
| 412 | goto error; | |||
| 413 | for (i = 0; i < vec->size; ++i) | |||
| 414 | isl_int_set(vec_mat->row[i][0], vec->el[i])isl_sioimath_set((vec_mat->row[i][0]), *(vec->el[i])); | |||
| 415 | vec_mat = isl_mat_inverse_product(mat, vec_mat); | |||
| 416 | isl_vec_free(vec); | |||
| 417 | if (!vec_mat) | |||
| 418 | return NULL((void*)0); | |||
| 419 | vec = isl_vec_alloc(vec_mat->ctx, vec_mat->n_row); | |||
| 420 | if (vec) | |||
| 421 | for (i = 0; i < vec->size; ++i) | |||
| 422 | isl_int_set(vec->el[i], vec_mat->row[i][0])isl_sioimath_set((vec->el[i]), *(vec_mat->row[i][0])); | |||
| 423 | isl_mat_free(vec_mat); | |||
| 424 | return vec; | |||
| 425 | error: | |||
| 426 | isl_mat_free(mat); | |||
| 427 | isl_vec_free(vec); | |||
| 428 | return NULL((void*)0); | |||
| 429 | } | |||
| 430 | ||||
| 431 | struct isl_vec *isl_vec_mat_product(struct isl_vec *vec, struct isl_mat *mat) | |||
| 432 | { | |||
| 433 | int i, j; | |||
| 434 | struct isl_vec *prod; | |||
| 435 | ||||
| 436 | if (!mat || !vec) | |||
| 437 | goto error; | |||
| 438 | ||||
| 439 | isl_assert(mat->ctx, mat->n_row == vec->size, goto error)do { if (mat->n_row == vec->size) break; do { isl_handle_error (mat->ctx, isl_error_unknown, "Assertion \"" "mat->n_row == vec->size" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 439); goto error; } while (0); } while (0); | |||
| 440 | ||||
| 441 | prod = isl_vec_alloc(mat->ctx, mat->n_col); | |||
| 442 | if (!prod) | |||
| 443 | goto error; | |||
| 444 | ||||
| 445 | for (i = 0; i < prod->size; ++i) { | |||
| 446 | isl_int_set_si(prod->el[i], 0)isl_sioimath_set_si((prod->el[i]), 0); | |||
| 447 | for (j = 0; j < vec->size; ++j) | |||
| 448 | isl_int_addmul(prod->el[i], vec->el[j], mat->row[j][i])isl_sioimath_addmul((prod->el[i]), *(vec->el[j]), *(mat ->row[j][i])); | |||
| 449 | } | |||
| 450 | isl_mat_free(mat); | |||
| 451 | isl_vec_free(vec); | |||
| 452 | return prod; | |||
| 453 | error: | |||
| 454 | isl_mat_free(mat); | |||
| 455 | isl_vec_free(vec); | |||
| 456 | return NULL((void*)0); | |||
| 457 | } | |||
| 458 | ||||
| 459 | struct isl_mat *isl_mat_aff_direct_sum(struct isl_mat *left, | |||
| 460 | struct isl_mat *right) | |||
| 461 | { | |||
| 462 | int i; | |||
| 463 | struct isl_mat *sum; | |||
| 464 | ||||
| 465 | if (!left || !right) | |||
| 466 | goto error; | |||
| 467 | ||||
| 468 | isl_assert(left->ctx, left->n_row == right->n_row, goto error)do { if (left->n_row == right->n_row) break; do { isl_handle_error (left->ctx, isl_error_unknown, "Assertion \"" "left->n_row == right->n_row" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 468); goto error; } while (0); } while (0); | |||
| 469 | isl_assert(left->ctx, left->n_row >= 1, goto error)do { if (left->n_row >= 1) break; do { isl_handle_error (left->ctx, isl_error_unknown, "Assertion \"" "left->n_row >= 1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 469); goto error; } while (0); } while (0); | |||
| 470 | isl_assert(left->ctx, left->n_col >= 1, goto error)do { if (left->n_col >= 1) break; do { isl_handle_error (left->ctx, isl_error_unknown, "Assertion \"" "left->n_col >= 1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 470); goto error; } while (0); } while (0); | |||
| 471 | isl_assert(left->ctx, right->n_col >= 1, goto error)do { if (right->n_col >= 1) break; do { isl_handle_error (left->ctx, isl_error_unknown, "Assertion \"" "right->n_col >= 1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 471); goto error; } while (0); } while (0); | |||
| 472 | isl_assert(left->ctx,do { if (isl_seq_first_non_zero(left->row[0]+1, left->n_col -1) == -1) break; do { isl_handle_error(left->ctx, isl_error_unknown , "Assertion \"" "isl_seq_first_non_zero(left->row[0]+1, left->n_col-1) == -1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 474); goto error; } while (0); } while (0) | |||
| 473 | isl_seq_first_non_zero(left->row[0]+1, left->n_col-1) == -1,do { if (isl_seq_first_non_zero(left->row[0]+1, left->n_col -1) == -1) break; do { isl_handle_error(left->ctx, isl_error_unknown , "Assertion \"" "isl_seq_first_non_zero(left->row[0]+1, left->n_col-1) == -1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 474); goto error; } while (0); } while (0) | |||
| 474 | goto error)do { if (isl_seq_first_non_zero(left->row[0]+1, left->n_col -1) == -1) break; do { isl_handle_error(left->ctx, isl_error_unknown , "Assertion \"" "isl_seq_first_non_zero(left->row[0]+1, left->n_col-1) == -1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 474); goto error; } while (0); } while (0); | |||
| 475 | isl_assert(left->ctx,do { if (isl_seq_first_non_zero(right->row[0]+1, right-> n_col-1) == -1) break; do { isl_handle_error(left->ctx, isl_error_unknown , "Assertion \"" "isl_seq_first_non_zero(right->row[0]+1, right->n_col-1) == -1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 477); goto error; } while (0); } while (0) | |||
| 476 | isl_seq_first_non_zero(right->row[0]+1, right->n_col-1) == -1,do { if (isl_seq_first_non_zero(right->row[0]+1, right-> n_col-1) == -1) break; do { isl_handle_error(left->ctx, isl_error_unknown , "Assertion \"" "isl_seq_first_non_zero(right->row[0]+1, right->n_col-1) == -1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 477); goto error; } while (0); } while (0) | |||
| 477 | goto error)do { if (isl_seq_first_non_zero(right->row[0]+1, right-> n_col-1) == -1) break; do { isl_handle_error(left->ctx, isl_error_unknown , "Assertion \"" "isl_seq_first_non_zero(right->row[0]+1, right->n_col-1) == -1" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 477); goto error; } while (0); } while (0); | |||
| 478 | ||||
| 479 | sum = isl_mat_alloc(left->ctx, left->n_row, left->n_col + right->n_col - 1); | |||
| 480 | if (!sum) | |||
| 481 | goto error; | |||
| 482 | isl_int_lcm(sum->row[0][0], left->row[0][0], right->row[0][0])isl_sioimath_lcm((sum->row[0][0]), *(left->row[0][0]), * (right->row[0][0])); | |||
| 483 | isl_int_divexact(left->row[0][0], sum->row[0][0], left->row[0][0])isl_sioimath_tdiv_q((left->row[0][0]), *(sum->row[0][0] ), *(left->row[0][0])); | |||
| 484 | isl_int_divexact(right->row[0][0], sum->row[0][0], right->row[0][0])isl_sioimath_tdiv_q((right->row[0][0]), *(sum->row[0][0 ]), *(right->row[0][0])); | |||
| 485 | ||||
| 486 | isl_seq_clr(sum->row[0]+1, sum->n_col-1); | |||
| 487 | for (i = 1; i < sum->n_row; ++i) { | |||
| 488 | isl_int_mul(sum->row[i][0], left->row[0][0], left->row[i][0])isl_sioimath_mul((sum->row[i][0]), *(left->row[0][0]), * (left->row[i][0])); | |||
| 489 | isl_int_addmul(sum->row[i][0],isl_sioimath_addmul((sum->row[i][0]), *(right->row[0][0 ]), *(right->row[i][0])) | |||
| 490 | right->row[0][0], right->row[i][0])isl_sioimath_addmul((sum->row[i][0]), *(right->row[0][0 ]), *(right->row[i][0])); | |||
| 491 | isl_seq_scale(sum->row[i]+1, left->row[i]+1, left->row[0][0], | |||
| 492 | left->n_col-1); | |||
| 493 | isl_seq_scale(sum->row[i]+left->n_col, | |||
| 494 | right->row[i]+1, right->row[0][0], | |||
| 495 | right->n_col-1); | |||
| 496 | } | |||
| 497 | ||||
| 498 | isl_int_divexact(left->row[0][0], sum->row[0][0], left->row[0][0])isl_sioimath_tdiv_q((left->row[0][0]), *(sum->row[0][0] ), *(left->row[0][0])); | |||
| 499 | isl_int_divexact(right->row[0][0], sum->row[0][0], right->row[0][0])isl_sioimath_tdiv_q((right->row[0][0]), *(sum->row[0][0 ]), *(right->row[0][0])); | |||
| 500 | isl_mat_free(left); | |||
| 501 | isl_mat_free(right); | |||
| 502 | return sum; | |||
| 503 | error: | |||
| 504 | isl_mat_free(left); | |||
| 505 | isl_mat_free(right); | |||
| 506 | return NULL((void*)0); | |||
| 507 | } | |||
| 508 | ||||
| 509 | static void exchange(struct isl_mat *M, struct isl_mat **U, | |||
| 510 | struct isl_mat **Q, unsigned row, unsigned i, unsigned j) | |||
| 511 | { | |||
| 512 | int r; | |||
| 513 | for (r = row; r < M->n_row; ++r) | |||
| 514 | isl_int_swap(M->row[r][i], M->row[r][j])isl_sioimath_swap((M->row[r][i]), (M->row[r][j])); | |||
| 515 | if (U) { | |||
| 516 | for (r = 0; r < (*U)->n_row; ++r) | |||
| 517 | isl_int_swap((*U)->row[r][i], (*U)->row[r][j])isl_sioimath_swap(((*U)->row[r][i]), ((*U)->row[r][j])); | |||
| 518 | } | |||
| 519 | if (Q) | |||
| 520 | isl_mat_swap_rows(*Q, i, j); | |||
| 521 | } | |||
| 522 | ||||
| 523 | static void subtract(struct isl_mat *M, struct isl_mat **U, | |||
| 524 | struct isl_mat **Q, unsigned row, unsigned i, unsigned j, isl_int m) | |||
| 525 | { | |||
| 526 | int r; | |||
| 527 | for (r = row; r < M->n_row; ++r) | |||
| 528 | isl_int_submul(M->row[r][j], m, M->row[r][i])isl_sioimath_submul((M->row[r][j]), *(m), *(M->row[r][i ])); | |||
| 529 | if (U) { | |||
| 530 | for (r = 0; r < (*U)->n_row; ++r) | |||
| 531 | isl_int_submul((*U)->row[r][j], m, (*U)->row[r][i])isl_sioimath_submul(((*U)->row[r][j]), *(m), *((*U)->row [r][i])); | |||
| 532 | } | |||
| 533 | if (Q) { | |||
| 534 | for (r = 0; r < (*Q)->n_col; ++r) | |||
| 535 | isl_int_addmul((*Q)->row[i][r], m, (*Q)->row[j][r])isl_sioimath_addmul(((*Q)->row[i][r]), *(m), *((*Q)->row [j][r])); | |||
| 536 | } | |||
| 537 | } | |||
| 538 | ||||
| 539 | static void oppose(struct isl_mat *M, struct isl_mat **U, | |||
| 540 | struct isl_mat **Q, unsigned row, unsigned col) | |||
| 541 | { | |||
| 542 | int r; | |||
| 543 | for (r = row; r < M->n_row; ++r) | |||
| 544 | isl_int_neg(M->row[r][col], M->row[r][col])isl_sioimath_neg((M->row[r][col]), *(M->row[r][col])); | |||
| 545 | if (U) { | |||
| 546 | for (r = 0; r < (*U)->n_row; ++r) | |||
| 547 | isl_int_neg((*U)->row[r][col], (*U)->row[r][col])isl_sioimath_neg(((*U)->row[r][col]), *((*U)->row[r][col ])); | |||
| 548 | } | |||
| 549 | if (Q) | |||
| 550 | isl_seq_neg((*Q)->row[col], (*Q)->row[col], (*Q)->n_col); | |||
| 551 | } | |||
| 552 | ||||
| 553 | /* Given matrix M, compute | |||
| 554 | * | |||
| 555 | * M U = H | |||
| 556 | * M = H Q | |||
| 557 | * | |||
| 558 | * with U and Q unimodular matrices and H a matrix in column echelon form | |||
| 559 | * such that on each echelon row the entries in the non-echelon column | |||
| 560 | * are non-negative (if neg == 0) or non-positive (if neg == 1) | |||
| 561 | * and strictly smaller (in absolute value) than the entries in the echelon | |||
| 562 | * column. | |||
| 563 | * If U or Q are NULL, then these matrices are not computed. | |||
| 564 | */ | |||
| 565 | struct isl_mat *isl_mat_left_hermite(struct isl_mat *M, int neg, | |||
| 566 | struct isl_mat **U, struct isl_mat **Q) | |||
| 567 | { | |||
| 568 | isl_int c; | |||
| 569 | int row, col; | |||
| 570 | ||||
| 571 | if (U) | |||
| 572 | *U = NULL((void*)0); | |||
| 573 | if (Q) | |||
| 574 | *Q = NULL((void*)0); | |||
| 575 | if (!M) | |||
| 576 | goto error; | |||
| 577 | M = isl_mat_cow(M); | |||
| 578 | if (!M) | |||
| 579 | goto error; | |||
| 580 | if (U) { | |||
| 581 | *U = isl_mat_identity(M->ctx, M->n_col); | |||
| 582 | if (!*U) | |||
| 583 | goto error; | |||
| 584 | } | |||
| 585 | if (Q) { | |||
| 586 | *Q = isl_mat_identity(M->ctx, M->n_col); | |||
| 587 | if (!*Q) | |||
| 588 | goto error; | |||
| 589 | } | |||
| 590 | ||||
| 591 | col = 0; | |||
| 592 | isl_int_init(c)isl_sioimath_init((c)); | |||
| 593 | for (row = 0; row < M->n_row; ++row) { | |||
| 594 | int first, i, off; | |||
| 595 | first = isl_seq_abs_min_non_zero(M->row[row]+col, M->n_col-col); | |||
| 596 | if (first == -1) | |||
| 597 | continue; | |||
| 598 | first += col; | |||
| 599 | if (first != col) | |||
| 600 | exchange(M, U, Q, row, first, col); | |||
| 601 | if (isl_int_is_neg(M->row[row][col])(isl_sioimath_sgn(*(M->row[row][col])) < 0)) | |||
| 602 | oppose(M, U, Q, row, col); | |||
| 603 | first = col+1; | |||
| 604 | while ((off = isl_seq_first_non_zero(M->row[row]+first, | |||
| 605 | M->n_col-first)) != -1) { | |||
| 606 | first += off; | |||
| 607 | isl_int_fdiv_q(c, M->row[row][first], M->row[row][col])isl_sioimath_fdiv_q((c), *(M->row[row][first]), *(M->row [row][col])); | |||
| 608 | subtract(M, U, Q, row, col, first, c); | |||
| 609 | if (!isl_int_is_zero(M->row[row][first])(isl_sioimath_sgn(*(M->row[row][first])) == 0)) | |||
| 610 | exchange(M, U, Q, row, first, col); | |||
| 611 | else | |||
| 612 | ++first; | |||
| 613 | } | |||
| 614 | for (i = 0; i < col; ++i) { | |||
| 615 | if (isl_int_is_zero(M->row[row][i])(isl_sioimath_sgn(*(M->row[row][i])) == 0)) | |||
| 616 | continue; | |||
| 617 | if (neg) | |||
| 618 | isl_int_cdiv_q(c, M->row[row][i], M->row[row][col])isl_sioimath_cdiv_q((c), *(M->row[row][i]), *(M->row[row ][col])); | |||
| 619 | else | |||
| 620 | isl_int_fdiv_q(c, M->row[row][i], M->row[row][col])isl_sioimath_fdiv_q((c), *(M->row[row][i]), *(M->row[row ][col])); | |||
| 621 | if (isl_int_is_zero(c)(isl_sioimath_sgn(*(c)) == 0)) | |||
| 622 | continue; | |||
| 623 | subtract(M, U, Q, row, col, i, c); | |||
| 624 | } | |||
| 625 | ++col; | |||
| 626 | } | |||
| 627 | isl_int_clear(c)isl_sioimath_clear((c)); | |||
| 628 | ||||
| 629 | return M; | |||
| 630 | error: | |||
| 631 | if (Q) { | |||
| 632 | isl_mat_free(*Q); | |||
| 633 | *Q = NULL((void*)0); | |||
| 634 | } | |||
| 635 | if (U) { | |||
| 636 | isl_mat_free(*U); | |||
| 637 | *U = NULL((void*)0); | |||
| 638 | } | |||
| 639 | isl_mat_free(M); | |||
| 640 | return NULL((void*)0); | |||
| 641 | } | |||
| 642 | ||||
| 643 | struct isl_mat *isl_mat_right_kernel(struct isl_mat *mat) | |||
| 644 | { | |||
| 645 | int i, rank; | |||
| 646 | struct isl_mat *U = NULL((void*)0); | |||
| 647 | struct isl_mat *K; | |||
| 648 | ||||
| 649 | mat = isl_mat_left_hermite(mat, 0, &U, NULL((void*)0)); | |||
| 650 | if (!mat || !U) | |||
| 651 | goto error; | |||
| 652 | ||||
| 653 | for (i = 0, rank = 0; rank < mat->n_col; ++rank) { | |||
| 654 | while (i < mat->n_row && isl_int_is_zero(mat->row[i][rank])(isl_sioimath_sgn(*(mat->row[i][rank])) == 0)) | |||
| 655 | ++i; | |||
| 656 | if (i >= mat->n_row) | |||
| 657 | break; | |||
| 658 | } | |||
| 659 | K = isl_mat_alloc(U->ctx, U->n_row, U->n_col - rank); | |||
| 660 | if (!K) | |||
| 661 | goto error; | |||
| 662 | isl_mat_sub_copy(K->ctx, K->row, U->row, U->n_row, 0, rank, U->n_col-rank); | |||
| 663 | isl_mat_free(mat); | |||
| 664 | isl_mat_free(U); | |||
| 665 | return K; | |||
| 666 | error: | |||
| 667 | isl_mat_free(mat); | |||
| 668 | isl_mat_free(U); | |||
| 669 | return NULL((void*)0); | |||
| 670 | } | |||
| 671 | ||||
| 672 | struct isl_mat *isl_mat_lin_to_aff(struct isl_mat *mat) | |||
| 673 | { | |||
| 674 | int i; | |||
| 675 | struct isl_mat *mat2; | |||
| 676 | ||||
| 677 | if (!mat) | |||
| 678 | return NULL((void*)0); | |||
| 679 | mat2 = isl_mat_alloc(mat->ctx, 1+mat->n_row, 1+mat->n_col); | |||
| 680 | if (!mat2) | |||
| 681 | goto error; | |||
| 682 | isl_int_set_si(mat2->row[0][0], 1)isl_sioimath_set_si((mat2->row[0][0]), 1); | |||
| 683 | isl_seq_clr(mat2->row[0]+1, mat->n_col); | |||
| 684 | for (i = 0; i < mat->n_row; ++i) { | |||
| 685 | isl_int_set_si(mat2->row[1+i][0], 0)isl_sioimath_set_si((mat2->row[1+i][0]), 0); | |||
| 686 | isl_seq_cpy(mat2->row[1+i]+1, mat->row[i], mat->n_col); | |||
| 687 | } | |||
| 688 | isl_mat_free(mat); | |||
| 689 | return mat2; | |||
| 690 | error: | |||
| 691 | isl_mat_free(mat); | |||
| 692 | return NULL((void*)0); | |||
| 693 | } | |||
| 694 | ||||
| 695 | /* Given two matrices M1 and M2, return the block matrix | |||
| 696 | * | |||
| 697 | * [ M1 0 ] | |||
| 698 | * [ 0 M2 ] | |||
| 699 | */ | |||
| 700 | __isl_give isl_mat *isl_mat_diagonal(__isl_take isl_mat *mat1, | |||
| 701 | __isl_take isl_mat *mat2) | |||
| 702 | { | |||
| 703 | int i; | |||
| 704 | isl_mat *mat; | |||
| 705 | ||||
| 706 | if (!mat1 || !mat2) | |||
| 707 | goto error; | |||
| 708 | ||||
| 709 | mat = isl_mat_alloc(mat1->ctx, mat1->n_row + mat2->n_row, | |||
| 710 | mat1->n_col + mat2->n_col); | |||
| 711 | if (!mat) | |||
| 712 | goto error; | |||
| 713 | for (i = 0; i < mat1->n_row; ++i) { | |||
| 714 | isl_seq_cpy(mat->row[i], mat1->row[i], mat1->n_col); | |||
| 715 | isl_seq_clr(mat->row[i] + mat1->n_col, mat2->n_col); | |||
| 716 | } | |||
| 717 | for (i = 0; i < mat2->n_row; ++i) { | |||
| 718 | isl_seq_clr(mat->row[mat1->n_row + i], mat1->n_col); | |||
| 719 | isl_seq_cpy(mat->row[mat1->n_row + i] + mat1->n_col, | |||
| 720 | mat2->row[i], mat2->n_col); | |||
| 721 | } | |||
| 722 | isl_mat_free(mat1); | |||
| 723 | isl_mat_free(mat2); | |||
| 724 | return mat; | |||
| 725 | error: | |||
| 726 | isl_mat_free(mat1); | |||
| 727 | isl_mat_free(mat2); | |||
| 728 | return NULL((void*)0); | |||
| 729 | } | |||
| 730 | ||||
| 731 | static int row_first_non_zero(isl_int **row, unsigned n_row, unsigned col) | |||
| 732 | { | |||
| 733 | int i; | |||
| 734 | ||||
| 735 | for (i = 0; i < n_row; ++i) | |||
| 736 | if (!isl_int_is_zero(row[i][col])(isl_sioimath_sgn(*(row[i][col])) == 0)) | |||
| 737 | return i; | |||
| 738 | return -1; | |||
| 739 | } | |||
| 740 | ||||
| 741 | static int row_abs_min_non_zero(isl_int **row, unsigned n_row, unsigned col) | |||
| 742 | { | |||
| 743 | int i, min = row_first_non_zero(row, n_row, col); | |||
| 744 | if (min < 0) | |||
| 745 | return -1; | |||
| 746 | for (i = min + 1; i < n_row; ++i) { | |||
| 747 | if (isl_int_is_zero(row[i][col])(isl_sioimath_sgn(*(row[i][col])) == 0)) | |||
| 748 | continue; | |||
| 749 | if (isl_int_abs_lt(row[i][col], row[min][col])(isl_sioimath_abs_cmp(*(row[i][col]), *(row[min][col])) < 0 )) | |||
| 750 | min = i; | |||
| 751 | } | |||
| 752 | return min; | |||
| 753 | } | |||
| 754 | ||||
| 755 | static void inv_exchange(struct isl_mat *left, struct isl_mat *right, | |||
| 756 | unsigned i, unsigned j) | |||
| 757 | { | |||
| 758 | left = isl_mat_swap_rows(left, i, j); | |||
| 759 | right = isl_mat_swap_rows(right, i, j); | |||
| 760 | } | |||
| 761 | ||||
| 762 | static void inv_oppose( | |||
| 763 | struct isl_mat *left, struct isl_mat *right, unsigned row) | |||
| 764 | { | |||
| 765 | isl_seq_neg(left->row[row]+row, left->row[row]+row, left->n_col-row); | |||
| 766 | isl_seq_neg(right->row[row], right->row[row], right->n_col); | |||
| 767 | } | |||
| 768 | ||||
| 769 | static void inv_subtract(struct isl_mat *left, struct isl_mat *right, | |||
| 770 | unsigned row, unsigned i, isl_int m) | |||
| 771 | { | |||
| 772 | isl_int_neg(m, m)isl_sioimath_neg((m), *(m)); | |||
| 773 | isl_seq_combine(left->row[i]+row, | |||
| 774 | left->ctx->one, left->row[i]+row, | |||
| 775 | m, left->row[row]+row, | |||
| 776 | left->n_col-row); | |||
| 777 | isl_seq_combine(right->row[i], right->ctx->one, right->row[i], | |||
| 778 | m, right->row[row], right->n_col); | |||
| 779 | } | |||
| 780 | ||||
| 781 | /* Compute inv(left)*right | |||
| 782 | */ | |||
| 783 | struct isl_mat *isl_mat_inverse_product(struct isl_mat *left, | |||
| 784 | struct isl_mat *right) | |||
| 785 | { | |||
| 786 | int row; | |||
| 787 | isl_int a, b; | |||
| 788 | ||||
| 789 | if (!left || !right) | |||
| 790 | goto error; | |||
| 791 | ||||
| 792 | isl_assert(left->ctx, left->n_row == left->n_col, goto error)do { if (left->n_row == left->n_col) break; do { isl_handle_error (left->ctx, isl_error_unknown, "Assertion \"" "left->n_row == left->n_col" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 792); goto error; } while (0); } while (0); | |||
| 793 | isl_assert(left->ctx, left->n_row == right->n_row, goto error)do { if (left->n_row == right->n_row) break; do { isl_handle_error (left->ctx, isl_error_unknown, "Assertion \"" "left->n_row == right->n_row" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 793); goto error; } while (0); } while (0); | |||
| 794 | ||||
| 795 | if (left->n_row == 0) { | |||
| 796 | isl_mat_free(left); | |||
| 797 | return right; | |||
| 798 | } | |||
| 799 | ||||
| 800 | left = isl_mat_cow(left); | |||
| 801 | right = isl_mat_cow(right); | |||
| 802 | if (!left || !right) | |||
| 803 | goto error; | |||
| 804 | ||||
| 805 | isl_int_init(a)isl_sioimath_init((a)); | |||
| 806 | isl_int_init(b)isl_sioimath_init((b)); | |||
| 807 | for (row = 0; row < left->n_row; ++row) { | |||
| 808 | int pivot, first, i, off; | |||
| 809 | pivot = row_abs_min_non_zero(left->row+row, left->n_row-row, row); | |||
| 810 | if (pivot < 0) { | |||
| 811 | isl_int_clear(a)isl_sioimath_clear((a)); | |||
| 812 | isl_int_clear(b)isl_sioimath_clear((b)); | |||
| 813 | isl_assert(left->ctx, pivot >= 0, goto error)do { if (pivot >= 0) break; do { isl_handle_error(left-> ctx, isl_error_unknown, "Assertion \"" "pivot >= 0" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 813); goto error; } while (0); } while (0); | |||
| 814 | } | |||
| 815 | pivot += row; | |||
| 816 | if (pivot != row) | |||
| 817 | inv_exchange(left, right, pivot, row); | |||
| 818 | if (isl_int_is_neg(left->row[row][row])(isl_sioimath_sgn(*(left->row[row][row])) < 0)) | |||
| 819 | inv_oppose(left, right, row); | |||
| 820 | first = row+1; | |||
| 821 | while ((off = row_first_non_zero(left->row+first, | |||
| 822 | left->n_row-first, row)) != -1) { | |||
| 823 | first += off; | |||
| 824 | isl_int_fdiv_q(a, left->row[first][row],isl_sioimath_fdiv_q((a), *(left->row[first][row]), *(left-> row[row][row])) | |||
| 825 | left->row[row][row])isl_sioimath_fdiv_q((a), *(left->row[first][row]), *(left-> row[row][row])); | |||
| 826 | inv_subtract(left, right, row, first, a); | |||
| 827 | if (!isl_int_is_zero(left->row[first][row])(isl_sioimath_sgn(*(left->row[first][row])) == 0)) | |||
| 828 | inv_exchange(left, right, row, first); | |||
| 829 | else | |||
| 830 | ++first; | |||
| 831 | } | |||
| 832 | for (i = 0; i < row; ++i) { | |||
| 833 | if (isl_int_is_zero(left->row[i][row])(isl_sioimath_sgn(*(left->row[i][row])) == 0)) | |||
| 834 | continue; | |||
| 835 | isl_int_gcd(a, left->row[row][row], left->row[i][row])isl_sioimath_gcd((a), *(left->row[row][row]), *(left->row [i][row])); | |||
| 836 | isl_int_divexact(b, left->row[i][row], a)isl_sioimath_tdiv_q((b), *(left->row[i][row]), *(a)); | |||
| 837 | isl_int_divexact(a, left->row[row][row], a)isl_sioimath_tdiv_q((a), *(left->row[row][row]), *(a)); | |||
| 838 | isl_int_neg(b, b)isl_sioimath_neg((b), *(b)); | |||
| 839 | isl_seq_combine(left->row[i] + i, | |||
| 840 | a, left->row[i] + i, | |||
| 841 | b, left->row[row] + i, | |||
| 842 | left->n_col - i); | |||
| 843 | isl_seq_combine(right->row[i], a, right->row[i], | |||
| 844 | b, right->row[row], right->n_col); | |||
| 845 | } | |||
| 846 | } | |||
| 847 | isl_int_clear(b)isl_sioimath_clear((b)); | |||
| 848 | ||||
| 849 | isl_int_set(a, left->row[0][0])isl_sioimath_set((a), *(left->row[0][0])); | |||
| 850 | for (row = 1; row < left->n_row; ++row) | |||
| 851 | isl_int_lcm(a, a, left->row[row][row])isl_sioimath_lcm((a), *(a), *(left->row[row][row])); | |||
| 852 | if (isl_int_is_zero(a)(isl_sioimath_sgn(*(a)) == 0)){ | |||
| 853 | isl_int_clear(a)isl_sioimath_clear((a)); | |||
| 854 | isl_assert(left->ctx, 0, goto error)do { if (0) break; do { isl_handle_error(left->ctx, isl_error_unknown , "Assertion \"" "0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 854); goto error; } while (0); } while (0); | |||
| 855 | } | |||
| 856 | for (row = 0; row < left->n_row; ++row) { | |||
| 857 | isl_int_divexact(left->row[row][row], a, left->row[row][row])isl_sioimath_tdiv_q((left->row[row][row]), *(a), *(left-> row[row][row])); | |||
| 858 | if (isl_int_is_one(left->row[row][row])(isl_sioimath_cmp_si(*(left->row[row][row]), 1) == 0)) | |||
| 859 | continue; | |||
| 860 | isl_seq_scale(right->row[row], right->row[row], | |||
| 861 | left->row[row][row], right->n_col); | |||
| 862 | } | |||
| 863 | isl_int_clear(a)isl_sioimath_clear((a)); | |||
| 864 | ||||
| 865 | isl_mat_free(left); | |||
| 866 | return right; | |||
| 867 | error: | |||
| 868 | isl_mat_free(left); | |||
| 869 | isl_mat_free(right); | |||
| 870 | return NULL((void*)0); | |||
| 871 | } | |||
| 872 | ||||
| 873 | void isl_mat_col_scale(struct isl_mat *mat, unsigned col, isl_int m) | |||
| 874 | { | |||
| 875 | int i; | |||
| 876 | ||||
| 877 | for (i = 0; i < mat->n_row; ++i) | |||
| 878 | isl_int_mul(mat->row[i][col], mat->row[i][col], m)isl_sioimath_mul((mat->row[i][col]), *(mat->row[i][col] ), *(m)); | |||
| 879 | } | |||
| 880 | ||||
| 881 | void isl_mat_col_combine(struct isl_mat *mat, unsigned dst, | |||
| 882 | isl_int m1, unsigned src1, isl_int m2, unsigned src2) | |||
| 883 | { | |||
| 884 | int i; | |||
| 885 | isl_int tmp; | |||
| 886 | ||||
| 887 | isl_int_init(tmp)isl_sioimath_init((tmp)); | |||
| 888 | for (i = 0; i < mat->n_row; ++i) { | |||
| 889 | isl_int_mul(tmp, m1, mat->row[i][src1])isl_sioimath_mul((tmp), *(m1), *(mat->row[i][src1])); | |||
| 890 | isl_int_addmul(tmp, m2, mat->row[i][src2])isl_sioimath_addmul((tmp), *(m2), *(mat->row[i][src2])); | |||
| 891 | isl_int_set(mat->row[i][dst], tmp)isl_sioimath_set((mat->row[i][dst]), *(tmp)); | |||
| 892 | } | |||
| 893 | isl_int_clear(tmp)isl_sioimath_clear((tmp)); | |||
| 894 | } | |||
| 895 | ||||
| 896 | struct isl_mat *isl_mat_right_inverse(struct isl_mat *mat) | |||
| 897 | { | |||
| 898 | struct isl_mat *inv; | |||
| 899 | int row; | |||
| 900 | isl_int a, b; | |||
| 901 | ||||
| 902 | mat = isl_mat_cow(mat); | |||
| 903 | if (!mat) | |||
| 904 | return NULL((void*)0); | |||
| 905 | ||||
| 906 | inv = isl_mat_identity(mat->ctx, mat->n_col); | |||
| 907 | inv = isl_mat_cow(inv); | |||
| 908 | if (!inv) | |||
| 909 | goto error; | |||
| 910 | ||||
| 911 | isl_int_init(a)isl_sioimath_init((a)); | |||
| 912 | isl_int_init(b)isl_sioimath_init((b)); | |||
| 913 | for (row = 0; row < mat->n_row; ++row) { | |||
| 914 | int pivot, first, i, off; | |||
| 915 | pivot = isl_seq_abs_min_non_zero(mat->row[row]+row, mat->n_col-row); | |||
| 916 | if (pivot < 0) { | |||
| 917 | isl_int_clear(a)isl_sioimath_clear((a)); | |||
| 918 | isl_int_clear(b)isl_sioimath_clear((b)); | |||
| 919 | isl_assert(mat->ctx, pivot >= 0, goto error)do { if (pivot >= 0) break; do { isl_handle_error(mat-> ctx, isl_error_unknown, "Assertion \"" "pivot >= 0" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 919); goto error; } while (0); } while (0); | |||
| 920 | } | |||
| 921 | pivot += row; | |||
| 922 | if (pivot != row) | |||
| 923 | exchange(mat, &inv, NULL((void*)0), row, pivot, row); | |||
| 924 | if (isl_int_is_neg(mat->row[row][row])(isl_sioimath_sgn(*(mat->row[row][row])) < 0)) | |||
| 925 | oppose(mat, &inv, NULL((void*)0), row, row); | |||
| 926 | first = row+1; | |||
| 927 | while ((off = isl_seq_first_non_zero(mat->row[row]+first, | |||
| 928 | mat->n_col-first)) != -1) { | |||
| 929 | first += off; | |||
| 930 | isl_int_fdiv_q(a, mat->row[row][first],isl_sioimath_fdiv_q((a), *(mat->row[row][first]), *(mat-> row[row][row])) | |||
| 931 | mat->row[row][row])isl_sioimath_fdiv_q((a), *(mat->row[row][first]), *(mat-> row[row][row])); | |||
| 932 | subtract(mat, &inv, NULL((void*)0), row, row, first, a); | |||
| 933 | if (!isl_int_is_zero(mat->row[row][first])(isl_sioimath_sgn(*(mat->row[row][first])) == 0)) | |||
| 934 | exchange(mat, &inv, NULL((void*)0), row, row, first); | |||
| 935 | else | |||
| 936 | ++first; | |||
| 937 | } | |||
| 938 | for (i = 0; i < row; ++i) { | |||
| 939 | if (isl_int_is_zero(mat->row[row][i])(isl_sioimath_sgn(*(mat->row[row][i])) == 0)) | |||
| 940 | continue; | |||
| 941 | isl_int_gcd(a, mat->row[row][row], mat->row[row][i])isl_sioimath_gcd((a), *(mat->row[row][row]), *(mat->row [row][i])); | |||
| 942 | isl_int_divexact(b, mat->row[row][i], a)isl_sioimath_tdiv_q((b), *(mat->row[row][i]), *(a)); | |||
| 943 | isl_int_divexact(a, mat->row[row][row], a)isl_sioimath_tdiv_q((a), *(mat->row[row][row]), *(a)); | |||
| 944 | isl_int_neg(a, a)isl_sioimath_neg((a), *(a)); | |||
| 945 | isl_mat_col_combine(mat, i, a, i, b, row); | |||
| 946 | isl_mat_col_combine(inv, i, a, i, b, row); | |||
| 947 | } | |||
| 948 | } | |||
| 949 | isl_int_clear(b)isl_sioimath_clear((b)); | |||
| 950 | ||||
| 951 | isl_int_set(a, mat->row[0][0])isl_sioimath_set((a), *(mat->row[0][0])); | |||
| 952 | for (row = 1; row < mat->n_row; ++row) | |||
| 953 | isl_int_lcm(a, a, mat->row[row][row])isl_sioimath_lcm((a), *(a), *(mat->row[row][row])); | |||
| 954 | if (isl_int_is_zero(a)(isl_sioimath_sgn(*(a)) == 0)){ | |||
| 955 | isl_int_clear(a)isl_sioimath_clear((a)); | |||
| 956 | goto error; | |||
| 957 | } | |||
| 958 | for (row = 0; row < mat->n_row; ++row) { | |||
| 959 | isl_int_divexact(mat->row[row][row], a, mat->row[row][row])isl_sioimath_tdiv_q((mat->row[row][row]), *(a), *(mat-> row[row][row])); | |||
| 960 | if (isl_int_is_one(mat->row[row][row])(isl_sioimath_cmp_si(*(mat->row[row][row]), 1) == 0)) | |||
| 961 | continue; | |||
| 962 | isl_mat_col_scale(inv, row, mat->row[row][row]); | |||
| 963 | } | |||
| 964 | isl_int_clear(a)isl_sioimath_clear((a)); | |||
| 965 | ||||
| 966 | isl_mat_free(mat); | |||
| 967 | ||||
| 968 | return inv; | |||
| 969 | error: | |||
| 970 | isl_mat_free(mat); | |||
| 971 | isl_mat_free(inv); | |||
| 972 | return NULL((void*)0); | |||
| 973 | } | |||
| 974 | ||||
| 975 | struct isl_mat *isl_mat_transpose(struct isl_mat *mat) | |||
| 976 | { | |||
| 977 | struct isl_mat *transpose = NULL((void*)0); | |||
| 978 | int i, j; | |||
| 979 | ||||
| 980 | if (!mat) | |||
| 981 | return NULL((void*)0); | |||
| 982 | ||||
| 983 | if (mat->n_col == mat->n_row) { | |||
| 984 | mat = isl_mat_cow(mat); | |||
| 985 | if (!mat) | |||
| 986 | return NULL((void*)0); | |||
| 987 | for (i = 0; i < mat->n_row; ++i) | |||
| 988 | for (j = i + 1; j < mat->n_col; ++j) | |||
| 989 | isl_int_swap(mat->row[i][j], mat->row[j][i])isl_sioimath_swap((mat->row[i][j]), (mat->row[j][i])); | |||
| 990 | return mat; | |||
| 991 | } | |||
| 992 | transpose = isl_mat_alloc(mat->ctx, mat->n_col, mat->n_row); | |||
| 993 | if (!transpose) | |||
| 994 | goto error; | |||
| 995 | for (i = 0; i < mat->n_row; ++i) | |||
| 996 | for (j = 0; j < mat->n_col; ++j) | |||
| 997 | isl_int_set(transpose->row[j][i], mat->row[i][j])isl_sioimath_set((transpose->row[j][i]), *(mat->row[i][ j])); | |||
| 998 | isl_mat_free(mat); | |||
| 999 | return transpose; | |||
| 1000 | error: | |||
| 1001 | isl_mat_free(mat); | |||
| 1002 | return NULL((void*)0); | |||
| 1003 | } | |||
| 1004 | ||||
| 1005 | struct isl_mat *isl_mat_swap_cols(struct isl_mat *mat, unsigned i, unsigned j) | |||
| 1006 | { | |||
| 1007 | int r; | |||
| 1008 | ||||
| 1009 | mat = isl_mat_cow(mat); | |||
| 1010 | if (!mat) | |||
| 1011 | return NULL((void*)0); | |||
| 1012 | isl_assert(mat->ctx, i < mat->n_col, goto error)do { if (i < mat->n_col) break; do { isl_handle_error(mat ->ctx, isl_error_unknown, "Assertion \"" "i < mat->n_col" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1012); goto error; } while (0); } while (0); | |||
| 1013 | isl_assert(mat->ctx, j < mat->n_col, goto error)do { if (j < mat->n_col) break; do { isl_handle_error(mat ->ctx, isl_error_unknown, "Assertion \"" "j < mat->n_col" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1013); goto error; } while (0); } while (0); | |||
| 1014 | ||||
| 1015 | for (r = 0; r < mat->n_row; ++r) | |||
| 1016 | isl_int_swap(mat->row[r][i], mat->row[r][j])isl_sioimath_swap((mat->row[r][i]), (mat->row[r][j])); | |||
| 1017 | return mat; | |||
| 1018 | error: | |||
| 1019 | isl_mat_free(mat); | |||
| 1020 | return NULL((void*)0); | |||
| 1021 | } | |||
| 1022 | ||||
| 1023 | struct isl_mat *isl_mat_swap_rows(struct isl_mat *mat, unsigned i, unsigned j) | |||
| 1024 | { | |||
| 1025 | isl_int *t; | |||
| 1026 | ||||
| 1027 | if (!mat) | |||
| 1028 | return NULL((void*)0); | |||
| 1029 | mat = isl_mat_cow(mat); | |||
| 1030 | if (!mat) | |||
| 1031 | return NULL((void*)0); | |||
| 1032 | t = mat->row[i]; | |||
| 1033 | mat->row[i] = mat->row[j]; | |||
| 1034 | mat->row[j] = t; | |||
| 1035 | return mat; | |||
| 1036 | } | |||
| 1037 | ||||
| 1038 | /* Calculate the product of two matrices. | |||
| 1039 | * | |||
| 1040 | * This function is optimized for operand matrices that contain many zeros and | |||
| 1041 | * skips multiplications where we know one of the operands is zero. | |||
| 1042 | */ | |||
| 1043 | __isl_give isl_mat *isl_mat_product(__isl_take isl_mat *left, | |||
| 1044 | __isl_take isl_mat *right) | |||
| 1045 | { | |||
| 1046 | int i, j, k; | |||
| 1047 | struct isl_mat *prod; | |||
| 1048 | ||||
| 1049 | if (!left || !right) | |||
| 1050 | goto error; | |||
| 1051 | isl_assert(left->ctx, left->n_col == right->n_row, goto error)do { if (left->n_col == right->n_row) break; do { isl_handle_error (left->ctx, isl_error_unknown, "Assertion \"" "left->n_col == right->n_row" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1051); goto error; } while (0); } while (0); | |||
| 1052 | prod = isl_mat_alloc(left->ctx, left->n_row, right->n_col); | |||
| 1053 | if (!prod) | |||
| 1054 | goto error; | |||
| 1055 | if (left->n_col == 0) { | |||
| 1056 | for (i = 0; i < prod->n_row; ++i) | |||
| 1057 | isl_seq_clr(prod->row[i], prod->n_col); | |||
| 1058 | isl_mat_free(left); | |||
| 1059 | isl_mat_free(right); | |||
| 1060 | return prod; | |||
| 1061 | } | |||
| 1062 | for (i = 0; i < prod->n_row; ++i) { | |||
| 1063 | for (j = 0; j < prod->n_col; ++j) | |||
| 1064 | isl_int_mul(prod->row[i][j],isl_sioimath_mul((prod->row[i][j]), *(left->row[i][0]), *(right->row[0][j])) | |||
| 1065 | left->row[i][0], right->row[0][j])isl_sioimath_mul((prod->row[i][j]), *(left->row[i][0]), *(right->row[0][j])); | |||
| 1066 | for (k = 1; k < left->n_col; ++k) { | |||
| 1067 | if (isl_int_is_zero(left->row[i][k])(isl_sioimath_sgn(*(left->row[i][k])) == 0)) | |||
| 1068 | continue; | |||
| 1069 | for (j = 0; j < prod->n_col; ++j) | |||
| 1070 | isl_int_addmul(prod->row[i][j],isl_sioimath_addmul((prod->row[i][j]), *(left->row[i][k ]), *(right->row[k][j])) | |||
| 1071 | left->row[i][k], right->row[k][j])isl_sioimath_addmul((prod->row[i][j]), *(left->row[i][k ]), *(right->row[k][j])); | |||
| 1072 | } | |||
| 1073 | } | |||
| 1074 | isl_mat_free(left); | |||
| 1075 | isl_mat_free(right); | |||
| 1076 | return prod; | |||
| 1077 | error: | |||
| 1078 | isl_mat_free(left); | |||
| 1079 | isl_mat_free(right); | |||
| 1080 | return NULL((void*)0); | |||
| 1081 | } | |||
| 1082 | ||||
| 1083 | /* Replace the variables x in the rows q by x' given by x = M x', | |||
| 1084 | * with M the matrix mat. | |||
| 1085 | * | |||
| 1086 | * If the number of new variables is greater than the original | |||
| 1087 | * number of variables, then the rows q have already been | |||
| 1088 | * preextended. If the new number is smaller, then the coefficients | |||
| 1089 | * of the divs, which are not changed, need to be shifted down. | |||
| 1090 | * The row q may be the equalities, the inequalities or the | |||
| 1091 | * div expressions. In the latter case, has_div is true and | |||
| 1092 | * we need to take into account the extra denominator column. | |||
| 1093 | */ | |||
| 1094 | static int preimage(struct isl_ctx *ctx, isl_int **q, unsigned n, | |||
| 1095 | unsigned n_div, int has_div, struct isl_mat *mat) | |||
| 1096 | { | |||
| 1097 | int i; | |||
| 1098 | struct isl_mat *t; | |||
| 1099 | int e; | |||
| 1100 | ||||
| 1101 | if (mat->n_col >= mat->n_row) | |||
| 1102 | e = 0; | |||
| 1103 | else | |||
| 1104 | e = mat->n_row - mat->n_col; | |||
| 1105 | if (has_div) | |||
| 1106 | for (i = 0; i < n; ++i) | |||
| 1107 | isl_int_mul(q[i][0], q[i][0], mat->row[0][0])isl_sioimath_mul((q[i][0]), *(q[i][0]), *(mat->row[0][0])); | |||
| 1108 | t = isl_mat_sub_alloc6(mat->ctx, q, 0, n, has_div, mat->n_row); | |||
| 1109 | t = isl_mat_product(t, mat); | |||
| 1110 | if (!t) | |||
| 1111 | return -1; | |||
| 1112 | for (i = 0; i < n; ++i) { | |||
| 1113 | isl_seq_swp_or_cpy(q[i] + has_div, t->row[i], t->n_col); | |||
| 1114 | isl_seq_cpy(q[i] + has_div + t->n_col, | |||
| 1115 | q[i] + has_div + t->n_col + e, n_div); | |||
| 1116 | isl_seq_clr(q[i] + has_div + t->n_col + n_div, e); | |||
| 1117 | } | |||
| 1118 | isl_mat_free(t); | |||
| 1119 | return 0; | |||
| 1120 | } | |||
| 1121 | ||||
| 1122 | /* Replace the variables x in bset by x' given by x = M x', with | |||
| 1123 | * M the matrix mat. | |||
| 1124 | * | |||
| 1125 | * If there are fewer variables x' then there are x, then we perform | |||
| 1126 | * the transformation in place, which that, in principle, | |||
| 1127 | * this frees up some extra variables as the number | |||
| 1128 | * of columns remains constant, but we would have to extend | |||
| 1129 | * the div array too as the number of rows in this array is assumed | |||
| 1130 | * to be equal to extra. | |||
| 1131 | */ | |||
| 1132 | struct isl_basic_setisl_basic_map *isl_basic_set_preimage(struct isl_basic_setisl_basic_map *bset, | |||
| 1133 | struct isl_mat *mat) | |||
| 1134 | { | |||
| 1135 | struct isl_ctx *ctx; | |||
| 1136 | ||||
| 1137 | if (!bset || !mat) | |||
| 1138 | goto error; | |||
| 1139 | ||||
| 1140 | ctx = bset->ctx; | |||
| 1141 | bset = isl_basic_set_cow(bset); | |||
| 1142 | if (!bset) | |||
| 1143 | goto error; | |||
| 1144 | ||||
| 1145 | isl_assert(ctx, bset->dim->nparam == 0, goto error)do { if (bset->dim->nparam == 0) break; do { isl_handle_error (ctx, isl_error_unknown, "Assertion \"" "bset->dim->nparam == 0" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1145); goto error; } while (0); } while (0); | |||
| 1146 | isl_assert(ctx, 1+bset->dim->n_out == mat->n_row, goto error)do { if (1+bset->dim->n_out == mat->n_row) break; do { isl_handle_error(ctx, isl_error_unknown, "Assertion \"" "1+bset->dim->n_out == mat->n_row" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1146); goto error; } while (0); } while (0); | |||
| 1147 | isl_assert(ctx, mat->n_col > 0, goto error)do { if (mat->n_col > 0) break; do { isl_handle_error(ctx , isl_error_unknown, "Assertion \"" "mat->n_col > 0" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1147); goto error; } while (0); } while (0); | |||
| 1148 | ||||
| 1149 | if (mat->n_col > mat->n_row) { | |||
| 1150 | bset = isl_basic_set_extend(bset, 0, mat->n_col-1, 0, 0, 0); | |||
| 1151 | if (!bset) | |||
| 1152 | goto error; | |||
| 1153 | } else if (mat->n_col < mat->n_row) { | |||
| 1154 | bset->dim = isl_space_cow(bset->dim); | |||
| 1155 | if (!bset->dim) | |||
| 1156 | goto error; | |||
| 1157 | bset->dim->n_out -= mat->n_row - mat->n_col; | |||
| 1158 | } | |||
| 1159 | ||||
| 1160 | if (preimage(ctx, bset->eq, bset->n_eq, bset->n_div, 0, | |||
| 1161 | isl_mat_copy(mat)) < 0) | |||
| 1162 | goto error; | |||
| 1163 | ||||
| 1164 | if (preimage(ctx, bset->ineq, bset->n_ineq, bset->n_div, 0, | |||
| 1165 | isl_mat_copy(mat)) < 0) | |||
| 1166 | goto error; | |||
| 1167 | ||||
| 1168 | if (preimage(ctx, bset->div, bset->n_div, bset->n_div, 1, mat) < 0) | |||
| 1169 | goto error2; | |||
| 1170 | ||||
| 1171 | ISL_F_CLR(bset, ISL_BASIC_SET_NO_IMPLICIT)(((bset)->flags) &= ~((1 << 2))); | |||
| 1172 | ISL_F_CLR(bset, ISL_BASIC_SET_NO_REDUNDANT)(((bset)->flags) &= ~((1 << 3))); | |||
| 1173 | ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED)(((bset)->flags) &= ~((1 << 5))); | |||
| 1174 | ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED_DIVS)(((bset)->flags) &= ~((1 << 6))); | |||
| 1175 | ISL_F_CLR(bset, ISL_BASIC_SET_ALL_EQUALITIES)(((bset)->flags) &= ~((1 << 7))); | |||
| 1176 | ||||
| 1177 | bset = isl_basic_set_simplify(bset); | |||
| 1178 | bset = isl_basic_set_finalize(bset); | |||
| 1179 | ||||
| 1180 | return bset; | |||
| 1181 | error: | |||
| 1182 | isl_mat_free(mat); | |||
| 1183 | error2: | |||
| 1184 | isl_basic_set_free(bset); | |||
| 1185 | return NULL((void*)0); | |||
| 1186 | } | |||
| 1187 | ||||
| 1188 | struct isl_setisl_map *isl_set_preimage(struct isl_setisl_map *set, struct isl_mat *mat) | |||
| 1189 | { | |||
| 1190 | int i; | |||
| 1191 | ||||
| 1192 | set = isl_set_cow(set); | |||
| 1193 | if (!set) | |||
| 1194 | return NULL((void*)0); | |||
| 1195 | ||||
| 1196 | for (i = 0; i < set->n; ++i) { | |||
| 1197 | set->p[i] = isl_basic_set_preimage(set->p[i], | |||
| 1198 | isl_mat_copy(mat)); | |||
| 1199 | if (!set->p[i]) | |||
| 1200 | goto error; | |||
| 1201 | } | |||
| 1202 | if (mat->n_col != mat->n_row) { | |||
| 1203 | set->dim = isl_space_cow(set->dim); | |||
| 1204 | if (!set->dim) | |||
| 1205 | goto error; | |||
| 1206 | set->dim->n_out += mat->n_col; | |||
| 1207 | set->dim->n_out -= mat->n_row; | |||
| 1208 | } | |||
| 1209 | isl_mat_free(mat); | |||
| 1210 | ISL_F_CLR(set, ISL_SET_NORMALIZED)(((set)->flags) &= ~((1 << 1))); | |||
| 1211 | return set; | |||
| 1212 | error: | |||
| 1213 | isl_set_free(set); | |||
| 1214 | isl_mat_free(mat); | |||
| 1215 | return NULL((void*)0); | |||
| 1216 | } | |||
| 1217 | ||||
| 1218 | /* Replace the variables x starting at pos in the rows q | |||
| 1219 | * by x' with x = M x' with M the matrix mat. | |||
| 1220 | * That is, replace the corresponding coefficients c by c M. | |||
| 1221 | */ | |||
| 1222 | static int transform(isl_ctx *ctx, isl_int **q, unsigned n, | |||
| 1223 | unsigned pos, __isl_take isl_mat *mat) | |||
| 1224 | { | |||
| 1225 | int i; | |||
| 1226 | isl_mat *t; | |||
| 1227 | ||||
| 1228 | t = isl_mat_sub_alloc6(ctx, q, 0, n, pos, mat->n_row); | |||
| 1229 | t = isl_mat_product(t, mat); | |||
| 1230 | if (!t) | |||
| 1231 | return -1; | |||
| 1232 | for (i = 0; i < n; ++i) | |||
| 1233 | isl_seq_swp_or_cpy(q[i] + pos, t->row[i], t->n_col); | |||
| 1234 | isl_mat_free(t); | |||
| 1235 | return 0; | |||
| 1236 | } | |||
| 1237 | ||||
| 1238 | /* Replace the variables x of type "type" starting at "first" in "bset" | |||
| 1239 | * by x' with x = M x' with M the matrix trans. | |||
| 1240 | * That is, replace the corresponding coefficients c by c M. | |||
| 1241 | * | |||
| 1242 | * The transformation matrix should be a square matrix. | |||
| 1243 | */ | |||
| 1244 | __isl_give isl_basic_setisl_basic_map *isl_basic_set_transform_dims( | |||
| 1245 | __isl_take isl_basic_setisl_basic_map *bset, enum isl_dim_type type, unsigned first, | |||
| 1246 | __isl_take isl_mat *trans) | |||
| 1247 | { | |||
| 1248 | isl_ctx *ctx; | |||
| 1249 | unsigned pos; | |||
| 1250 | ||||
| 1251 | bset = isl_basic_set_cow(bset); | |||
| 1252 | if (!bset || !trans) | |||
| ||||
| 1253 | goto error; | |||
| 1254 | ||||
| 1255 | ctx = isl_basic_set_get_ctx(bset); | |||
| 1256 | if (trans->n_row != trans->n_col) | |||
| 1257 | isl_die(trans->ctx, isl_error_invalid,do { isl_handle_error(trans->ctx, isl_error_invalid, "expecting square transformation matrix" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1258); goto error; } while (0) | |||
| 1258 | "expecting square transformation matrix", goto error)do { isl_handle_error(trans->ctx, isl_error_invalid, "expecting square transformation matrix" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1258); goto error; } while (0); | |||
| 1259 | if (first + trans->n_row > isl_basic_set_dim(bset, type)) | |||
| 1260 | isl_die(trans->ctx, isl_error_invalid,do { isl_handle_error(trans->ctx, isl_error_invalid, "oversized transformation matrix" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1261); goto error; } while (0) | |||
| 1261 | "oversized transformation matrix", goto error)do { isl_handle_error(trans->ctx, isl_error_invalid, "oversized transformation matrix" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1261); goto error; } while (0); | |||
| 1262 | ||||
| 1263 | pos = isl_basic_set_offset(bset, type) + first; | |||
| 1264 | ||||
| 1265 | if (transform(ctx, bset->eq, bset->n_eq, pos, isl_mat_copy(trans)) < 0) | |||
| 1266 | goto error; | |||
| 1267 | if (transform(ctx, bset->ineq, bset->n_ineq, pos, | |||
| 1268 | isl_mat_copy(trans)) < 0) | |||
| 1269 | goto error; | |||
| 1270 | if (transform(ctx, bset->div, bset->n_div, 1 + pos, | |||
| 1271 | isl_mat_copy(trans)) < 0) | |||
| 1272 | goto error; | |||
| 1273 | ||||
| 1274 | ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED)(((bset)->flags) &= ~((1 << 5))); | |||
| 1275 | ISL_F_CLR(bset, ISL_BASIC_SET_NORMALIZED_DIVS)(((bset)->flags) &= ~((1 << 6))); | |||
| 1276 | ||||
| 1277 | isl_mat_free(trans); | |||
| 1278 | return bset; | |||
| 1279 | error: | |||
| 1280 | isl_mat_free(trans); | |||
| ||||
| 1281 | isl_basic_set_free(bset); | |||
| 1282 | return NULL((void*)0); | |||
| 1283 | } | |||
| 1284 | ||||
| 1285 | void isl_mat_print_internal(__isl_keep isl_mat *mat, FILE *out, int indent) | |||
| 1286 | { | |||
| 1287 | int i, j; | |||
| 1288 | ||||
| 1289 | if (!mat) { | |||
| 1290 | fprintf(out, "%*snull mat\n", indent, "")__fprintf_chk (out, 2 - 1, "%*snull mat\n", indent, ""); | |||
| 1291 | return; | |||
| 1292 | } | |||
| 1293 | ||||
| 1294 | if (mat->n_row == 0) | |||
| 1295 | fprintf(out, "%*s[]\n", indent, "")__fprintf_chk (out, 2 - 1, "%*s[]\n", indent, ""); | |||
| 1296 | ||||
| 1297 | for (i = 0; i < mat->n_row; ++i) { | |||
| 1298 | if (!i) | |||
| 1299 | fprintf(out, "%*s[[", indent, "")__fprintf_chk (out, 2 - 1, "%*s[[", indent, ""); | |||
| 1300 | else | |||
| 1301 | fprintf(out, "%*s[", indent+1, "")__fprintf_chk (out, 2 - 1, "%*s[", indent+1, ""); | |||
| 1302 | for (j = 0; j < mat->n_col; ++j) { | |||
| 1303 | if (j) | |||
| 1304 | fprintf(out, ",")__fprintf_chk (out, 2 - 1, ","); | |||
| 1305 | isl_int_print(out, mat->row[i][j], 0)isl_sioimath_print(out, *(mat->row[i][j]), 0); | |||
| 1306 | } | |||
| 1307 | if (i == mat->n_row-1) | |||
| 1308 | fprintf(out, "]]\n")__fprintf_chk (out, 2 - 1, "]]\n"); | |||
| 1309 | else | |||
| 1310 | fprintf(out, "]\n")__fprintf_chk (out, 2 - 1, "]\n"); | |||
| 1311 | } | |||
| 1312 | } | |||
| 1313 | ||||
| 1314 | void isl_mat_dump(__isl_keep isl_mat *mat) | |||
| 1315 | { | |||
| 1316 | isl_mat_print_internal(mat, stderrstderr, 0); | |||
| 1317 | } | |||
| 1318 | ||||
| 1319 | struct isl_mat *isl_mat_drop_cols(struct isl_mat *mat, unsigned col, unsigned n) | |||
| 1320 | { | |||
| 1321 | int r; | |||
| 1322 | ||||
| 1323 | if (n == 0) | |||
| 1324 | return mat; | |||
| 1325 | ||||
| 1326 | mat = isl_mat_cow(mat); | |||
| 1327 | if (!mat) | |||
| 1328 | return NULL((void*)0); | |||
| 1329 | ||||
| 1330 | if (col != mat->n_col-n) { | |||
| 1331 | for (r = 0; r < mat->n_row; ++r) | |||
| 1332 | isl_seq_cpy(mat->row[r]+col, mat->row[r]+col+n, | |||
| 1333 | mat->n_col - col - n); | |||
| 1334 | } | |||
| 1335 | mat->n_col -= n; | |||
| 1336 | return mat; | |||
| 1337 | } | |||
| 1338 | ||||
| 1339 | struct isl_mat *isl_mat_drop_rows(struct isl_mat *mat, unsigned row, unsigned n) | |||
| 1340 | { | |||
| 1341 | int r; | |||
| 1342 | ||||
| 1343 | mat = isl_mat_cow(mat); | |||
| 1344 | if (!mat) | |||
| 1345 | return NULL((void*)0); | |||
| 1346 | ||||
| 1347 | for (r = row; r+n < mat->n_row; ++r) | |||
| 1348 | mat->row[r] = mat->row[r+n]; | |||
| 1349 | ||||
| 1350 | mat->n_row -= n; | |||
| 1351 | return mat; | |||
| 1352 | } | |||
| 1353 | ||||
| 1354 | __isl_give isl_mat *isl_mat_insert_cols(__isl_take isl_mat *mat, | |||
| 1355 | unsigned col, unsigned n) | |||
| 1356 | { | |||
| 1357 | isl_mat *ext; | |||
| 1358 | ||||
| 1359 | if (!mat) | |||
| 1360 | return NULL((void*)0); | |||
| 1361 | if (n == 0) | |||
| 1362 | return mat; | |||
| 1363 | ||||
| 1364 | ext = isl_mat_alloc(mat->ctx, mat->n_row, mat->n_col + n); | |||
| 1365 | if (!ext) | |||
| 1366 | goto error; | |||
| 1367 | ||||
| 1368 | isl_mat_sub_copy(mat->ctx, ext->row, mat->row, mat->n_row, 0, 0, col); | |||
| 1369 | isl_mat_sub_copy(mat->ctx, ext->row, mat->row, mat->n_row, | |||
| 1370 | col + n, col, mat->n_col - col); | |||
| 1371 | ||||
| 1372 | isl_mat_free(mat); | |||
| 1373 | return ext; | |||
| 1374 | error: | |||
| 1375 | isl_mat_free(mat); | |||
| 1376 | return NULL((void*)0); | |||
| 1377 | } | |||
| 1378 | ||||
| 1379 | __isl_give isl_mat *isl_mat_insert_zero_cols(__isl_take isl_mat *mat, | |||
| 1380 | unsigned first, unsigned n) | |||
| 1381 | { | |||
| 1382 | int i; | |||
| 1383 | ||||
| 1384 | if (!mat) | |||
| 1385 | return NULL((void*)0); | |||
| 1386 | mat = isl_mat_insert_cols(mat, first, n); | |||
| 1387 | if (!mat) | |||
| 1388 | return NULL((void*)0); | |||
| 1389 | ||||
| 1390 | for (i = 0; i < mat->n_row; ++i) | |||
| 1391 | isl_seq_clr(mat->row[i] + first, n); | |||
| 1392 | ||||
| 1393 | return mat; | |||
| 1394 | } | |||
| 1395 | ||||
| 1396 | __isl_give isl_mat *isl_mat_add_zero_cols(__isl_take isl_mat *mat, unsigned n) | |||
| 1397 | { | |||
| 1398 | if (!mat) | |||
| 1399 | return NULL((void*)0); | |||
| 1400 | ||||
| 1401 | return isl_mat_insert_zero_cols(mat, mat->n_col, n); | |||
| 1402 | } | |||
| 1403 | ||||
| 1404 | __isl_give isl_mat *isl_mat_insert_rows(__isl_take isl_mat *mat, | |||
| 1405 | unsigned row, unsigned n) | |||
| 1406 | { | |||
| 1407 | isl_mat *ext; | |||
| 1408 | ||||
| 1409 | if (!mat) | |||
| 1410 | return NULL((void*)0); | |||
| 1411 | if (n == 0) | |||
| 1412 | return mat; | |||
| 1413 | ||||
| 1414 | ext = isl_mat_alloc(mat->ctx, mat->n_row + n, mat->n_col); | |||
| 1415 | if (!ext) | |||
| 1416 | goto error; | |||
| 1417 | ||||
| 1418 | isl_mat_sub_copy(mat->ctx, ext->row, mat->row, row, 0, 0, mat->n_col); | |||
| 1419 | isl_mat_sub_copy(mat->ctx, ext->row + row + n, mat->row + row, | |||
| 1420 | mat->n_row - row, 0, 0, mat->n_col); | |||
| 1421 | ||||
| 1422 | isl_mat_free(mat); | |||
| 1423 | return ext; | |||
| 1424 | error: | |||
| 1425 | isl_mat_free(mat); | |||
| 1426 | return NULL((void*)0); | |||
| 1427 | } | |||
| 1428 | ||||
| 1429 | __isl_give isl_mat *isl_mat_add_rows(__isl_take isl_mat *mat, unsigned n) | |||
| 1430 | { | |||
| 1431 | if (!mat) | |||
| 1432 | return NULL((void*)0); | |||
| 1433 | ||||
| 1434 | return isl_mat_insert_rows(mat, mat->n_row, n); | |||
| 1435 | } | |||
| 1436 | ||||
| 1437 | __isl_give isl_mat *isl_mat_insert_zero_rows(__isl_take isl_mat *mat, | |||
| 1438 | unsigned row, unsigned n) | |||
| 1439 | { | |||
| 1440 | int i; | |||
| 1441 | ||||
| 1442 | mat = isl_mat_insert_rows(mat, row, n); | |||
| 1443 | if (!mat) | |||
| 1444 | return NULL((void*)0); | |||
| 1445 | ||||
| 1446 | for (i = 0; i < n; ++i) | |||
| 1447 | isl_seq_clr(mat->row[row + i], mat->n_col); | |||
| 1448 | ||||
| 1449 | return mat; | |||
| 1450 | } | |||
| 1451 | ||||
| 1452 | __isl_give isl_mat *isl_mat_add_zero_rows(__isl_take isl_mat *mat, unsigned n) | |||
| 1453 | { | |||
| 1454 | if (!mat) | |||
| 1455 | return NULL((void*)0); | |||
| 1456 | ||||
| 1457 | return isl_mat_insert_zero_rows(mat, mat->n_row, n); | |||
| 1458 | } | |||
| 1459 | ||||
| 1460 | void isl_mat_col_submul(struct isl_mat *mat, | |||
| 1461 | int dst_col, isl_int f, int src_col) | |||
| 1462 | { | |||
| 1463 | int i; | |||
| 1464 | ||||
| 1465 | for (i = 0; i < mat->n_row; ++i) | |||
| 1466 | isl_int_submul(mat->row[i][dst_col], f, mat->row[i][src_col])isl_sioimath_submul((mat->row[i][dst_col]), *(f), *(mat-> row[i][src_col])); | |||
| 1467 | } | |||
| 1468 | ||||
| 1469 | void isl_mat_col_add(__isl_keep isl_mat *mat, int dst_col, int src_col) | |||
| 1470 | { | |||
| 1471 | int i; | |||
| 1472 | ||||
| 1473 | if (!mat) | |||
| 1474 | return; | |||
| 1475 | ||||
| 1476 | for (i = 0; i < mat->n_row; ++i) | |||
| 1477 | isl_int_add(mat->row[i][dst_col],isl_sioimath_add((mat->row[i][dst_col]), *(mat->row[i][ dst_col]), *(mat->row[i][src_col])) | |||
| 1478 | mat->row[i][dst_col], mat->row[i][src_col])isl_sioimath_add((mat->row[i][dst_col]), *(mat->row[i][ dst_col]), *(mat->row[i][src_col])); | |||
| 1479 | } | |||
| 1480 | ||||
| 1481 | void isl_mat_col_mul(struct isl_mat *mat, int dst_col, isl_int f, int src_col) | |||
| 1482 | { | |||
| 1483 | int i; | |||
| 1484 | ||||
| 1485 | for (i = 0; i < mat->n_row; ++i) | |||
| 1486 | isl_int_mul(mat->row[i][dst_col], f, mat->row[i][src_col])isl_sioimath_mul((mat->row[i][dst_col]), *(f), *(mat->row [i][src_col])); | |||
| 1487 | } | |||
| 1488 | ||||
| 1489 | struct isl_mat *isl_mat_unimodular_complete(struct isl_mat *M, int row) | |||
| 1490 | { | |||
| 1491 | int r; | |||
| 1492 | struct isl_mat *H = NULL((void*)0), *Q = NULL((void*)0); | |||
| 1493 | ||||
| 1494 | if (!M) | |||
| 1495 | return NULL((void*)0); | |||
| 1496 | ||||
| 1497 | isl_assert(M->ctx, M->n_row == M->n_col, goto error)do { if (M->n_row == M->n_col) break; do { isl_handle_error (M->ctx, isl_error_unknown, "Assertion \"" "M->n_row == M->n_col" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1497); goto error; } while (0); } while (0); | |||
| 1498 | M->n_row = row; | |||
| 1499 | H = isl_mat_left_hermite(isl_mat_copy(M), 0, NULL((void*)0), &Q); | |||
| 1500 | M->n_row = M->n_col; | |||
| 1501 | if (!H) | |||
| 1502 | goto error; | |||
| 1503 | for (r = 0; r < row; ++r) | |||
| 1504 | isl_assert(M->ctx, isl_int_is_one(H->row[r][r]), goto error)do { if ((isl_sioimath_cmp_si(*(H->row[r][r]), 1) == 0)) break ; do { isl_handle_error(M->ctx, isl_error_unknown, "Assertion \"" "(isl_sioimath_cmp_si(*(H->row[r][r]), 1) == 0)" "\" failed" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1504); goto error; } while (0); } while (0); | |||
| 1505 | for (r = row; r < M->n_row; ++r) | |||
| 1506 | isl_seq_cpy(M->row[r], Q->row[r], M->n_col); | |||
| 1507 | isl_mat_free(H); | |||
| 1508 | isl_mat_free(Q); | |||
| 1509 | return M; | |||
| 1510 | error: | |||
| 1511 | isl_mat_free(H); | |||
| 1512 | isl_mat_free(Q); | |||
| 1513 | isl_mat_free(M); | |||
| 1514 | return NULL((void*)0); | |||
| 1515 | } | |||
| 1516 | ||||
| 1517 | __isl_give isl_mat *isl_mat_concat(__isl_take isl_mat *top, | |||
| 1518 | __isl_take isl_mat *bot) | |||
| 1519 | { | |||
| 1520 | struct isl_mat *mat; | |||
| 1521 | ||||
| 1522 | if (!top || !bot) | |||
| 1523 | goto error; | |||
| 1524 | ||||
| 1525 | isl_assert(top->ctx, top->n_col == bot->n_col, goto error)do { if (top->n_col == bot->n_col) break; do { isl_handle_error (top->ctx, isl_error_unknown, "Assertion \"" "top->n_col == bot->n_col" "\" failed", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1525); goto error; } while (0); } while (0); | |||
| 1526 | if (top->n_row == 0) { | |||
| 1527 | isl_mat_free(top); | |||
| 1528 | return bot; | |||
| 1529 | } | |||
| 1530 | if (bot->n_row == 0) { | |||
| 1531 | isl_mat_free(bot); | |||
| 1532 | return top; | |||
| 1533 | } | |||
| 1534 | ||||
| 1535 | mat = isl_mat_alloc(top->ctx, top->n_row + bot->n_row, top->n_col); | |||
| 1536 | if (!mat) | |||
| 1537 | goto error; | |||
| 1538 | isl_mat_sub_copy(mat->ctx, mat->row, top->row, top->n_row, | |||
| 1539 | 0, 0, mat->n_col); | |||
| 1540 | isl_mat_sub_copy(mat->ctx, mat->row + top->n_row, bot->row, bot->n_row, | |||
| 1541 | 0, 0, mat->n_col); | |||
| 1542 | isl_mat_free(top); | |||
| 1543 | isl_mat_free(bot); | |||
| 1544 | return mat; | |||
| 1545 | error: | |||
| 1546 | isl_mat_free(top); | |||
| 1547 | isl_mat_free(bot); | |||
| 1548 | return NULL((void*)0); | |||
| 1549 | } | |||
| 1550 | ||||
| 1551 | int isl_mat_is_equal(__isl_keep isl_mat *mat1, __isl_keep isl_mat *mat2) | |||
| 1552 | { | |||
| 1553 | int i; | |||
| 1554 | ||||
| 1555 | if (!mat1 || !mat2) | |||
| 1556 | return -1; | |||
| 1557 | ||||
| 1558 | if (mat1->n_row != mat2->n_row) | |||
| 1559 | return 0; | |||
| 1560 | ||||
| 1561 | if (mat1->n_col != mat2->n_col) | |||
| 1562 | return 0; | |||
| 1563 | ||||
| 1564 | for (i = 0; i < mat1->n_row; ++i) | |||
| 1565 | if (!isl_seq_eq(mat1->row[i], mat2->row[i], mat1->n_col)) | |||
| 1566 | return 0; | |||
| 1567 | ||||
| 1568 | return 1; | |||
| 1569 | } | |||
| 1570 | ||||
| 1571 | __isl_give isl_mat *isl_mat_from_row_vec(__isl_take isl_vec *vec) | |||
| 1572 | { | |||
| 1573 | struct isl_mat *mat; | |||
| 1574 | ||||
| 1575 | if (!vec) | |||
| 1576 | return NULL((void*)0); | |||
| 1577 | mat = isl_mat_alloc(vec->ctx, 1, vec->size); | |||
| 1578 | if (!mat) | |||
| 1579 | goto error; | |||
| 1580 | ||||
| 1581 | isl_seq_cpy(mat->row[0], vec->el, vec->size); | |||
| 1582 | ||||
| 1583 | isl_vec_free(vec); | |||
| 1584 | return mat; | |||
| 1585 | error: | |||
| 1586 | isl_vec_free(vec); | |||
| 1587 | return NULL((void*)0); | |||
| 1588 | } | |||
| 1589 | ||||
| 1590 | /* Return a copy of row "row" of "mat" as an isl_vec. | |||
| 1591 | */ | |||
| 1592 | __isl_give isl_vec *isl_mat_get_row(__isl_keep isl_mat *mat, unsigned row) | |||
| 1593 | { | |||
| 1594 | isl_vec *v; | |||
| 1595 | ||||
| 1596 | if (!mat) | |||
| 1597 | return NULL((void*)0); | |||
| 1598 | if (row >= mat->n_row) | |||
| 1599 | isl_die(mat->ctx, isl_error_invalid, "row out of range",do { isl_handle_error(mat->ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1600); return ((void*)0); } while (0) | |||
| 1600 | return NULL)do { isl_handle_error(mat->ctx, isl_error_invalid, "row out of range" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn257205/polly/lib/External/isl/isl_mat.c" , 1600); return ((void*)0); } while (0); | |||
| 1601 | ||||
| 1602 | v = isl_vec_alloc(isl_mat_get_ctx(mat), mat->n_col); | |||
| 1603 | if (!v) | |||
| 1604 | return NULL((void*)0); | |||
| 1605 | isl_seq_cpy(v->el, mat->row[row], mat->n_col); | |||
| 1606 | ||||
| 1607 | return v; | |||
| 1608 | } | |||
| 1609 | ||||
| 1610 | __isl_give isl_mat *isl_mat_vec_concat(__isl_take isl_mat *top, | |||
| 1611 | __isl_take isl_vec *bot) | |||
| 1612 | { | |||
| 1613 | return isl_mat_concat(top, isl_mat_from_row_vec(bot)); | |||
| 1614 | } | |||
| 1615 | ||||
| 1616 | __isl_give isl_mat *isl_mat_move_cols(__isl_take isl_mat *mat, | |||
| 1617 | unsigned dst_col, unsigned src_col, unsigned n) | |||
| 1618 | { | |||
| 1619 | isl_mat *res; | |||
| 1620 | ||||
| 1621 | if (!mat) | |||
| 1622 | return NULL((void*)0); | |||
| 1623 | if (n == 0 || dst_col == src_col) | |||
| 1624 | return mat; | |||
| 1625 | ||||
| 1626 | res = isl_mat_alloc(mat->ctx, mat->n_row, mat->n_col); | |||
| 1627 | if (!res) | |||
| 1628 | goto error; | |||
| 1629 | ||||
| 1630 | if (dst_col < src_col) { | |||
| 1631 | isl_mat_sub_copy(res->ctx, res->row, mat->row, mat->n_row, | |||
| 1632 | 0, 0, dst_col); | |||
| 1633 | isl_mat_sub_copy(res->ctx, res->row, mat->row, mat->n_row, | |||
| 1634 | dst_col, src_col, n); | |||
| 1635 | isl_mat_sub_copy(res->ctx, res->row, mat->row, mat->n_row, | |||
| 1636 | dst_col + n, dst_col, src_col - dst_col); | |||
| 1637 | isl_mat_sub_copy(res->ctx, res->row, mat->row, mat->n_row, | |||
| 1638 | src_col + n, src_col + n, | |||
| 1639 | res->n_col - src_col - n); | |||
| 1640 | } else { | |||
| 1641 | isl_mat_sub_copy(res->ctx, res->row, mat->row, mat->n_row, | |||
| 1642 | 0, 0, src_col); | |||
| 1643 | isl_mat_sub_copy(res->ctx, res->row, mat->row, mat->n_row, | |||
| 1644 | src_col, src_col + n, dst_col - src_col); | |||
| 1645 | isl_mat_sub_copy(res->ctx, res->row, mat->row, mat->n_row, | |||
| 1646 | dst_col, src_col, n); | |||
| 1647 | isl_mat_sub_copy(res->ctx, res->row, mat->row, mat->n_row, | |||
| 1648 | dst_col + n, dst_col + n, | |||
| 1649 | res->n_col - dst_col - n); | |||
| 1650 | } | |||
| 1651 | isl_mat_free(mat); | |||
| 1652 | ||||
| 1653 | return res; | |||
| 1654 | error: | |||
| 1655 | isl_mat_free(mat); | |||
| 1656 | return NULL((void*)0); | |||
| 1657 | } | |||
| 1658 | ||||
| 1659 | void isl_mat_gcd(__isl_keep isl_mat *mat, isl_int *gcd) | |||
| 1660 | { | |||
| 1661 | int i; | |||
| 1662 | isl_int g; | |||
| 1663 | ||||
| 1664 | isl_int_set_si(*gcd, 0)isl_sioimath_set_si((*gcd), 0); | |||
| 1665 | if (!mat) | |||
| 1666 | return; | |||
| 1667 | ||||
| 1668 | isl_int_init(g)isl_sioimath_init((g)); | |||
| 1669 | for (i = 0; i < mat->n_row; ++i) { | |||
| 1670 | isl_seq_gcd(mat->row[i], mat->n_col, &g); | |||
| 1671 | isl_int_gcd(*gcd, *gcd, g)isl_sioimath_gcd((*gcd), *(*gcd), *(g)); | |||
| 1672 | } | |||
| 1673 | isl_int_clear(g)isl_sioimath_clear((g)); | |||
| 1674 | } | |||
| 1675 | ||||
| 1676 | __isl_give isl_mat *isl_mat_scale_down(__isl_take isl_mat *mat, isl_int m) | |||
| 1677 | { | |||
| 1678 | int i; | |||
| 1679 | ||||
| 1680 | if (isl_int_is_one(m)(isl_sioimath_cmp_si(*(m), 1) == 0)) | |||
| 1681 | return mat; | |||
| 1682 | ||||
| 1683 | mat = isl_mat_cow(mat); | |||
| 1684 | if (!mat) | |||
| 1685 | return NULL((void*)0); | |||
| 1686 | ||||
| 1687 | for (i = 0; i < mat->n_row; ++i) | |||
| 1688 | isl_seq_scale_down(mat->row[i], mat->row[i], m, mat->n_col); | |||
| 1689 | ||||
| 1690 | return mat; | |||
| 1691 | } | |||
| 1692 | ||||
| 1693 | __isl_give isl_mat *isl_mat_scale_down_row(__isl_take isl_mat *mat, int row, | |||
| 1694 | isl_int m) | |||
| 1695 | { | |||
| 1696 | if (isl_int_is_one(m)(isl_sioimath_cmp_si(*(m), 1) == 0)) | |||
| 1697 | return mat; | |||
| 1698 | ||||
| 1699 | mat = isl_mat_cow(mat); | |||
| 1700 | if (!mat) | |||
| 1701 | return NULL((void*)0); | |||
| 1702 | ||||
| 1703 | isl_seq_scale_down(mat->row[row], mat->row[row], m, mat->n_col); | |||
| 1704 | ||||
| 1705 | return mat; | |||
| 1706 | } | |||
| 1707 | ||||
| 1708 | __isl_give isl_mat *isl_mat_normalize(__isl_take isl_mat *mat) | |||
| 1709 | { | |||
| 1710 | isl_int gcd; | |||
| 1711 | ||||
| 1712 | if (!mat) | |||
| 1713 | return NULL((void*)0); | |||
| 1714 | ||||
| 1715 | isl_int_init(gcd)isl_sioimath_init((gcd)); | |||
| 1716 | isl_mat_gcd(mat, &gcd); | |||
| 1717 | mat = isl_mat_scale_down(mat, gcd); | |||
| 1718 | isl_int_clear(gcd)isl_sioimath_clear((gcd)); | |||
| 1719 | ||||
| 1720 | return mat; | |||
| 1721 | } | |||
| 1722 | ||||
| 1723 | __isl_give isl_mat *isl_mat_normalize_row(__isl_take isl_mat *mat, int row) | |||
| 1724 | { | |||
| 1725 | mat = isl_mat_cow(mat); | |||
| 1726 | if (!mat) | |||
| 1727 | return NULL((void*)0); | |||
| 1728 | ||||
| 1729 | isl_seq_normalize(mat->ctx, mat->row[row], mat->n_col); | |||
| 1730 | ||||
| 1731 | return mat; | |||
| 1732 | } | |||
| 1733 | ||||
| 1734 | /* Number of initial non-zero columns. | |||
| 1735 | */ | |||
| 1736 | int isl_mat_initial_non_zero_cols(__isl_keep isl_mat *mat) | |||
| 1737 | { | |||
| 1738 | int i; | |||
| 1739 | ||||
| 1740 | if (!mat) | |||
| 1741 | return -1; | |||
| 1742 | ||||
| 1743 | for (i = 0; i < mat->n_col; ++i) | |||
| 1744 | if (row_first_non_zero(mat->row, mat->n_row, i) < 0) | |||
| 1745 | break; | |||
| 1746 | ||||
| 1747 | return i; | |||
| 1748 | } |