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