Bug Summary

File:tools/polly/lib/External/isl/isl_mat.c
Warning:line 2093, column 23
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name isl_mat.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-config-compatibility-mode=true -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/include -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn348900/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-command-line-argument -Wno-unknown-warning-option -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=gnu99 -fconst-strings -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External -ferror-limit 19 -fmessage-length 0 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-12-12-042652-12204-1 -x c /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_mat.c -faddrsig
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
25isl_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 */
32uint32_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
53struct 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;
83error:
84 isl_blk_free(ctx, mat->block);
85 free(mat);
86 return NULL((void*)0);
87}
88
89struct 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;
141error:
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;
168error:
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
182void 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
191void 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)
3
Assuming 'mat' is non-null
4
Taking false branch
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)
11
Taking false branch
228 return NULL((void*)0);
229
230 if (mat->ref == 1 && !ISL_F_ISSET(mat, ISL_MAT_BORROWED)(!!(((mat)->flags) & ((1 << 0)))))
12
Assuming the condition is false
231 return mat;
232
233 mat2 = isl_mat_dup(mat);
234 isl_mat_free(mat);
13
Calling 'isl_mat_free'
20
Returning; memory was released via 1st parameter
235 return mat2;
236}
237
238__isl_null isl_mat *isl_mat_free(__isl_take isl_mat *mat)
239{
240 if (!mat)
14
Taking false branch
241 return NULL((void*)0);
242
243 if (--mat->ref > 0)
15
Assuming the condition is false
16
Taking false branch
244 return NULL((void*)0);
245
246 if (!ISL_F_ISSET(mat, ISL_MAT_BORROWED)(!!(((mat)->flags) & ((1 << 0)))))
17
Assuming the condition is false
18
Taking false branch
247 isl_blk_free(mat->ctx, mat->block);
248 isl_ctx_deref(mat->ctx);
249 free(mat->row);
250 free(mat);
19
Memory is released
251
252 return NULL((void*)0);
253}
254
255int isl_mat_rows(__isl_keep isl_mat *mat)
256{
257 return mat ? mat->n_row : -1;
258}
259
260int 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 */
267static 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-8~svn348900/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-8~svn348900/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 */
279static 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-8~svn348900/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-8~svn348900/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 */
291static 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-8~svn348900/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-8~svn348900/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-8~svn348900/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 */
305static 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-8~svn348900/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-8~svn348900/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-8~svn348900/tools/polly/lib/External/isl/isl_mat.c"
, 313); return isl_stat_error; } while (0)
;
314 return isl_stat_ok;
315}
316
317int 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-8~svn348900/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-8~svn348900/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;
379error:
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 */
426int 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-8~svn348900/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;
469error:
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;
498error:
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-8~svn348900/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;
527error:
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-8~svn348900/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-8~svn348900/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-8~svn348900/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-8~svn348900/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-8~svn348900/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-8~svn348900/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-8~svn348900/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-8~svn348900/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-8~svn348900/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-8~svn348900/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;
577error:
578 isl_mat_free(left);
579 isl_mat_free(right);
580 return NULL((void*)0);
581}
582
583static 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
597static 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
613static 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)
7
Taking false branch
646 *U = NULL((void*)0);
647 if (Q)
8
Taking false branch
648 *Q = NULL((void*)0);
649 if (!M)
9
Taking false branch
650 goto error;
651 M = isl_mat_cow(M);
10
Calling 'isl_mat_cow'
21
Returning; memory was released via 1st parameter
652 if (!M)
22
Taking false branch
653 goto error;
654 if (U) {
23
Taking false branch
655 *U = isl_mat_identity(M->ctx, M->n_col);
656 if (!*U)
657 goto error;
658 }
659 if (Q) {
24
Taking false branch
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) {
25
Assuming the condition is true
26
Loop condition is true. Entering loop body
30
Assuming the condition is false
31
Loop condition is false. Execution continues on line 701
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)
27
Assuming the condition is true
28
Taking true branch
671 continue;
29
Execution continues on line 667
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;
704error:
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 */
719static __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 */
829static 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 */
847int 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));
2
Calling 'isl_mat_copy'
5
Returning from 'isl_mat_copy'
6
Calling 'isl_mat_left_hermite'
32
Returning; memory was released via 1st parameter
853 if (!H)
33
Taking false branch
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;
880error:
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;
904error:
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;
939error:
940 isl_mat_free(mat1);
941 isl_mat_free(mat2);
942 return NULL((void*)0);
943}
944
945static 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
955static 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
969static 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
980static 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
987static 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-8~svn348900/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-8~svn348900/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-8~svn348900/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-8~svn348900/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;
1088error:
1089 isl_mat_free(left);
1090 isl_mat_free(right);
1091 return NULL((void*)0);
1092}
1093
1094void 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
1102void 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-8~svn348900/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;
1190error:
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;
1221error:
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-8~svn348900/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;
1298error:
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 */
1315static 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-8~svn348900/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-8~svn348900/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-8~svn348900/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;
1402error:
1403 isl_mat_free(mat);
1404error2:
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;
1434error:
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 */
1444isl_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
1464void 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
1493void 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;
1555error:
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;
1605error:
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
1641void 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
1650void 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
1662void 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-8~svn348900/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-8~svn348900/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;
1750error:
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-8~svn348900/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;
1785error:
1786 isl_mat_free(top);
1787 isl_mat_free(bot);
1788 return NULL((void*)0);
1789}
1790
1791isl_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;
1825error:
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-8~svn348900/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-8~svn348900/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;
1894error:
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 */
1902isl_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
1912void 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 */
2008int 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;
2064error:
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 */
2076isl_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);
1
Calling 'isl_mat_rank'
34
Returning; memory was released via 1st parameter
2083 if (r1 < 0)
35
Taking false branch
2084 return isl_bool_error;
2085 if (r1 == 0)
36
Taking false branch
2086 return isl_bool_true;
2087 r2 = isl_mat_rank(mat2);
2088 if (r2 < 0)
37
Assuming 'r2' is >= 0
38
Taking false branch
2089 return isl_bool_error;
2090 if (r2 == 0)
39
Assuming 'r2' is not equal to 0
40
Taking false branch
2091 return isl_bool_true;
2092
2093 mat = isl_mat_concat(isl_mat_copy(mat1), isl_mat_copy(mat2));
41
Use of memory after it is freed
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}