Bug Summary

File:tools/polly/lib/External/isl/isl_morph.c
Warning:line 742, column 56
Use of memory after it is freed

Annotated Source Code

1/*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2014 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
11 */
12
13#include <isl_map_private.h>
14#include <isl_aff_private.h>
15#include <isl_morph.h>
16#include <isl_seq.h>
17#include <isl_mat_private.h>
18#include <isl_space_private.h>
19#include <isl_equalities.h>
20
21isl_ctx *isl_morph_get_ctx(__isl_keep isl_morph *morph)
22{
23 if (!morph)
24 return NULL((void*)0);
25 return isl_basic_set_get_ctx(morph->dom);
26}
27
28__isl_give isl_morph *isl_morph_alloc(
29 __isl_take isl_basic_setisl_basic_map *dom, __isl_take isl_basic_setisl_basic_map *ran,
30 __isl_take isl_mat *map, __isl_take isl_mat *inv)
31{
32 isl_morph *morph;
33
34 if (!dom || !ran || !map || !inv)
12
Assuming 'dom' is non-null
13
Assuming 'ran' is non-null
14
Assuming 'map' is non-null
15
Assuming 'inv' is non-null
16
Taking false branch
35 goto error;
36
37 morph = isl_alloc_type(dom->ctx, struct isl_morph)((struct isl_morph *)isl_malloc_or_die(dom->ctx, sizeof(struct
isl_morph)))
;
38 if (!morph)
17
Assuming 'morph' is non-null
18
Taking false branch
39 goto error;
40
41 morph->ref = 1;
42 morph->dom = dom;
43 morph->ran = ran;
44 morph->map = map;
45 morph->inv = inv;
46
47 return morph;
48error:
49 isl_basic_set_free(dom);
50 isl_basic_set_free(ran);
51 isl_mat_free(map);
52 isl_mat_free(inv);
53 return NULL((void*)0);
54}
55
56__isl_give isl_morph *isl_morph_copy(__isl_keep isl_morph *morph)
57{
58 if (!morph)
59 return NULL((void*)0);
60
61 morph->ref++;
62 return morph;
63}
64
65__isl_give isl_morph *isl_morph_dup(__isl_keep isl_morph *morph)
66{
67 if (!morph)
68 return NULL((void*)0);
69
70 return isl_morph_alloc(isl_basic_set_copy(morph->dom),
71 isl_basic_set_copy(morph->ran),
72 isl_mat_copy(morph->map), isl_mat_copy(morph->inv));
73}
74
75__isl_give isl_morph *isl_morph_cow(__isl_take isl_morph *morph)
76{
77 if (!morph)
78 return NULL((void*)0);
79
80 if (morph->ref == 1)
81 return morph;
82 morph->ref--;
83 return isl_morph_dup(morph);
84}
85
86void isl_morph_free(__isl_take isl_morph *morph)
87{
88 if (!morph)
43
Taking false branch
89 return;
90
91 if (--morph->ref > 0)
44
Assuming the condition is false
45
Taking false branch
92 return;
93
94 isl_basic_set_free(morph->dom);
95 isl_basic_set_free(morph->ran);
96 isl_mat_free(morph->map);
97 isl_mat_free(morph->inv);
98 free(morph);
46
Memory is released
99}
100
101/* Is "morph" an identity on the parameters?
102 */
103static int identity_on_parameters(__isl_keep isl_morph *morph)
104{
105 int is_identity;
106 unsigned nparam;
107 isl_mat *sub;
108
109 nparam = isl_morph_dom_dim(morph, isl_dim_param);
110 if (nparam != isl_morph_ran_dim(morph, isl_dim_param))
111 return 0;
112 if (nparam == 0)
113 return 1;
114 sub = isl_mat_sub_alloc(morph->map, 0, 1 + nparam, 0, 1 + nparam);
115 is_identity = isl_mat_is_scaled_identity(sub);
116 isl_mat_free(sub);
117
118 return is_identity;
119}
120
121/* Return an affine expression of the variables of the range of "morph"
122 * in terms of the parameters and the variables of the domain on "morph".
123 *
124 * In order for the space manipulations to make sense, we require
125 * that the parameters are not modified by "morph".
126 */
127__isl_give isl_multi_aff *isl_morph_get_var_multi_aff(
128 __isl_keep isl_morph *morph)
129{
130 isl_space *dom, *ran, *space;
131 isl_local_space *ls;
132 isl_multi_aff *ma;
133 unsigned nparam, nvar;
134 int i;
135 int is_identity;
136
137 if (!morph)
138 return NULL((void*)0);
139
140 is_identity = identity_on_parameters(morph);
141 if (is_identity < 0)
142 return NULL((void*)0);
143 if (!is_identity)
144 isl_die(isl_morph_get_ctx(morph), isl_error_invalid,do { isl_handle_error(isl_morph_get_ctx(morph), isl_error_invalid
, "cannot handle parameter compression", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 145); return ((void*)0); } while (0)
145 "cannot handle parameter compression", return NULL)do { isl_handle_error(isl_morph_get_ctx(morph), isl_error_invalid
, "cannot handle parameter compression", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 145); return ((void*)0); } while (0)
;
146
147 dom = isl_morph_get_dom_space(morph);
148 ls = isl_local_space_from_space(isl_space_copy(dom));
149 ran = isl_morph_get_ran_space(morph);
150 space = isl_space_map_from_domain_and_range(dom, ran);
151 ma = isl_multi_aff_zero(space);
152
153 nparam = isl_multi_aff_dim(ma, isl_dim_param);
154 nvar = isl_multi_aff_dim(ma, isl_dim_out);
155 for (i = 0; i < nvar; ++i) {
156 isl_val *val;
157 isl_vec *v;
158 isl_aff *aff;
159
160 v = isl_mat_get_row(morph->map, 1 + nparam + i);
161 v = isl_vec_insert_els(v, 0, 1);
162 val = isl_mat_get_element_val(morph->map, 0, 0);
163 v = isl_vec_set_element_val(v, 0, val);
164 aff = isl_aff_alloc_vec(isl_local_space_copy(ls), v);
165 ma = isl_multi_aff_set_aff(ma, i, aff);
166 }
167
168 isl_local_space_free(ls);
169 return ma;
170}
171
172/* Return the domain space of "morph".
173 */
174__isl_give isl_space *isl_morph_get_dom_space(__isl_keep isl_morph *morph)
175{
176 if (!morph)
177 return NULL((void*)0);
178
179 return isl_basic_set_get_space(morph->dom);
180}
181
182__isl_give isl_space *isl_morph_get_ran_space(__isl_keep isl_morph *morph)
183{
184 if (!morph)
185 return NULL((void*)0);
186
187 return isl_space_copy(morph->ran->dim);
188}
189
190unsigned isl_morph_dom_dim(__isl_keep isl_morph *morph, enum isl_dim_type type)
191{
192 if (!morph)
193 return 0;
194
195 return isl_basic_set_dim(morph->dom, type);
196}
197
198unsigned isl_morph_ran_dim(__isl_keep isl_morph *morph, enum isl_dim_type type)
199{
200 if (!morph)
201 return 0;
202
203 return isl_basic_set_dim(morph->ran, type);
204}
205
206__isl_give isl_morph *isl_morph_remove_dom_dims(__isl_take isl_morph *morph,
207 enum isl_dim_type type, unsigned first, unsigned n)
208{
209 unsigned dom_offset;
210
211 if (n == 0)
212 return morph;
213
214 morph = isl_morph_cow(morph);
215 if (!morph)
216 return NULL((void*)0);
217
218 dom_offset = 1 + isl_space_offset(morph->dom->dim, type);
219
220 morph->dom = isl_basic_set_remove_dims(morph->dom, type, first, n);
221
222 morph->map = isl_mat_drop_cols(morph->map, dom_offset + first, n);
223
224 morph->inv = isl_mat_drop_rows(morph->inv, dom_offset + first, n);
225
226 if (morph->dom && morph->ran && morph->map && morph->inv)
227 return morph;
228
229 isl_morph_free(morph);
230 return NULL((void*)0);
231}
232
233__isl_give isl_morph *isl_morph_remove_ran_dims(__isl_take isl_morph *morph,
234 enum isl_dim_type type, unsigned first, unsigned n)
235{
236 unsigned ran_offset;
237
238 if (n == 0)
239 return morph;
240
241 morph = isl_morph_cow(morph);
242 if (!morph)
243 return NULL((void*)0);
244
245 ran_offset = 1 + isl_space_offset(morph->ran->dim, type);
246
247 morph->ran = isl_basic_set_remove_dims(morph->ran, type, first, n);
248
249 morph->map = isl_mat_drop_rows(morph->map, ran_offset + first, n);
250
251 morph->inv = isl_mat_drop_cols(morph->inv, ran_offset + first, n);
252
253 if (morph->dom && morph->ran && morph->map && morph->inv)
254 return morph;
255
256 isl_morph_free(morph);
257 return NULL((void*)0);
258}
259
260/* Project domain of morph onto its parameter domain.
261 */
262__isl_give isl_morph *isl_morph_dom_params(__isl_take isl_morph *morph)
263{
264 unsigned n;
265
266 morph = isl_morph_cow(morph);
267 if (!morph)
268 return NULL((void*)0);
269 n = isl_basic_set_dim(morph->dom, isl_dim_set);
270 morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, n);
271 if (!morph)
272 return NULL((void*)0);
273 morph->dom = isl_basic_set_params(morph->dom);
274 if (morph->dom)
275 return morph;
276
277 isl_morph_free(morph);
278 return NULL((void*)0);
279}
280
281/* Project range of morph onto its parameter domain.
282 */
283__isl_give isl_morph *isl_morph_ran_params(__isl_take isl_morph *morph)
284{
285 unsigned n;
286
287 morph = isl_morph_cow(morph);
288 if (!morph)
289 return NULL((void*)0);
290 n = isl_basic_set_dim(morph->ran, isl_dim_set);
291 morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, n);
292 if (!morph)
293 return NULL((void*)0);
294 morph->ran = isl_basic_set_params(morph->ran);
295 if (morph->ran)
296 return morph;
297
298 isl_morph_free(morph);
299 return NULL((void*)0);
300}
301
302void isl_morph_print_internal(__isl_take isl_morph *morph, FILE *out)
303{
304 if (!morph)
305 return;
306
307 isl_basic_set_dump(morph->dom);
308 isl_basic_set_dump(morph->ran);
309 isl_mat_print_internal(morph->map, out, 4);
310 isl_mat_print_internal(morph->inv, out, 4);
311}
312
313void isl_morph_dump(__isl_take isl_morph *morph)
314{
315 isl_morph_print_internal(morph, stderrstderr);
316}
317
318__isl_give isl_morph *isl_morph_identity(__isl_keep isl_basic_setisl_basic_map *bset)
319{
320 isl_mat *id;
321 isl_basic_setisl_basic_map *universe;
322 unsigned total;
323
324 if (!bset)
325 return NULL((void*)0);
326
327 total = isl_basic_set_total_dim(bset);
328 id = isl_mat_identity(bset->ctx, 1 + total);
329 universe = isl_basic_set_universe(isl_space_copy(bset->dim));
330
331 return isl_morph_alloc(universe, isl_basic_set_copy(universe),
332 id, isl_mat_copy(id));
333}
334
335/* Create a(n identity) morphism between empty sets of the same dimension
336 * a "bset".
337 */
338__isl_give isl_morph *isl_morph_empty(__isl_keep isl_basic_setisl_basic_map *bset)
339{
340 isl_mat *id;
341 isl_basic_setisl_basic_map *empty;
342 unsigned total;
343
344 if (!bset)
345 return NULL((void*)0);
346
347 total = isl_basic_set_total_dim(bset);
348 id = isl_mat_identity(bset->ctx, 1 + total);
349 empty = isl_basic_set_empty(isl_space_copy(bset->dim));
350
351 return isl_morph_alloc(empty, isl_basic_set_copy(empty),
352 id, isl_mat_copy(id));
353}
354
355/* Construct a basic set described by the "n" equalities of "bset" starting
356 * at "first".
357 */
358static __isl_give isl_basic_setisl_basic_map *copy_equalities(__isl_keep isl_basic_setisl_basic_map *bset,
359 unsigned first, unsigned n)
360{
361 int i, k;
362 isl_basic_setisl_basic_map *eq;
363 unsigned total;
364
365 isl_assert(bset->ctx, bset->n_div == 0, return NULL)do { if (bset->n_div == 0) break; do { isl_handle_error(bset
->ctx, isl_error_unknown, "Assertion \"" "bset->n_div == 0"
"\" failed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 365); return ((void*)0); } while (0); } while (0)
;
366
367 total = isl_basic_set_total_dim(bset);
368 eq = isl_basic_set_alloc_space(isl_space_copy(bset->dim), 0, n, 0);
369 if (!eq)
370 return NULL((void*)0);
371 for (i = 0; i < n; ++i) {
372 k = isl_basic_set_alloc_equality(eq);
373 if (k < 0)
374 goto error;
375 isl_seq_cpy(eq->eq[k], bset->eq[first + i], 1 + total);
376 }
377
378 return eq;
379error:
380 isl_basic_set_free(eq);
381 return NULL((void*)0);
382}
383
384/* Given a basic set, exploit the equalties in the basic set to construct
385 * a morphishm that maps the basic set to a lower-dimensional space.
386 * Specifically, the morphism reduces the number of dimensions of type "type".
387 *
388 * We first select the equalities of interest, that is those that involve
389 * variables of type "type" and no later variables.
390 * Denote those equalities as
391 *
392 * -C(p) + M x = 0
393 *
394 * where C(p) depends on the parameters if type == isl_dim_set and
395 * is a constant if type == isl_dim_param.
396 *
397 * Use isl_mat_final_variable_compression to construct a compression
398 *
399 * x = T x'
400 *
401 * x' = Q x
402 *
403 * If T is a zero-column matrix, then the set of equality constraints
404 * do not admit a solution. In this case, an empty morphism is returned.
405 *
406 * Both matrices are extended to map the full original space to the full
407 * compressed space.
408 */
409__isl_give isl_morph *isl_basic_set_variable_compression(
410 __isl_keep isl_basic_setisl_basic_map *bset, enum isl_dim_type type)
411{
412 unsigned otype;
413 unsigned ntype;
414 unsigned orest;
415 unsigned nrest;
416 int f_eq, n_eq;
417 isl_space *dim;
418 isl_mat *E, *Q, *C;
419 isl_basic_setisl_basic_map *dom, *ran;
420
421 if (!bset)
422 return NULL((void*)0);
423
424 if (isl_basic_set_plain_is_empty(bset))
425 return isl_morph_empty(bset);
426
427 isl_assert(bset->ctx, bset->n_div == 0, return NULL)do { if (bset->n_div == 0) break; do { isl_handle_error(bset
->ctx, isl_error_unknown, "Assertion \"" "bset->n_div == 0"
"\" failed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 427); return ((void*)0); } while (0); } while (0)
;
428
429 otype = 1 + isl_space_offset(bset->dim, type);
430 ntype = isl_basic_set_dim(bset, type);
431 orest = otype + ntype;
432 nrest = isl_basic_set_total_dim(bset) - (orest - 1);
433
434 for (f_eq = 0; f_eq < bset->n_eq; ++f_eq)
435 if (isl_seq_first_non_zero(bset->eq[f_eq] + orest, nrest) == -1)
436 break;
437 for (n_eq = 0; f_eq + n_eq < bset->n_eq; ++n_eq)
438 if (isl_seq_first_non_zero(bset->eq[f_eq + n_eq] + otype, ntype) == -1)
439 break;
440 if (n_eq == 0)
441 return isl_morph_identity(bset);
442
443 E = isl_mat_sub_alloc6(bset->ctx, bset->eq, f_eq, n_eq, 0, orest);
444 C = isl_mat_final_variable_compression(E, otype - 1, &Q);
445 if (!Q)
446 C = isl_mat_free(C);
447 if (C && C->n_col == 0) {
448 isl_mat_free(C);
449 isl_mat_free(Q);
450 return isl_morph_empty(bset);
451 }
452
453 Q = isl_mat_diagonal(Q, isl_mat_identity(bset->ctx, nrest));
454 C = isl_mat_diagonal(C, isl_mat_identity(bset->ctx, nrest));
455
456 dim = isl_space_copy(bset->dim);
457 dim = isl_space_drop_dims(dim, type, 0, ntype);
458 dim = isl_space_add_dims(dim, type, ntype - n_eq);
459 ran = isl_basic_set_universe(dim);
460 dom = copy_equalities(bset, f_eq, n_eq);
461
462 return isl_morph_alloc(dom, ran, Q, C);
463}
464
465/* Construct a parameter compression for "bset".
466 * We basically just call isl_mat_parameter_compression with the right input
467 * and then extend the resulting matrix to include the variables.
468 *
469 * The implementation assumes that "bset" does not have any equalities
470 * that only involve the parameters and that isl_basic_set_gauss has
471 * been applied to "bset".
472 *
473 * Let the equalities be given as
474 *
475 * B(p) + A x = 0.
476 *
477 * We use isl_mat_parameter_compression_ext to compute the compression
478 *
479 * p = T p'.
480 */
481__isl_give isl_morph *isl_basic_set_parameter_compression(
482 __isl_keep isl_basic_setisl_basic_map *bset)
483{
484 unsigned nparam;
485 unsigned nvar;
486 unsigned n_div;
487 int n_eq;
488 isl_mat *H, *B;
489 isl_mat *map, *inv;
490 isl_basic_setisl_basic_map *dom, *ran;
491
492 if (!bset)
2
Assuming 'bset' is non-null
3
Taking false branch
493 return NULL((void*)0);
494
495 if (isl_basic_set_plain_is_empty(bset))
4
Assuming the condition is false
5
Taking false branch
496 return isl_morph_empty(bset);
497 if (bset->n_eq == 0)
6
Assuming the condition is false
7
Taking false branch
498 return isl_morph_identity(bset);
499
500 n_eq = bset->n_eq;
501 nparam = isl_basic_set_dim(bset, isl_dim_param);
502 nvar = isl_basic_set_dim(bset, isl_dim_set);
503 n_div = isl_basic_set_dim(bset, isl_dim_div);
504
505 if (isl_seq_first_non_zero(bset->eq[bset->n_eq - 1] + 1 + nparam,
8
Assuming the condition is false
9
Taking false branch
506 nvar + n_div) == -1)
507 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,do { isl_handle_error(isl_basic_set_get_ctx(bset), isl_error_invalid
, "input not allowed to have parameter equalities", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 509); return ((void*)0); } while (0)
508 "input not allowed to have parameter equalities",do { isl_handle_error(isl_basic_set_get_ctx(bset), isl_error_invalid
, "input not allowed to have parameter equalities", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 509); return ((void*)0); } while (0)
509 return NULL)do { isl_handle_error(isl_basic_set_get_ctx(bset), isl_error_invalid
, "input not allowed to have parameter equalities", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 509); return ((void*)0); } while (0)
;
510 if (n_eq > nvar + n_div)
10
Taking false branch
511 isl_die(isl_basic_set_get_ctx(bset), isl_error_invalid,do { isl_handle_error(isl_basic_set_get_ctx(bset), isl_error_invalid
, "input not gaussed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 512); return ((void*)0); } while (0)
512 "input not gaussed", return NULL)do { isl_handle_error(isl_basic_set_get_ctx(bset), isl_error_invalid
, "input not gaussed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 512); return ((void*)0); } while (0)
;
513
514 B = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, n_eq, 0, 1 + nparam);
515 H = isl_mat_sub_alloc6(bset->ctx, bset->eq,
516 0, n_eq, 1 + nparam, nvar + n_div);
517 inv = isl_mat_parameter_compression_ext(B, H);
518 inv = isl_mat_diagonal(inv, isl_mat_identity(bset->ctx, nvar));
519 map = isl_mat_right_inverse(isl_mat_copy(inv));
520
521 dom = isl_basic_set_universe(isl_space_copy(bset->dim));
522 ran = isl_basic_set_universe(isl_space_copy(bset->dim));
523
524 return isl_morph_alloc(dom, ran, map, inv);
11
Calling 'isl_morph_alloc'
19
Returning from 'isl_morph_alloc'
525}
526
527/* Add stride constraints to "bset" based on the inverse mapping
528 * that was plugged in. In particular, if morph maps x' to x,
529 * the the constraints of the original input
530 *
531 * A x' + b >= 0
532 *
533 * have been rewritten to
534 *
535 * A inv x + b >= 0
536 *
537 * However, this substitution may loose information on the integrality of x',
538 * so we need to impose that
539 *
540 * inv x
541 *
542 * is integral. If inv = B/d, this means that we need to impose that
543 *
544 * B x = 0 mod d
545 *
546 * or
547 *
548 * exists alpha in Z^m: B x = d alpha
549 *
550 * This function is similar to add_strides in isl_affine_hull.c
551 */
552static __isl_give isl_basic_setisl_basic_map *add_strides(__isl_take isl_basic_setisl_basic_map *bset,
553 __isl_keep isl_morph *morph)
554{
555 int i, div, k;
556 isl_int gcd;
557
558 if (isl_int_is_one(morph->inv->row[0][0])(isl_sioimath_cmp_si(*(morph->inv->row[0][0]), 1) == 0))
559 return bset;
560
561 isl_int_init(gcd)isl_sioimath_init((gcd));
562
563 for (i = 0; 1 + i < morph->inv->n_row; ++i) {
564 isl_seq_gcd(morph->inv->row[1 + i], morph->inv->n_col, &gcd);
565 if (isl_int_is_divisible_by(gcd, morph->inv->row[0][0])isl_sioimath_is_divisible_by(*(gcd), *(morph->inv->row[
0][0]))
)
566 continue;
567 div = isl_basic_set_alloc_div(bset);
568 if (div < 0)
569 goto error;
570 isl_int_set_si(bset->div[div][0], 0)isl_sioimath_set_si((bset->div[div][0]), 0);
571 k = isl_basic_set_alloc_equality(bset);
572 if (k < 0)
573 goto error;
574 isl_seq_cpy(bset->eq[k], morph->inv->row[1 + i],
575 morph->inv->n_col);
576 isl_seq_clr(bset->eq[k] + morph->inv->n_col, bset->n_div);
577 isl_int_set(bset->eq[k][morph->inv->n_col + div],isl_sioimath_set((bset->eq[k][morph->inv->n_col + div
]), *(morph->inv->row[0][0]))
578 morph->inv->row[0][0])isl_sioimath_set((bset->eq[k][morph->inv->n_col + div
]), *(morph->inv->row[0][0]))
;
579 }
580
581 isl_int_clear(gcd)isl_sioimath_clear((gcd));
582
583 return bset;
584error:
585 isl_int_clear(gcd)isl_sioimath_clear((gcd));
586 isl_basic_set_free(bset);
587 return NULL((void*)0);
588}
589
590/* Apply the morphism to the basic set.
591 * We basically just compute the preimage of "bset" under the inverse mapping
592 * in morph, add in stride constraints and intersect with the range
593 * of the morphism.
594 */
595__isl_give isl_basic_setisl_basic_map *isl_morph_basic_set(__isl_take isl_morph *morph,
596 __isl_take isl_basic_setisl_basic_map *bset)
597{
598 isl_basic_setisl_basic_map *res = NULL((void*)0);
599 isl_mat *mat = NULL((void*)0);
600 int i, k;
601 int max_stride;
602
603 if (!morph || !bset)
24
Assuming 'bset' is non-null
25
Taking false branch
604 goto error;
605
606 isl_assert(bset->ctx, isl_space_is_equal(bset->dim, morph->dom->dim),do { if (isl_space_is_equal(bset->dim, morph->dom->dim
)) break; do { isl_handle_error(bset->ctx, isl_error_unknown
, "Assertion \"" "isl_space_is_equal(bset->dim, morph->dom->dim)"
"\" failed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 607); goto error; } while (0); } while (0)
607 goto error)do { if (isl_space_is_equal(bset->dim, morph->dom->dim
)) break; do { isl_handle_error(bset->ctx, isl_error_unknown
, "Assertion \"" "isl_space_is_equal(bset->dim, morph->dom->dim)"
"\" failed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 607); goto error; } while (0); } while (0)
;
608
609 max_stride = morph->inv->n_row - 1;
610 if (isl_int_is_one(morph->inv->row[0][0])(isl_sioimath_cmp_si(*(morph->inv->row[0][0]), 1) == 0))
26
Taking false branch
611 max_stride = 0;
612 res = isl_basic_set_alloc_space(isl_space_copy(morph->ran->dim),
613 bset->n_div + max_stride, bset->n_eq + max_stride, bset->n_ineq);
614
615 for (i = 0; i < bset->n_div; ++i)
27
Assuming the condition is false
28
Loop condition is false. Execution continues on line 619
616 if (isl_basic_set_alloc_div(res) < 0)
617 goto error;
618
619 mat = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
620 0, morph->inv->n_row);
621 mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
622 if (!mat)
29
Assuming 'mat' is non-null
30
Taking false branch
623 goto error;
624 for (i = 0; i < bset->n_eq; ++i) {
31
Assuming the condition is false
32
Loop condition is false. Execution continues on line 632
625 k = isl_basic_set_alloc_equality(res);
626 if (k < 0)
627 goto error;
628 isl_seq_cpy(res->eq[k], mat->row[i], mat->n_col);
629 isl_seq_scale(res->eq[k] + mat->n_col, bset->eq[i] + mat->n_col,
630 morph->inv->row[0][0], bset->n_div);
631 }
632 isl_mat_free(mat);
633
634 mat = isl_mat_sub_alloc6(bset->ctx, bset->ineq, 0, bset->n_ineq,
635 0, morph->inv->n_row);
636 mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
637 if (!mat)
33
Assuming 'mat' is non-null
34
Taking false branch
638 goto error;
639 for (i = 0; i < bset->n_ineq; ++i) {
35
Assuming the condition is false
36
Loop condition is false. Execution continues on line 648
640 k = isl_basic_set_alloc_inequality(res);
641 if (k < 0)
642 goto error;
643 isl_seq_cpy(res->ineq[k], mat->row[i], mat->n_col);
644 isl_seq_scale(res->ineq[k] + mat->n_col,
645 bset->ineq[i] + mat->n_col,
646 morph->inv->row[0][0], bset->n_div);
647 }
648 isl_mat_free(mat);
649
650 mat = isl_mat_sub_alloc6(bset->ctx, bset->div, 0, bset->n_div,
651 1, morph->inv->n_row);
652 mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
653 if (!mat)
37
Assuming 'mat' is non-null
38
Taking false branch
654 goto error;
655 for (i = 0; i < bset->n_div; ++i) {
39
Loop condition is false. Execution continues on line 663
656 isl_int_mul(res->div[i][0],isl_sioimath_mul((res->div[i][0]), *(morph->inv->row
[0][0]), *(bset->div[i][0]))
657 morph->inv->row[0][0], bset->div[i][0])isl_sioimath_mul((res->div[i][0]), *(morph->inv->row
[0][0]), *(bset->div[i][0]))
;
658 isl_seq_cpy(res->div[i] + 1, mat->row[i], mat->n_col);
659 isl_seq_scale(res->div[i] + 1 + mat->n_col,
660 bset->div[i] + 1 + mat->n_col,
661 morph->inv->row[0][0], bset->n_div);
662 }
663 isl_mat_free(mat);
664
665 res = add_strides(res, morph);
666
667 if (isl_basic_set_is_rational(bset))
40
Assuming the condition is false
41
Taking false branch
668 res = isl_basic_set_set_rational(res);
669
670 res = isl_basic_set_simplify(res);
671 res = isl_basic_set_finalize(res);
672
673 res = isl_basic_set_intersect(res, isl_basic_set_copy(morph->ran));
674
675 isl_morph_free(morph);
42
Calling 'isl_morph_free'
47
Returning; memory was released via 1st parameter
676 isl_basic_set_free(bset);
677 return res;
678error:
679 isl_mat_free(mat);
680 isl_morph_free(morph);
681 isl_basic_set_free(bset);
682 isl_basic_set_free(res);
683 return NULL((void*)0);
684}
685
686/* Apply the morphism to the set.
687 */
688__isl_give isl_setisl_map *isl_morph_set(__isl_take isl_morph *morph,
689 __isl_take isl_setisl_map *set)
690{
691 int i;
692
693 if (!morph || !set)
694 goto error;
695
696 isl_assert(set->ctx, isl_space_is_equal(set->dim, morph->dom->dim), goto error)do { if (isl_space_is_equal(set->dim, morph->dom->dim
)) break; do { isl_handle_error(set->ctx, isl_error_unknown
, "Assertion \"" "isl_space_is_equal(set->dim, morph->dom->dim)"
"\" failed", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn298304/tools/polly/lib/External/isl/isl_morph.c"
, 696); goto error; } while (0); } while (0)
;
697
698 set = isl_set_cow(set);
699 if (!set)
700 goto error;
701
702 isl_space_free(set->dim);
703 set->dim = isl_space_copy(morph->ran->dim);
704 if (!set->dim)
705 goto error;
706
707 for (i = 0; i < set->n; ++i) {
708 set->p[i] = isl_morph_basic_set(isl_morph_copy(morph), set->p[i]);
709 if (!set->p[i])
710 goto error;
711 }
712
713 isl_morph_free(morph);
714
715 ISL_F_CLR(set, ISL_SET_NORMALIZED)(((set)->flags) &= ~((1 << 1)));
716
717 return set;
718error:
719 isl_set_free(set);
720 isl_morph_free(morph);
721 return NULL((void*)0);
722}
723
724/* Construct a morphism that first does morph2 and then morph1.
725 */
726__isl_give isl_morph *isl_morph_compose(__isl_take isl_morph *morph1,
727 __isl_take isl_morph *morph2)
728{
729 isl_mat *map, *inv;
730 isl_basic_setisl_basic_map *dom, *ran;
731
732 if (!morph1 || !morph2)
22
Taking false branch
733 goto error;
734
735 map = isl_mat_product(isl_mat_copy(morph1->map), isl_mat_copy(morph2->map));
736 inv = isl_mat_product(isl_mat_copy(morph2->inv), isl_mat_copy(morph1->inv));
737 dom = isl_morph_basic_set(isl_morph_inverse(isl_morph_copy(morph2)),
738 isl_basic_set_copy(morph1->dom));
739 dom = isl_basic_set_intersect(dom, isl_basic_set_copy(morph2->dom));
740 ran = isl_morph_basic_set(isl_morph_copy(morph1),
23
Calling 'isl_morph_basic_set'
48
Returning; memory was released via 1st parameter
741 isl_basic_set_copy(morph2->ran));
742 ran = isl_basic_set_intersect(ran, isl_basic_set_copy(morph1->ran));
49
Use of memory after it is freed
743
744 isl_morph_free(morph1);
745 isl_morph_free(morph2);
746
747 return isl_morph_alloc(dom, ran, map, inv);
748error:
749 isl_morph_free(morph1);
750 isl_morph_free(morph2);
751 return NULL((void*)0);
752}
753
754__isl_give isl_morph *isl_morph_inverse(__isl_take isl_morph *morph)
755{
756 isl_basic_setisl_basic_map *bset;
757 isl_mat *mat;
758
759 morph = isl_morph_cow(morph);
760 if (!morph)
761 return NULL((void*)0);
762
763 bset = morph->dom;
764 morph->dom = morph->ran;
765 morph->ran = bset;
766
767 mat = morph->map;
768 morph->map = morph->inv;
769 morph->inv = mat;
770
771 return morph;
772}
773
774/* We detect all the equalities first to avoid implicit equalties
775 * being discovered during the computations. In particular,
776 * the compression on the variables could expose additional stride
777 * constraints on the parameters. This would result in existentially
778 * quantified variables after applying the resulting morph, which
779 * in turn could break invariants of the calling functions.
780 */
781__isl_give isl_morph *isl_basic_set_full_compression(
782 __isl_keep isl_basic_setisl_basic_map *bset)
783{
784 isl_morph *morph, *morph2;
785
786 bset = isl_basic_set_copy(bset);
787 bset = isl_basic_set_detect_equalities(bset);
788
789 morph = isl_basic_set_variable_compression(bset, isl_dim_param);
790 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
791
792 morph2 = isl_basic_set_parameter_compression(bset);
1
Calling 'isl_basic_set_parameter_compression'
20
Returning from 'isl_basic_set_parameter_compression'
793 bset = isl_morph_basic_set(isl_morph_copy(morph2), bset);
794
795 morph = isl_morph_compose(morph2, morph);
21
Calling 'isl_morph_compose'
796
797 morph2 = isl_basic_set_variable_compression(bset, isl_dim_set);
798 isl_basic_set_free(bset);
799
800 morph = isl_morph_compose(morph2, morph);
801
802 return morph;
803}
804
805__isl_give isl_vec *isl_morph_vec(__isl_take isl_morph *morph,
806 __isl_take isl_vec *vec)
807{
808 if (!morph)
809 goto error;
810
811 vec = isl_mat_vec_product(isl_mat_copy(morph->map), vec);
812
813 isl_morph_free(morph);
814 return vec;
815error:
816 isl_morph_free(morph);
817 isl_vec_free(vec);
818 return NULL((void*)0);
819}