Coverage Report

Created: 2017-08-18 19:41

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