Coverage Report

Created: 2017-10-03 07:32

/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
112k
{
33
112k
  isl_morph *morph;
34
112k
35
112k
  if (
!dom || 112k
!ran112k
||
!map112k
||
!inv112k
)
36
0
    goto error;
37
112k
38
112k
  
morph = 112k
isl_alloc_type112k
(dom->ctx, struct isl_morph);
39
112k
  if (!morph)
40
0
    goto error;
41
112k
42
112k
  morph->ref = 1;
43
112k
  morph->dom = dom;
44
112k
  morph->ran = ran;
45
112k
  morph->map = map;
46
112k
  morph->inv = inv;
47
112k
48
112k
  return morph;
49
0
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
0
  return NULL;
55
112k
}
56
57
__isl_give isl_morph *isl_morph_copy(__isl_keep isl_morph *morph)
58
88.6k
{
59
88.6k
  if (!morph)
60
0
    return NULL;
61
88.6k
62
88.6k
  morph->ref++;
63
88.6k
  return morph;
64
88.6k
}
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
44.1k
{
78
44.1k
  if (!morph)
79
0
    return NULL;
80
44.1k
81
44.1k
  
if (44.1k
morph->ref == 144.1k
)
82
44.0k
    return morph;
83
8
  morph->ref--;
84
8
  return isl_morph_dup(morph);
85
8
}
86
87
__isl_null isl_morph *isl_morph_free(__isl_take isl_morph *morph)
88
201k
{
89
201k
  if (!morph)
90
0
    return NULL;
91
201k
92
201k
  
if (201k
--morph->ref > 0201k
)
93
88.6k
    return NULL;
94
112k
95
112k
  isl_basic_set_free(morph->dom);
96
112k
  isl_basic_set_free(morph->ran);
97
112k
  isl_mat_free(morph->map);
98
112k
  isl_mat_free(morph->inv);
99
112k
  free(morph);
100
112k
101
112k
  return NULL;
102
112k
}
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
0
  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
0
  return is_identity;
122
0
}
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
) {
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
2
217
2
  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
0
232
0
  isl_morph_free(morph);
233
0
  return NULL;
234
0
}
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
2
244
2
  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
0
259
0
  isl_morph_free(morph);
260
0
  return NULL;
261
0
}
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
0
280
0
  isl_morph_free(morph);
281
0
  return NULL;
282
0
}
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
0
301
0
  isl_morph_free(morph);
302
0
  return NULL;
303
0
}
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
68.4k
{
323
68.4k
  isl_mat *id;
324
68.4k
  isl_basic_set *universe;
325
68.4k
  unsigned total;
326
68.4k
327
68.4k
  if (!bset)
328
0
    return NULL;
329
68.4k
330
68.4k
  total = isl_basic_set_total_dim(bset);
331
68.4k
  id = isl_mat_identity(bset->ctx, 1 + total);
332
68.4k
  universe = isl_basic_set_universe(isl_space_copy(bset->dim));
333
68.4k
334
68.4k
  return isl_morph_alloc(universe, isl_basic_set_copy(universe),
335
68.4k
    id, isl_mat_copy(id));
336
68.4k
}
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
) {
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
0
error:
383
0
  isl_basic_set_free(eq);
384
0
  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);
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
11
448
11
  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
) {
453
0
    isl_mat_free(C);
454
0
    isl_mat_free(Q);
455
0
    return isl_morph_empty(bset);
456
0
  }
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
11
}
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
44.5k
{
572
44.5k
  int i, div, k;
573
44.5k
  isl_int gcd;
574
44.5k
575
44.5k
  if (isl_int_is_one(morph->inv->row[0][0]))
576
44.5k
    return bset;
577
2
578
2
  
isl_int_init2
(gcd);
579
2
580
6
  for (i = 0; 
1 + i < morph->inv->n_row6
;
++i4
) {
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
2
    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);
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
4
          morph->inv->row[0][0]);
596
4
  }
597
2
598
2
  
isl_int_clear2
(gcd);
599
2
600
2
  return bset;
601
0
error:
602
0
  isl_int_clear(gcd);
603
0
  isl_basic_set_free(bset);
604
0
  return NULL;
605
44.5k
}
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
44.5k
{
615
44.5k
  isl_basic_set *res = NULL;
616
44.5k
  isl_mat *mat = NULL;
617
44.5k
  int i, k;
618
44.5k
  int max_stride;
619
44.5k
620
44.5k
  if (
!morph || 44.5k
!bset44.5k
)
621
2
    goto error;
622
44.5k
623
44.5k
  
isl_assert44.5k
(bset->ctx, isl_space_is_equal(bset->dim, morph->dom->dim),
624
44.5k
        goto error);
625
44.5k
626
44.5k
  max_stride = morph->inv->n_row - 1;
627
44.5k
  if (isl_int_is_one(morph->inv->row[0][0]))
628
44.5k
    max_stride = 0;
629
44.5k
  res = isl_basic_set_alloc_space(isl_space_copy(morph->ran->dim),
630
44.5k
    bset->n_div + max_stride, bset->n_eq + max_stride, bset->n_ineq);
631
44.5k
632
44.5k
  for (i = 0; 
i < bset->n_div44.5k
;
++i0
)
633
0
    
if (0
isl_basic_set_alloc_div(res) < 00
)
634
0
      goto error;
635
44.5k
636
44.5k
  mat = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
637
44.5k
          0, morph->inv->n_row);
638
44.5k
  mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
639
44.5k
  if (!mat)
640
0
    goto error;
641
44.5k
  
for (i = 0; 44.5k
i < bset->n_eq44.5k
;
++i22
) {
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
22
  }
649
44.5k
  isl_mat_free(mat);
650
44.5k
651
44.5k
  mat = isl_mat_sub_alloc6(bset->ctx, bset->ineq, 0, bset->n_ineq,
652
44.5k
          0, morph->inv->n_row);
653
44.5k
  mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
654
44.5k
  if (!mat)
655
0
    goto error;
656
609k
  
for (i = 0; 44.5k
i < bset->n_ineq609k
;
++i565k
) {
657
565k
    k = isl_basic_set_alloc_inequality(res);
658
565k
    if (k < 0)
659
0
      goto error;
660
565k
    isl_seq_cpy(res->ineq[k], mat->row[i], mat->n_col);
661
565k
    isl_seq_scale(res->ineq[k] + mat->n_col,
662
565k
        bset->ineq[i] + mat->n_col,
663
565k
        morph->inv->row[0][0], bset->n_div);
664
565k
  }
665
44.5k
  isl_mat_free(mat);
666
44.5k
667
44.5k
  mat = isl_mat_sub_alloc6(bset->ctx, bset->div, 0, bset->n_div,
668
44.5k
          1, morph->inv->n_row);
669
44.5k
  mat = isl_mat_product(mat, isl_mat_copy(morph->inv));
670
44.5k
  if (!mat)
671
0
    goto error;
672
44.5k
  
for (i = 0; 44.5k
i < bset->n_div44.5k
;
++i0
) {
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
0
  }
680
44.5k
  isl_mat_free(mat);
681
44.5k
682
44.5k
  res = add_strides(res, morph);
683
44.5k
684
44.5k
  if (isl_basic_set_is_rational(bset))
685
3
    res = isl_basic_set_set_rational(res);
686
44.5k
687
44.5k
  res = isl_basic_set_simplify(res);
688
44.5k
  res = isl_basic_set_finalize(res);
689
44.5k
690
44.5k
  res = isl_basic_set_intersect(res, isl_basic_set_copy(morph->ran));
691
44.5k
692
44.5k
  isl_morph_free(morph);
693
44.5k
  isl_basic_set_free(bset);
694
44.5k
  return res;
695
2
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
2
  return NULL;
701
44.5k
}
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);
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
) {
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
0
error:
736
0
  isl_set_free(set);
737
0
  isl_morph_free(morph);
738
0
  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
0
error:
766
0
  isl_morph_free(morph1);
767
0
  isl_morph_free(morph2);
768
0
  return NULL;
769
6
}
770
771
__isl_give isl_morph *isl_morph_inverse(__isl_take isl_morph *morph)
772
44.0k
{
773
44.0k
  isl_basic_set *bset;
774
44.0k
  isl_mat *mat;
775
44.0k
776
44.0k
  morph = isl_morph_cow(morph);
777
44.0k
  if (!morph)
778
0
    return NULL;
779
44.0k
780
44.0k
  bset = morph->dom;
781
44.0k
  morph->dom = morph->ran;
782
44.0k
  morph->ran = bset;
783
44.0k
784
44.0k
  mat = morph->map;
785
44.0k
  morph->map = morph->inv;
786
44.0k
  morph->inv = mat;
787
44.0k
788
44.0k
  return morph;
789
44.0k
}
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
44.0k
{
825
44.0k
  if (!morph)
826
0
    goto error;
827
44.0k
828
44.0k
  vec = isl_mat_vec_product(isl_mat_copy(morph->map), vec);
829
44.0k
830
44.0k
  isl_morph_free(morph);
831
44.0k
  return vec;
832
0
error:
833
0
  isl_morph_free(morph);
834
0
  isl_vec_free(vec);
835
0
  return NULL;
836
44.0k
}