Coverage Report

Created: 2017-04-27 19:33

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