Coverage Report

Created: 2017-11-21 03:47

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_aff.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2011      INRIA Saclay
3
 * Copyright 2011      Sven Verdoolaege
4
 * Copyright 2012-2014 Ecole Normale Superieure
5
 * Copyright 2014      INRIA Rocquencourt
6
 *
7
 * Use of this software is governed by the MIT license
8
 *
9
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
10
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11
 * 91893 Orsay, France
12
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
14
 * B.P. 105 - 78153 Le Chesnay, France
15
 */
16
17
#include <isl_ctx_private.h>
18
#define ISL_DIM_H
19
#include <isl_map_private.h>
20
#include <isl_union_map_private.h>
21
#include <isl_aff_private.h>
22
#include <isl_space_private.h>
23
#include <isl_local_space_private.h>
24
#include <isl_vec_private.h>
25
#include <isl_mat_private.h>
26
#include <isl/constraint.h>
27
#include <isl_seq.h>
28
#include <isl/set.h>
29
#include <isl_val_private.h>
30
#include <isl/deprecated/aff_int.h>
31
#include <isl_config.h>
32
33
#undef BASE
34
#define BASE aff
35
36
#include <isl_list_templ.c>
37
38
#undef BASE
39
#define BASE pw_aff
40
41
#include <isl_list_templ.c>
42
43
#undef BASE
44
#define BASE union_pw_aff
45
46
#include <isl_list_templ.c>
47
48
#undef BASE
49
#define BASE union_pw_multi_aff
50
51
#include <isl_list_templ.c>
52
53
__isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
54
  __isl_take isl_vec *v)
55
303k
{
56
303k
  isl_aff *aff;
57
303k
58
303k
  if (!ls || !v)
59
0
    goto error;
60
303k
61
303k
  aff = isl_calloc_type(v->ctx, struct isl_aff);
62
303k
  if (!aff)
63
0
    goto error;
64
303k
65
303k
  aff->ref = 1;
66
303k
  aff->ls = ls;
67
303k
  aff->v = v;
68
303k
69
303k
  return aff;
70
0
error:
71
0
  isl_local_space_free(ls);
72
0
  isl_vec_free(v);
73
0
  return NULL;
74
303k
}
75
76
__isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
77
160k
{
78
160k
  isl_ctx *ctx;
79
160k
  isl_vec *v;
80
160k
  unsigned total;
81
160k
82
160k
  if (!ls)
83
0
    return NULL;
84
160k
85
160k
  ctx = isl_local_space_get_ctx(ls);
86
160k
  if (!isl_local_space_divs_known(ls))
87
160k
    
isl_die0
(ctx, isl_error_invalid, "local space has unknown divs",
88
160k
      goto error);
89
160k
  if (!isl_local_space_is_set(ls))
90
160k
    
isl_die0
(ctx, isl_error_invalid,
91
160k
      "domain of affine expression should be a set",
92
160k
      goto error);
93
160k
94
160k
  total = isl_local_space_dim(ls, isl_dim_all);
95
160k
  v = isl_vec_alloc(ctx, 1 + 1 + total);
96
160k
  return isl_aff_alloc_vec(ls, v);
97
0
error:
98
0
  isl_local_space_free(ls);
99
0
  return NULL;
100
160k
}
101
102
__isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
103
54.7k
{
104
54.7k
  isl_aff *aff;
105
54.7k
106
54.7k
  aff = isl_aff_alloc(ls);
107
54.7k
  if (!aff)
108
0
    return NULL;
109
54.7k
110
54.7k
  isl_int_set_si(aff->v->el[0], 1);
111
54.7k
  isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
112
54.7k
113
54.7k
  return aff;
114
54.7k
}
115
116
/* Return a piecewise affine expression defined on the specified domain
117
 * that is equal to zero.
118
 */
119
__isl_give isl_pw_aff *isl_pw_aff_zero_on_domain(__isl_take isl_local_space *ls)
120
628
{
121
628
  return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
122
628
}
123
124
/* Return an affine expression defined on the specified domain
125
 * that represents NaN.
126
 */
127
__isl_give isl_aff *isl_aff_nan_on_domain(__isl_take isl_local_space *ls)
128
108
{
129
108
  isl_aff *aff;
130
108
131
108
  aff = isl_aff_alloc(ls);
132
108
  if (!aff)
133
0
    return NULL;
134
108
135
108
  isl_seq_clr(aff->v->el, aff->v->size);
136
108
137
108
  return aff;
138
108
}
139
140
/* Return a piecewise affine expression defined on the specified domain
141
 * that represents NaN.
142
 */
143
__isl_give isl_pw_aff *isl_pw_aff_nan_on_domain(__isl_take isl_local_space *ls)
144
32
{
145
32
  return isl_pw_aff_from_aff(isl_aff_nan_on_domain(ls));
146
32
}
147
148
/* Return an affine expression that is equal to "val" on
149
 * domain local space "ls".
150
 */
151
__isl_give isl_aff *isl_aff_val_on_domain(__isl_take isl_local_space *ls,
152
  __isl_take isl_val *val)
153
28.1k
{
154
28.1k
  isl_aff *aff;
155
28.1k
156
28.1k
  if (!ls || !val)
157
0
    goto error;
158
28.1k
  if (!isl_val_is_rat(val))
159
28.1k
    
isl_die0
(isl_val_get_ctx(val), isl_error_invalid,
160
28.1k
      "expecting rational value", goto error);
161
28.1k
162
28.1k
  aff = isl_aff_alloc(isl_local_space_copy(ls));
163
28.1k
  if (!aff)
164
0
    goto error;
165
28.1k
166
28.1k
  isl_seq_clr(aff->v->el + 2, aff->v->size - 2);
167
28.1k
  isl_int_set(aff->v->el[1], val->n);
168
28.1k
  isl_int_set(aff->v->el[0], val->d);
169
28.1k
170
28.1k
  isl_local_space_free(ls);
171
28.1k
  isl_val_free(val);
172
28.1k
  return aff;
173
0
error:
174
0
  isl_local_space_free(ls);
175
0
  isl_val_free(val);
176
0
  return NULL;
177
28.1k
}
178
179
/* Return an affine expression that is equal to the specified dimension
180
 * in "ls".
181
 */
182
__isl_give isl_aff *isl_aff_var_on_domain(__isl_take isl_local_space *ls,
183
  enum isl_dim_type type, unsigned pos)
184
29.1k
{
185
29.1k
  isl_space *space;
186
29.1k
  isl_aff *aff;
187
29.1k
188
29.1k
  if (!ls)
189
0
    return NULL;
190
29.1k
191
29.1k
  space = isl_local_space_get_space(ls);
192
29.1k
  if (!space)
193
0
    goto error;
194
29.1k
  if (isl_space_is_map(space))
195
29.1k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
196
29.1k
      "expecting (parameter) set space", goto error);
197
29.1k
  if (pos >= isl_local_space_dim(ls, type))
198
29.1k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
199
29.1k
      "position out of bounds", goto error);
200
29.1k
201
29.1k
  isl_space_free(space);
202
29.1k
  aff = isl_aff_alloc(ls);
203
29.1k
  if (!aff)
204
0
    return NULL;
205
29.1k
206
29.1k
  pos += isl_local_space_offset(aff->ls, type);
207
29.1k
208
29.1k
  isl_int_set_si(aff->v->el[0], 1);
209
29.1k
  isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
210
29.1k
  isl_int_set_si(aff->v->el[1 + pos], 1);
211
29.1k
212
29.1k
  return aff;
213
0
error:
214
0
  isl_local_space_free(ls);
215
0
  isl_space_free(space);
216
0
  return NULL;
217
29.1k
}
218
219
/* Return a piecewise affine expression that is equal to
220
 * the specified dimension in "ls".
221
 */
222
__isl_give isl_pw_aff *isl_pw_aff_var_on_domain(__isl_take isl_local_space *ls,
223
  enum isl_dim_type type, unsigned pos)
224
539
{
225
539
  return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, type, pos));
226
539
}
227
228
__isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
229
1.23M
{
230
1.23M
  if (!aff)
231
0
    return NULL;
232
1.23M
233
1.23M
  aff->ref++;
234
1.23M
  return aff;
235
1.23M
}
236
237
__isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
238
143k
{
239
143k
  if (!aff)
240
0
    return NULL;
241
143k
242
143k
  return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
243
143k
         isl_vec_copy(aff->v));
244
143k
}
245
246
__isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
247
320k
{
248
320k
  if (!aff)
249
0
    return NULL;
250
320k
251
320k
  if (aff->ref == 1)
252
177k
    return aff;
253
143k
  aff->ref--;
254
143k
  return isl_aff_dup(aff);
255
143k
}
256
257
__isl_null isl_aff *isl_aff_free(__isl_take isl_aff *aff)
258
2.33M
{
259
2.33M
  if (!aff)
260
936k
    return NULL;
261
1.39M
262
1.39M
  if (--aff->ref > 0)
263
1.09M
    return NULL;
264
303k
265
303k
  isl_local_space_free(aff->ls);
266
303k
  isl_vec_free(aff->v);
267
303k
268
303k
  free(aff);
269
303k
270
303k
  return NULL;
271
303k
}
272
273
isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
274
1.63M
{
275
1.63M
  return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
276
1.63M
}
277
278
/* Return a hash value that digests "aff".
279
 */
280
uint32_t isl_aff_get_hash(__isl_keep isl_aff *aff)
281
0
{
282
0
  uint32_t hash, ls_hash, v_hash;
283
0
284
0
  if (!aff)
285
0
    return 0;
286
0
287
0
  hash = isl_hash_init();
288
0
  ls_hash = isl_local_space_get_hash(aff->ls);
289
0
  isl_hash_hash(hash, ls_hash);
290
0
  v_hash = isl_vec_get_hash(aff->v);
291
0
  isl_hash_hash(hash, v_hash);
292
0
293
0
  return hash;
294
0
}
295
296
/* Externally, an isl_aff has a map space, but internally, the
297
 * ls field corresponds to the domain of that space.
298
 */
299
int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
300
320k
{
301
320k
  if (!aff)
302
0
    return 0;
303
320k
  if (type == isl_dim_out)
304
0
    return 1;
305
320k
  if (type == isl_dim_in)
306
32.9k
    type = isl_dim_set;
307
320k
  return isl_local_space_dim(aff->ls, type);
308
320k
}
309
310
/* Return the position of the dimension of the given type and name
311
 * in "aff".
312
 * Return -1 if no such dimension can be found.
313
 */
314
int isl_aff_find_dim_by_name(__isl_keep isl_aff *aff, enum isl_dim_type type,
315
  const char *name)
316
0
{
317
0
  if (!aff)
318
0
    return -1;
319
0
  if (type == isl_dim_out)
320
0
    return -1;
321
0
  if (type == isl_dim_in)
322
0
    type = isl_dim_set;
323
0
  return isl_local_space_find_dim_by_name(aff->ls, type, name);
324
0
}
325
326
__isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
327
1.93M
{
328
1.93M
  return aff ? isl_local_space_get_space(aff->ls) : NULL;
329
1.93M
}
330
331
__isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
332
296k
{
333
296k
  isl_space *space;
334
296k
  if (!aff)
335
0
    return NULL;
336
296k
  space = isl_local_space_get_space(aff->ls);
337
296k
  space = isl_space_from_domain(space);
338
296k
  space = isl_space_add_dims(space, isl_dim_out, 1);
339
296k
  return space;
340
296k
}
341
342
__isl_give isl_local_space *isl_aff_get_domain_local_space(
343
  __isl_keep isl_aff *aff)
344
76.8k
{
345
76.8k
  return aff ? isl_local_space_copy(aff->ls) : NULL;
346
76.8k
}
347
348
__isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
349
72.3k
{
350
72.3k
  isl_local_space *ls;
351
72.3k
  if (!aff)
352
0
    return NULL;
353
72.3k
  ls = isl_local_space_copy(aff->ls);
354
72.3k
  ls = isl_local_space_from_domain(ls);
355
72.3k
  ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
356
72.3k
  return ls;
357
72.3k
}
358
359
/* Externally, an isl_aff has a map space, but internally, the
360
 * ls field corresponds to the domain of that space.
361
 */
362
const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
363
  enum isl_dim_type type, unsigned pos)
364
0
{
365
0
  if (!aff)
366
0
    return NULL;
367
0
  if (type == isl_dim_out)
368
0
    return NULL;
369
0
  if (type == isl_dim_in)
370
0
    type = isl_dim_set;
371
0
  return isl_local_space_get_dim_name(aff->ls, type, pos);
372
0
}
373
374
__isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
375
  __isl_take isl_space *dim)
376
82.9k
{
377
82.9k
  aff = isl_aff_cow(aff);
378
82.9k
  if (!aff || !dim)
379
0
    goto error;
380
82.9k
381
82.9k
  aff->ls = isl_local_space_reset_space(aff->ls, dim);
382
82.9k
  if (!aff->ls)
383
0
    return isl_aff_free(aff);
384
82.9k
385
82.9k
  return aff;
386
0
error:
387
0
  isl_aff_free(aff);
388
0
  isl_space_free(dim);
389
0
  return NULL;
390
82.9k
}
391
392
/* Reset the space of "aff".  This function is called from isl_pw_templ.c
393
 * and doesn't know if the space of an element object is represented
394
 * directly or through its domain.  It therefore passes along both.
395
 */
396
__isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
397
  __isl_take isl_space *space, __isl_take isl_space *domain)
398
66.8k
{
399
66.8k
  isl_space_free(space);
400
66.8k
  return isl_aff_reset_domain_space(aff, domain);
401
66.8k
}
402
403
/* Reorder the coefficients of the affine expression based
404
 * on the given reordering.
405
 * The reordering r is assumed to have been extended with the local
406
 * variables.
407
 */
408
static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
409
  __isl_take isl_reordering *r, int n_div)
410
9.63k
{
411
9.63k
  isl_vec *res;
412
9.63k
  int i;
413
9.63k
414
9.63k
  if (!vec || !r)
415
0
    goto error;
416
9.63k
417
9.63k
  res = isl_vec_alloc(vec->ctx,
418
9.63k
          2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
419
9.63k
  if (!res)
420
0
    goto error;
421
9.63k
  isl_seq_cpy(res->el, vec->el, 2);
422
9.63k
  isl_seq_clr(res->el + 2, res->size - 2);
423
27.8k
  for (i = 0; i < r->len; 
++i18.2k
)
424
18.2k
    isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
425
9.63k
426
9.63k
  isl_reordering_free(r);
427
9.63k
  isl_vec_free(vec);
428
9.63k
  return res;
429
0
error:
430
0
  isl_vec_free(vec);
431
0
  isl_reordering_free(r);
432
0
  return NULL;
433
9.63k
}
434
435
/* Reorder the dimensions of the domain of "aff" according
436
 * to the given reordering.
437
 */
438
__isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
439
  __isl_take isl_reordering *r)
440
9.63k
{
441
9.63k
  aff = isl_aff_cow(aff);
442
9.63k
  if (!aff)
443
0
    goto error;
444
9.63k
445
9.63k
  r = isl_reordering_extend(r, aff->ls->div->n_row);
446
9.63k
  aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
447
9.63k
        aff->ls->div->n_row);
448
9.63k
  aff->ls = isl_local_space_realign(aff->ls, r);
449
9.63k
450
9.63k
  if (!aff->v || !aff->ls)
451
0
    return isl_aff_free(aff);
452
9.63k
453
9.63k
  return aff;
454
0
error:
455
0
  isl_aff_free(aff);
456
0
  isl_reordering_free(r);
457
0
  return NULL;
458
9.63k
}
459
460
__isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff,
461
  __isl_take isl_space *model)
462
0
{
463
0
  isl_bool equal_params;
464
0
465
0
  if (!aff || !model)
466
0
    goto error;
467
0
468
0
  equal_params = isl_space_has_equal_params(aff->ls->dim, model);
469
0
  if (equal_params < 0)
470
0
    goto error;
471
0
  if (!equal_params) {
472
0
    isl_reordering *exp;
473
0
474
0
    model = isl_space_drop_dims(model, isl_dim_in,
475
0
          0, isl_space_dim(model, isl_dim_in));
476
0
    model = isl_space_drop_dims(model, isl_dim_out,
477
0
          0, isl_space_dim(model, isl_dim_out));
478
0
    exp = isl_parameter_alignment_reordering(aff->ls->dim, model);
479
0
    exp = isl_reordering_extend_space(exp,
480
0
          isl_aff_get_domain_space(aff));
481
0
    aff = isl_aff_realign_domain(aff, exp);
482
0
  }
483
0
484
0
  isl_space_free(model);
485
0
  return aff;
486
0
error:
487
0
  isl_space_free(model);
488
0
  isl_aff_free(aff);
489
0
  return NULL;
490
0
}
491
492
/* Is "aff" obviously equal to zero?
493
 *
494
 * If the denominator is zero, then "aff" is not equal to zero.
495
 */
496
isl_bool isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
497
1
{
498
1
  if (!aff)
499
0
    return isl_bool_error;
500
1
501
1
  if (isl_int_is_zero(aff->v->el[0]))
502
1
    
return isl_bool_false0
;
503
1
  return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
504
1
}
505
506
/* Does "aff" represent NaN?
507
 */
508
isl_bool isl_aff_is_nan(__isl_keep isl_aff *aff)
509
500k
{
510
500k
  if (!aff)
511
0
    return isl_bool_error;
512
500k
513
500k
  return isl_seq_first_non_zero(aff->v->el, 2) < 0;
514
500k
}
515
516
/* Are "aff1" and "aff2" obviously equal?
517
 *
518
 * NaN is not equal to anything, not even to another NaN.
519
 */
520
isl_bool isl_aff_plain_is_equal(__isl_keep isl_aff *aff1,
521
  __isl_keep isl_aff *aff2)
522
2.85k
{
523
2.85k
  isl_bool equal;
524
2.85k
525
2.85k
  if (!aff1 || !aff2)
526
0
    return isl_bool_error;
527
2.85k
528
2.85k
  if (isl_aff_is_nan(aff1) || isl_aff_is_nan(aff2))
529
0
    return isl_bool_false;
530
2.85k
531
2.85k
  equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
532
2.85k
  if (equal < 0 || !equal)
533
535
    return equal;
534
2.31k
535
2.31k
  return isl_vec_is_equal(aff1->v, aff2->v);
536
2.31k
}
537
538
/* Return the common denominator of "aff" in "v".
539
 *
540
 * We cannot return anything meaningful in case of a NaN.
541
 */
542
isl_stat isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
543
0
{
544
0
  if (!aff)
545
0
    return isl_stat_error;
546
0
  if (isl_aff_is_nan(aff))
547
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
548
0
      "cannot get denominator of NaN", return isl_stat_error);
549
0
  isl_int_set(*v, aff->v->el[0]);
550
0
  return isl_stat_ok;
551
0
}
552
553
/* Return the common denominator of "aff".
554
 */
555
__isl_give isl_val *isl_aff_get_denominator_val(__isl_keep isl_aff *aff)
556
8.29k
{
557
8.29k
  isl_ctx *ctx;
558
8.29k
559
8.29k
  if (!aff)
560
0
    return NULL;
561
8.29k
562
8.29k
  ctx = isl_aff_get_ctx(aff);
563
8.29k
  if (isl_aff_is_nan(aff))
564
0
    return isl_val_nan(ctx);
565
8.29k
  return isl_val_int_from_isl_int(ctx, aff->v->el[0]);
566
8.29k
}
567
568
/* Return the constant term of "aff" in "v".
569
 *
570
 * We cannot return anything meaningful in case of a NaN.
571
 */
572
int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
573
0
{
574
0
  if (!aff)
575
0
    return -1;
576
0
  if (isl_aff_is_nan(aff))
577
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
578
0
      "cannot get constant term of NaN", return -1);
579
0
  isl_int_set(*v, aff->v->el[1]);
580
0
  return 0;
581
0
}
582
583
/* Return the constant term of "aff".
584
 */
585
__isl_give isl_val *isl_aff_get_constant_val(__isl_keep isl_aff *aff)
586
9.52k
{
587
9.52k
  isl_ctx *ctx;
588
9.52k
  isl_val *v;
589
9.52k
590
9.52k
  if (!aff)
591
0
    return NULL;
592
9.52k
593
9.52k
  ctx = isl_aff_get_ctx(aff);
594
9.52k
  if (isl_aff_is_nan(aff))
595
0
    return isl_val_nan(ctx);
596
9.52k
  v = isl_val_rat_from_isl_int(ctx, aff->v->el[1], aff->v->el[0]);
597
9.52k
  return isl_val_normalize(v);
598
9.52k
}
599
600
/* Return the coefficient of the variable of type "type" at position "pos"
601
 * of "aff" in "v".
602
 *
603
 * We cannot return anything meaningful in case of a NaN.
604
 */
605
int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
606
  enum isl_dim_type type, int pos, isl_int *v)
607
0
{
608
0
  if (!aff)
609
0
    return -1;
610
0
611
0
  if (type == isl_dim_out)
612
0
    isl_die(aff->v->ctx, isl_error_invalid,
613
0
      "output/set dimension does not have a coefficient",
614
0
      return -1);
615
0
  if (type == isl_dim_in)
616
0
    type = isl_dim_set;
617
0
618
0
  if (pos >= isl_local_space_dim(aff->ls, type))
619
0
    isl_die(aff->v->ctx, isl_error_invalid,
620
0
      "position out of bounds", return -1);
621
0
622
0
  if (isl_aff_is_nan(aff))
623
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
624
0
      "cannot get coefficient of NaN", return -1);
625
0
  pos += isl_local_space_offset(aff->ls, type);
626
0
  isl_int_set(*v, aff->v->el[1 + pos]);
627
0
628
0
  return 0;
629
0
}
630
631
/* Return the coefficient of the variable of type "type" at position "pos"
632
 * of "aff".
633
 */
634
__isl_give isl_val *isl_aff_get_coefficient_val(__isl_keep isl_aff *aff,
635
  enum isl_dim_type type, int pos)
636
54.3k
{
637
54.3k
  isl_ctx *ctx;
638
54.3k
  isl_val *v;
639
54.3k
640
54.3k
  if (!aff)
641
0
    return NULL;
642
54.3k
643
54.3k
  ctx = isl_aff_get_ctx(aff);
644
54.3k
  if (type == isl_dim_out)
645
54.3k
    
isl_die0
(ctx, isl_error_invalid,
646
54.3k
      "output/set dimension does not have a coefficient",
647
54.3k
      return NULL);
648
54.3k
  if (type == isl_dim_in)
649
47.6k
    type = isl_dim_set;
650
54.3k
651
54.3k
  if (pos >= isl_local_space_dim(aff->ls, type))
652
54.3k
    
isl_die0
(ctx, isl_error_invalid,
653
54.3k
      "position out of bounds", return NULL);
654
54.3k
655
54.3k
  if (isl_aff_is_nan(aff))
656
0
    return isl_val_nan(ctx);
657
54.3k
  pos += isl_local_space_offset(aff->ls, type);
658
54.3k
  v = isl_val_rat_from_isl_int(ctx, aff->v->el[1 + pos], aff->v->el[0]);
659
54.3k
  return isl_val_normalize(v);
660
54.3k
}
661
662
/* Return the sign of the coefficient of the variable of type "type"
663
 * at position "pos" of "aff".
664
 */
665
int isl_aff_coefficient_sgn(__isl_keep isl_aff *aff, enum isl_dim_type type,
666
  int pos)
667
86
{
668
86
  isl_ctx *ctx;
669
86
670
86
  if (!aff)
671
0
    return 0;
672
86
673
86
  ctx = isl_aff_get_ctx(aff);
674
86
  if (type == isl_dim_out)
675
86
    
isl_die0
(ctx, isl_error_invalid,
676
86
      "output/set dimension does not have a coefficient",
677
86
      return 0);
678
86
  if (type == isl_dim_in)
679
63
    type = isl_dim_set;
680
86
681
86
  if (pos >= isl_local_space_dim(aff->ls, type))
682
86
    
isl_die0
(ctx, isl_error_invalid,
683
86
      "position out of bounds", return 0);
684
86
685
86
  pos += isl_local_space_offset(aff->ls, type);
686
86
  return isl_int_sgn(aff->v->el[1 + pos]);
687
86
}
688
689
/* Replace the denominator of "aff" by "v".
690
 *
691
 * A NaN is unaffected by this operation.
692
 */
693
__isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
694
0
{
695
0
  if (!aff)
696
0
    return NULL;
697
0
  if (isl_aff_is_nan(aff))
698
0
    return aff;
699
0
  aff = isl_aff_cow(aff);
700
0
  if (!aff)
701
0
    return NULL;
702
0
703
0
  aff->v = isl_vec_cow(aff->v);
704
0
  if (!aff->v)
705
0
    return isl_aff_free(aff);
706
0
707
0
  isl_int_set(aff->v->el[0], v);
708
0
709
0
  return aff;
710
0
}
711
712
/* Replace the numerator of the constant term of "aff" by "v".
713
 *
714
 * A NaN is unaffected by this operation.
715
 */
716
__isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
717
935
{
718
935
  if (!aff)
719
0
    return NULL;
720
935
  if (isl_aff_is_nan(aff))
721
0
    return aff;
722
935
  aff = isl_aff_cow(aff);
723
935
  if (!aff)
724
0
    return NULL;
725
935
726
935
  aff->v = isl_vec_cow(aff->v);
727
935
  if (!aff->v)
728
0
    return isl_aff_free(aff);
729
935
730
935
  isl_int_set(aff->v->el[1], v);
731
935
732
935
  return aff;
733
935
}
734
735
/* Replace the constant term of "aff" by "v".
736
 *
737
 * A NaN is unaffected by this operation.
738
 */
739
__isl_give isl_aff *isl_aff_set_constant_val(__isl_take isl_aff *aff,
740
  __isl_take isl_val *v)
741
36
{
742
36
  if (!aff || !v)
743
0
    goto error;
744
36
745
36
  if (isl_aff_is_nan(aff)) {
746
0
    isl_val_free(v);
747
0
    return aff;
748
0
  }
749
36
750
36
  if (!isl_val_is_rat(v))
751
36
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
752
36
      "expecting rational value", goto error);
753
36
754
36
  if (isl_int_eq(aff->v->el[1], v->n) &&
755
36
      
isl_int_eq34
(aff->v->el[0], v->d)) {
756
34
    isl_val_free(v);
757
34
    return aff;
758
34
  }
759
2
760
2
  aff = isl_aff_cow(aff);
761
2
  if (!aff)
762
0
    goto error;
763
2
  aff->v = isl_vec_cow(aff->v);
764
2
  if (!aff->v)
765
0
    goto error;
766
2
767
2
  if (isl_int_eq(aff->v->el[0], v->d)) {
768
2
    isl_int_set(aff->v->el[1], v->n);
769
2
  } else 
if (0
isl_int_is_one0
(v->d)) {
770
0
    isl_int_mul(aff->v->el[1], aff->v->el[0], v->n);
771
0
  } else {
772
0
    isl_seq_scale(aff->v->el + 1,
773
0
        aff->v->el + 1, v->d, aff->v->size - 1);
774
0
    isl_int_mul(aff->v->el[1], aff->v->el[0], v->n);
775
0
    isl_int_mul(aff->v->el[0], aff->v->el[0], v->d);
776
0
    aff->v = isl_vec_normalize(aff->v);
777
0
    if (!aff->v)
778
0
      goto error;
779
2
  }
780
2
781
2
  isl_val_free(v);
782
2
  return aff;
783
0
error:
784
0
  isl_aff_free(aff);
785
0
  isl_val_free(v);
786
0
  return NULL;
787
36
}
788
789
/* Add "v" to the constant term of "aff".
790
 *
791
 * A NaN is unaffected by this operation.
792
 */
793
__isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
794
22.9k
{
795
22.9k
  if (isl_int_is_zero(v))
796
22.9k
    
return aff4.41k
;
797
18.5k
798
18.5k
  if (!aff)
799
0
    return NULL;
800
18.5k
  if (isl_aff_is_nan(aff))
801
0
    return aff;
802
18.5k
  aff = isl_aff_cow(aff);
803
18.5k
  if (!aff)
804
0
    return NULL;
805
18.5k
806
18.5k
  aff->v = isl_vec_cow(aff->v);
807
18.5k
  if (!aff->v)
808
0
    return isl_aff_free(aff);
809
18.5k
810
18.5k
  isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
811
18.5k
812
18.5k
  return aff;
813
18.5k
}
814
815
/* Add "v" to the constant term of "aff".
816
 *
817
 * A NaN is unaffected by this operation.
818
 */
819
__isl_give isl_aff *isl_aff_add_constant_val(__isl_take isl_aff *aff,
820
  __isl_take isl_val *v)
821
66
{
822
66
  if (!aff || !v)
823
0
    goto error;
824
66
825
66
  if (isl_aff_is_nan(aff) || isl_val_is_zero(v)) {
826
0
    isl_val_free(v);
827
0
    return aff;
828
0
  }
829
66
830
66
  if (!isl_val_is_rat(v))
831
66
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
832
66
      "expecting rational value", goto error);
833
66
834
66
  aff = isl_aff_cow(aff);
835
66
  if (!aff)
836
0
    goto error;
837
66
838
66
  aff->v = isl_vec_cow(aff->v);
839
66
  if (!aff->v)
840
0
    goto error;
841
66
842
66
  if (isl_int_is_one(v->d)) {
843
66
    isl_int_addmul(aff->v->el[1], aff->v->el[0], v->n);
844
66
  } else 
if (0
isl_int_eq0
(aff->v->el[0], v->d)) {
845
0
    isl_int_add(aff->v->el[1], aff->v->el[1], v->n);
846
0
    aff->v = isl_vec_normalize(aff->v);
847
0
    if (!aff->v)
848
0
      goto error;
849
0
  } else {
850
0
    isl_seq_scale(aff->v->el + 1,
851
0
        aff->v->el + 1, v->d, aff->v->size - 1);
852
0
    isl_int_addmul(aff->v->el[1], aff->v->el[0], v->n);
853
0
    isl_int_mul(aff->v->el[0], aff->v->el[0], v->d);
854
0
    aff->v = isl_vec_normalize(aff->v);
855
0
    if (!aff->v)
856
0
      goto error;
857
66
  }
858
66
859
66
  isl_val_free(v);
860
66
  return aff;
861
0
error:
862
0
  isl_aff_free(aff);
863
0
  isl_val_free(v);
864
0
  return NULL;
865
66
}
866
867
__isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
868
17.4k
{
869
17.4k
  isl_int t;
870
17.4k
871
17.4k
  isl_int_init(t);
872
17.4k
  isl_int_set_si(t, v);
873
17.4k
  aff = isl_aff_add_constant(aff, t);
874
17.4k
  isl_int_clear(t);
875
17.4k
876
17.4k
  return aff;
877
17.4k
}
878
879
/* Add "v" to the numerator of the constant term of "aff".
880
 *
881
 * A NaN is unaffected by this operation.
882
 */
883
__isl_give isl_aff *isl_aff_add_constant_num(__isl_take isl_aff *aff, isl_int v)
884
114
{
885
114
  if (isl_int_is_zero(v))
886
114
    
return aff0
;
887
114
888
114
  if (!aff)
889
0
    return NULL;
890
114
  if (isl_aff_is_nan(aff))
891
0
    return aff;
892
114
  aff = isl_aff_cow(aff);
893
114
  if (!aff)
894
0
    return NULL;
895
114
896
114
  aff->v = isl_vec_cow(aff->v);
897
114
  if (!aff->v)
898
0
    return isl_aff_free(aff);
899
114
900
114
  isl_int_add(aff->v->el[1], aff->v->el[1], v);
901
114
902
114
  return aff;
903
114
}
904
905
/* Add "v" to the numerator of the constant term of "aff".
906
 *
907
 * A NaN is unaffected by this operation.
908
 */
909
__isl_give isl_aff *isl_aff_add_constant_num_si(__isl_take isl_aff *aff, int v)
910
114
{
911
114
  isl_int t;
912
114
913
114
  if (v == 0)
914
0
    return aff;
915
114
916
114
  isl_int_init(t);
917
114
  isl_int_set_si(t, v);
918
114
  aff = isl_aff_add_constant_num(aff, t);
919
114
  isl_int_clear(t);
920
114
921
114
  return aff;
922
114
}
923
924
/* Replace the numerator of the constant term of "aff" by "v".
925
 *
926
 * A NaN is unaffected by this operation.
927
 */
928
__isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
929
931
{
930
931
  if (!aff)
931
0
    return NULL;
932
931
  if (isl_aff_is_nan(aff))
933
0
    return aff;
934
931
  aff = isl_aff_cow(aff);
935
931
  if (!aff)
936
0
    return NULL;
937
931
938
931
  aff->v = isl_vec_cow(aff->v);
939
931
  if (!aff->v)
940
0
    return isl_aff_free(aff);
941
931
942
931
  isl_int_set_si(aff->v->el[1], v);
943
931
944
931
  return aff;
945
931
}
946
947
/* Replace the numerator of the coefficient of the variable of type "type"
948
 * at position "pos" of "aff" by "v".
949
 *
950
 * A NaN is unaffected by this operation.
951
 */
952
__isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
953
  enum isl_dim_type type, int pos, isl_int v)
954
2.09k
{
955
2.09k
  if (!aff)
956
0
    return NULL;
957
2.09k
958
2.09k
  if (type == isl_dim_out)
959
2.09k
    
isl_die0
(aff->v->ctx, isl_error_invalid,
960
2.09k
      "output/set dimension does not have a coefficient",
961
2.09k
      return isl_aff_free(aff));
962
2.09k
  if (type == isl_dim_in)
963
1.62k
    type = isl_dim_set;
964
2.09k
965
2.09k
  if (pos >= isl_local_space_dim(aff->ls, type))
966
2.09k
    
isl_die0
(aff->v->ctx, isl_error_invalid,
967
2.09k
      "position out of bounds", return isl_aff_free(aff));
968
2.09k
969
2.09k
  if (isl_aff_is_nan(aff))
970
0
    return aff;
971
2.09k
  aff = isl_aff_cow(aff);
972
2.09k
  if (!aff)
973
0
    return NULL;
974
2.09k
975
2.09k
  aff->v = isl_vec_cow(aff->v);
976
2.09k
  if (!aff->v)
977
0
    return isl_aff_free(aff);
978
2.09k
979
2.09k
  pos += isl_local_space_offset(aff->ls, type);
980
2.09k
  isl_int_set(aff->v->el[1 + pos], v);
981
2.09k
982
2.09k
  return aff;
983
2.09k
}
984
985
/* Replace the numerator of the coefficient of the variable of type "type"
986
 * at position "pos" of "aff" by "v".
987
 *
988
 * A NaN is unaffected by this operation.
989
 */
990
__isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
991
  enum isl_dim_type type, int pos, int v)
992
3.18k
{
993
3.18k
  if (!aff)
994
0
    return NULL;
995
3.18k
996
3.18k
  if (type == isl_dim_out)
997
3.18k
    
isl_die0
(aff->v->ctx, isl_error_invalid,
998
3.18k
      "output/set dimension does not have a coefficient",
999
3.18k
      return isl_aff_free(aff));
1000
3.18k
  if (type == isl_dim_in)
1001
3.06k
    type = isl_dim_set;
1002
3.18k
1003
3.18k
  if (pos < 0 || pos >= isl_local_space_dim(aff->ls, type))
1004
3.18k
    
isl_die0
(aff->v->ctx, isl_error_invalid,
1005
3.18k
      "position out of bounds", return isl_aff_free(aff));
1006
3.18k
1007
3.18k
  if (isl_aff_is_nan(aff))
1008
0
    return aff;
1009
3.18k
  pos += isl_local_space_offset(aff->ls, type);
1010
3.18k
  if (isl_int_cmp_si(aff->v->el[1 + pos], v) == 0)
1011
2
    return aff;
1012
3.18k
1013
3.18k
  aff = isl_aff_cow(aff);
1014
3.18k
  if (!aff)
1015
0
    return NULL;
1016
3.18k
1017
3.18k
  aff->v = isl_vec_cow(aff->v);
1018
3.18k
  if (!aff->v)
1019
0
    return isl_aff_free(aff);
1020
3.18k
1021
3.18k
  isl_int_set_si(aff->v->el[1 + pos], v);
1022
3.18k
1023
3.18k
  return aff;
1024
3.18k
}
1025
1026
/* Replace the coefficient of the variable of type "type" at position "pos"
1027
 * of "aff" by "v".
1028
 *
1029
 * A NaN is unaffected by this operation.
1030
 */
1031
__isl_give isl_aff *isl_aff_set_coefficient_val(__isl_take isl_aff *aff,
1032
  enum isl_dim_type type, int pos, __isl_take isl_val *v)
1033
0
{
1034
0
  if (!aff || !v)
1035
0
    goto error;
1036
0
1037
0
  if (type == isl_dim_out)
1038
0
    isl_die(aff->v->ctx, isl_error_invalid,
1039
0
      "output/set dimension does not have a coefficient",
1040
0
      goto error);
1041
0
  if (type == isl_dim_in)
1042
0
    type = isl_dim_set;
1043
0
1044
0
  if (pos >= isl_local_space_dim(aff->ls, type))
1045
0
    isl_die(aff->v->ctx, isl_error_invalid,
1046
0
      "position out of bounds", goto error);
1047
0
1048
0
  if (isl_aff_is_nan(aff)) {
1049
0
    isl_val_free(v);
1050
0
    return aff;
1051
0
  }
1052
0
  if (!isl_val_is_rat(v))
1053
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1054
0
      "expecting rational value", goto error);
1055
0
1056
0
  pos += isl_local_space_offset(aff->ls, type);
1057
0
  if (isl_int_eq(aff->v->el[1 + pos], v->n) &&
1058
0
      isl_int_eq(aff->v->el[0], v->d)) {
1059
0
    isl_val_free(v);
1060
0
    return aff;
1061
0
  }
1062
0
1063
0
  aff = isl_aff_cow(aff);
1064
0
  if (!aff)
1065
0
    goto error;
1066
0
  aff->v = isl_vec_cow(aff->v);
1067
0
  if (!aff->v)
1068
0
    goto error;
1069
0
1070
0
  if (isl_int_eq(aff->v->el[0], v->d)) {
1071
0
    isl_int_set(aff->v->el[1 + pos], v->n);
1072
0
  } else if (isl_int_is_one(v->d)) {
1073
0
    isl_int_mul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1074
0
  } else {
1075
0
    isl_seq_scale(aff->v->el + 1,
1076
0
        aff->v->el + 1, v->d, aff->v->size - 1);
1077
0
    isl_int_mul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1078
0
    isl_int_mul(aff->v->el[0], aff->v->el[0], v->d);
1079
0
    aff->v = isl_vec_normalize(aff->v);
1080
0
    if (!aff->v)
1081
0
      goto error;
1082
0
  }
1083
0
1084
0
  isl_val_free(v);
1085
0
  return aff;
1086
0
error:
1087
0
  isl_aff_free(aff);
1088
0
  isl_val_free(v);
1089
0
  return NULL;
1090
0
}
1091
1092
/* Add "v" to the coefficient of the variable of type "type"
1093
 * at position "pos" of "aff".
1094
 *
1095
 * A NaN is unaffected by this operation.
1096
 */
1097
__isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
1098
  enum isl_dim_type type, int pos, isl_int v)
1099
19.9k
{
1100
19.9k
  if (!aff)
1101
0
    return NULL;
1102
19.9k
1103
19.9k
  if (type == isl_dim_out)
1104
19.9k
    
isl_die0
(aff->v->ctx, isl_error_invalid,
1105
19.9k
      "output/set dimension does not have a coefficient",
1106
19.9k
      return isl_aff_free(aff));
1107
19.9k
  if (type == isl_dim_in)
1108
18.1k
    type = isl_dim_set;
1109
19.9k
1110
19.9k
  if (pos >= isl_local_space_dim(aff->ls, type))
1111
19.9k
    
isl_die0
(aff->v->ctx, isl_error_invalid,
1112
19.9k
      "position out of bounds", return isl_aff_free(aff));
1113
19.9k
1114
19.9k
  if (isl_aff_is_nan(aff))
1115
0
    return aff;
1116
19.9k
  aff = isl_aff_cow(aff);
1117
19.9k
  if (!aff)
1118
0
    return NULL;
1119
19.9k
1120
19.9k
  aff->v = isl_vec_cow(aff->v);
1121
19.9k
  if (!aff->v)
1122
0
    return isl_aff_free(aff);
1123
19.9k
1124
19.9k
  pos += isl_local_space_offset(aff->ls, type);
1125
19.9k
  isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
1126
19.9k
1127
19.9k
  return aff;
1128
19.9k
}
1129
1130
/* Add "v" to the coefficient of the variable of type "type"
1131
 * at position "pos" of "aff".
1132
 *
1133
 * A NaN is unaffected by this operation.
1134
 */
1135
__isl_give isl_aff *isl_aff_add_coefficient_val(__isl_take isl_aff *aff,
1136
  enum isl_dim_type type, int pos, __isl_take isl_val *v)
1137
0
{
1138
0
  if (!aff || !v)
1139
0
    goto error;
1140
0
1141
0
  if (isl_val_is_zero(v)) {
1142
0
    isl_val_free(v);
1143
0
    return aff;
1144
0
  }
1145
0
1146
0
  if (type == isl_dim_out)
1147
0
    isl_die(aff->v->ctx, isl_error_invalid,
1148
0
      "output/set dimension does not have a coefficient",
1149
0
      goto error);
1150
0
  if (type == isl_dim_in)
1151
0
    type = isl_dim_set;
1152
0
1153
0
  if (pos >= isl_local_space_dim(aff->ls, type))
1154
0
    isl_die(aff->v->ctx, isl_error_invalid,
1155
0
      "position out of bounds", goto error);
1156
0
1157
0
  if (isl_aff_is_nan(aff)) {
1158
0
    isl_val_free(v);
1159
0
    return aff;
1160
0
  }
1161
0
  if (!isl_val_is_rat(v))
1162
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1163
0
      "expecting rational value", goto error);
1164
0
1165
0
  aff = isl_aff_cow(aff);
1166
0
  if (!aff)
1167
0
    goto error;
1168
0
1169
0
  aff->v = isl_vec_cow(aff->v);
1170
0
  if (!aff->v)
1171
0
    goto error;
1172
0
1173
0
  pos += isl_local_space_offset(aff->ls, type);
1174
0
  if (isl_int_is_one(v->d)) {
1175
0
    isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1176
0
  } else if (isl_int_eq(aff->v->el[0], v->d)) {
1177
0
    isl_int_add(aff->v->el[1 + pos], aff->v->el[1 + pos], v->n);
1178
0
    aff->v = isl_vec_normalize(aff->v);
1179
0
    if (!aff->v)
1180
0
      goto error;
1181
0
  } else {
1182
0
    isl_seq_scale(aff->v->el + 1,
1183
0
        aff->v->el + 1, v->d, aff->v->size - 1);
1184
0
    isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1185
0
    isl_int_mul(aff->v->el[0], aff->v->el[0], v->d);
1186
0
    aff->v = isl_vec_normalize(aff->v);
1187
0
    if (!aff->v)
1188
0
      goto error;
1189
0
  }
1190
0
1191
0
  isl_val_free(v);
1192
0
  return aff;
1193
0
error:
1194
0
  isl_aff_free(aff);
1195
0
  isl_val_free(v);
1196
0
  return NULL;
1197
0
}
1198
1199
__isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
1200
  enum isl_dim_type type, int pos, int v)
1201
19.9k
{
1202
19.9k
  isl_int t;
1203
19.9k
1204
19.9k
  isl_int_init(t);
1205
19.9k
  isl_int_set_si(t, v);
1206
19.9k
  aff = isl_aff_add_coefficient(aff, type, pos, t);
1207
19.9k
  isl_int_clear(t);
1208
19.9k
1209
19.9k
  return aff;
1210
19.9k
}
1211
1212
__isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
1213
97
{
1214
97
  if (!aff)
1215
0
    return NULL;
1216
97
1217
97
  return isl_local_space_get_div(aff->ls, pos);
1218
97
}
1219
1220
/* Return the negation of "aff".
1221
 *
1222
 * As a special case, -NaN = NaN.
1223
 */
1224
__isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
1225
27.2k
{
1226
27.2k
  if (!aff)
1227
0
    return NULL;
1228
27.2k
  if (isl_aff_is_nan(aff))
1229
1
    return aff;
1230
27.2k
  aff = isl_aff_cow(aff);
1231
27.2k
  if (!aff)
1232
0
    return NULL;
1233
27.2k
  aff->v = isl_vec_cow(aff->v);
1234
27.2k
  if (!aff->v)
1235
0
    return isl_aff_free(aff);
1236
27.2k
1237
27.2k
  isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
1238
27.2k
1239
27.2k
  return aff;
1240
27.2k
}
1241
1242
/* Remove divs from the local space that do not appear in the affine
1243
 * expression.
1244
 * We currently only remove divs at the end.
1245
 * Some intermediate divs may also not appear directly in the affine
1246
 * expression, but we would also need to check that no other divs are
1247
 * defined in terms of them.
1248
 */
1249
__isl_give isl_aff *isl_aff_remove_unused_divs(__isl_take isl_aff *aff)
1250
50.4k
{
1251
50.4k
  int pos;
1252
50.4k
  int off;
1253
50.4k
  int n;
1254
50.4k
1255
50.4k
  if (!aff)
1256
0
    return NULL;
1257
50.4k
1258
50.4k
  n = isl_local_space_dim(aff->ls, isl_dim_div);
1259
50.4k
  off = isl_local_space_offset(aff->ls, isl_dim_div);
1260
50.4k
1261
50.4k
  pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
1262
50.4k
  if (pos == n)
1263
48.8k
    return aff;
1264
1.58k
1265
1.58k
  aff = isl_aff_cow(aff);
1266
1.58k
  if (!aff)
1267
0
    return NULL;
1268
1.58k
1269
1.58k
  aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
1270
1.58k
  aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
1271
1.58k
  if (!aff->ls || !aff->v)
1272
0
    return isl_aff_free(aff);
1273
1.58k
1274
1.58k
  return aff;
1275
1.58k
}
1276
1277
/* Look for any divs in the aff->ls with a denominator equal to one
1278
 * and plug them into the affine expression and any subsequent divs
1279
 * that may reference the div.
1280
 */
1281
static __isl_give isl_aff *plug_in_integral_divs(__isl_take isl_aff *aff)
1282
40.5k
{
1283
40.5k
  int i, n;
1284
40.5k
  int len;
1285
40.5k
  isl_int v;
1286
40.5k
  isl_vec *vec;
1287
40.5k
  isl_local_space *ls;
1288
40.5k
  unsigned pos;
1289
40.5k
1290
40.5k
  if (!aff)
1291
0
    return NULL;
1292
40.5k
1293
40.5k
  n = isl_local_space_dim(aff->ls, isl_dim_div);
1294
40.5k
  len = aff->v->size;
1295
48.0k
  for (i = 0; i < n; 
++i7.42k
) {
1296
7.42k
    if (!isl_int_is_one(aff->ls->div->row[i][0]))
1297
7.42k
      
continue7.05k
;
1298
373
    ls = isl_local_space_copy(aff->ls);
1299
373
    ls = isl_local_space_substitute_seq(ls, isl_dim_div, i,
1300
373
        aff->ls->div->row[i], len, i + 1, n - (i + 1));
1301
373
    vec = isl_vec_copy(aff->v);
1302
373
    vec = isl_vec_cow(vec);
1303
373
    if (!ls || !vec)
1304
0
      goto error;
1305
373
1306
373
    isl_int_init(v);
1307
373
1308
373
    pos = isl_local_space_offset(aff->ls, isl_dim_div) + i;
1309
373
    isl_seq_substitute(vec->el, pos, aff->ls->div->row[i],
1310
373
          len, len, v);
1311
373
1312
373
    isl_int_clear(v);
1313
7.42k
1314
7.42k
    isl_vec_free(aff->v);
1315
7.42k
    aff->v = vec;
1316
7.42k
    isl_local_space_free(aff->ls);
1317
7.42k
    aff->ls = ls;
1318
7.42k
  }
1319
40.5k
1320
40.5k
  return aff;
1321
0
error:
1322
0
  isl_vec_free(vec);
1323
0
  isl_local_space_free(ls);
1324
0
  return isl_aff_free(aff);
1325
40.5k
}
1326
1327
/* Look for any divs j that appear with a unit coefficient inside
1328
 * the definitions of other divs i and plug them into the definitions
1329
 * of the divs i.
1330
 *
1331
 * In particular, an expression of the form
1332
 *
1333
 *  floor((f(..) + floor(g(..)/n))/m)
1334
 *
1335
 * is simplified to
1336
 *
1337
 *  floor((n * f(..) + g(..))/(n * m))
1338
 *
1339
 * This simplification is correct because we can move the expression
1340
 * f(..) into the inner floor in the original expression to obtain
1341
 *
1342
 *  floor(floor((n * f(..) + g(..))/n)/m)
1343
 *
1344
 * from which we can derive the simplified expression.
1345
 */
1346
static __isl_give isl_aff *plug_in_unit_divs(__isl_take isl_aff *aff)
1347
40.5k
{
1348
40.5k
  int i, j, n;
1349
40.5k
  int off;
1350
40.5k
1351
40.5k
  if (!aff)
1352
0
    return NULL;
1353
40.5k
1354
40.5k
  n = isl_local_space_dim(aff->ls, isl_dim_div);
1355
40.5k
  off = isl_local_space_offset(aff->ls, isl_dim_div);
1356
42.2k
  for (i = 1; i < n; 
++i1.64k
) {
1357
4.10k
    for (j = 0; j < i; 
++j2.45k
) {
1358
2.45k
      if (!isl_int_is_one(aff->ls->div->row[i][1 + off + j]))
1359
2.45k
        
continue2.28k
;
1360
173
      aff->ls = isl_local_space_substitute_seq(aff->ls,
1361
173
        isl_dim_div, j, aff->ls->div->row[j],
1362
173
        aff->v->size, i, 1);
1363
173
      if (!aff->ls)
1364
0
        return isl_aff_free(aff);
1365
2.45k
    }
1366
1.64k
  }
1367
40.5k
1368
40.5k
  return aff;
1369
40.5k
}
1370
1371
/* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
1372
 *
1373
 * Even though this function is only called on isl_affs with a single
1374
 * reference, we are careful to only change aff->v and aff->ls together.
1375
 */
1376
static __isl_give isl_aff *swap_div(__isl_take isl_aff *aff, int a, int b)
1377
985
{
1378
985
  unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
1379
985
  isl_local_space *ls;
1380
985
  isl_vec *v;
1381
985
1382
985
  ls = isl_local_space_copy(aff->ls);
1383
985
  ls = isl_local_space_swap_div(ls, a, b);
1384
985
  v = isl_vec_copy(aff->v);
1385
985
  v = isl_vec_cow(v);
1386
985
  if (!ls || !v)
1387
0
    goto error;
1388
985
1389
985
  isl_int_swap(v->el[1 + off + a], v->el[1 + off + b]);
1390
985
  isl_vec_free(aff->v);
1391
985
  aff->v = v;
1392
985
  isl_local_space_free(aff->ls);
1393
985
  aff->ls = ls;
1394
985
1395
985
  return aff;
1396
0
error:
1397
0
  isl_vec_free(v);
1398
0
  isl_local_space_free(ls);
1399
0
  return isl_aff_free(aff);
1400
985
}
1401
1402
/* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
1403
 *
1404
 * We currently do not actually remove div "b", but simply add its
1405
 * coefficient to that of "a" and then zero it out.
1406
 */
1407
static __isl_give isl_aff *merge_divs(__isl_take isl_aff *aff, int a, int b)
1408
118
{
1409
118
  unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
1410
118
1411
118
  if (isl_int_is_zero(aff->v->el[1 + off + b]))
1412
118
    
return aff75
;
1413
43
1414
43
  aff->v = isl_vec_cow(aff->v);
1415
43
  if (!aff->v)
1416
0
    return isl_aff_free(aff);
1417
43
1418
43
  isl_int_add(aff->v->el[1 + off + a],
1419
43
        aff->v->el[1 + off + a], aff->v->el[1 + off + b]);
1420
43
  isl_int_set_si(aff->v->el[1 + off + b], 0);
1421
118
1422
118
  return aff;
1423
118
}
1424
1425
/* Sort the divs in the local space of "aff" according to
1426
 * the comparison function "cmp_row" in isl_local_space.c,
1427
 * combining the coefficients of identical divs.
1428
 *
1429
 * Reordering divs does not change the semantics of "aff",
1430
 * so there is no need to call isl_aff_cow.
1431
 * Moreover, this function is currently only called on isl_affs
1432
 * with a single reference.
1433
 */
1434
static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff)
1435
40.5k
{
1436
40.5k
  int i, j, n;
1437
40.5k
1438
40.5k
  if (!aff)
1439
0
    return NULL;
1440
40.5k
1441
40.5k
  n = isl_aff_dim(aff, isl_dim_div);
1442
42.2k
  for (i = 1; i < n; 
++i1.64k
) {
1443
2.74k
    for (j = i - 1; j >= 0; 
--j1.10k
) {
1444
2.09k
      int cmp = isl_mat_cmp_div(aff->ls->div, j, j + 1);
1445
2.09k
      if (cmp < 0)
1446
993
        break;
1447
1.10k
      if (cmp == 0)
1448
118
        aff = merge_divs(aff, j, j + 1);
1449
985
      else
1450
985
        aff = swap_div(aff, j, j + 1);
1451
1.10k
      if (!aff)
1452
0
        return NULL;
1453
2.09k
    }
1454
1.64k
  }
1455
40.5k
1456
40.5k
  return aff;
1457
40.5k
}
1458
1459
/* Normalize the representation of "aff".
1460
 *
1461
 * This function should only be called of "new" isl_affs, i.e.,
1462
 * with only a single reference.  We therefore do not need to
1463
 * worry about affecting other instances.
1464
 */
1465
__isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
1466
40.5k
{
1467
40.5k
  if (!aff)
1468
0
    return NULL;
1469
40.5k
  aff->v = isl_vec_normalize(aff->v);
1470
40.5k
  if (!aff->v)
1471
0
    return isl_aff_free(aff);
1472
40.5k
  aff = plug_in_integral_divs(aff);
1473
40.5k
  aff = plug_in_unit_divs(aff);
1474
40.5k
  aff = sort_divs(aff);
1475
40.5k
  aff = isl_aff_remove_unused_divs(aff);
1476
40.5k
  return aff;
1477
40.5k
}
1478
1479
/* Given f, return floor(f).
1480
 * If f is an integer expression, then just return f.
1481
 * If f is a constant, then return the constant floor(f).
1482
 * Otherwise, if f = g/m, write g = q m + r,
1483
 * create a new div d = [r/m] and return the expression q + d.
1484
 * The coefficients in r are taken to lie between -m/2 and m/2.
1485
 *
1486
 * reduce_div_coefficients performs the same normalization.
1487
 *
1488
 * As a special case, floor(NaN) = NaN.
1489
 */
1490
__isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
1491
18.3k
{
1492
18.3k
  int i;
1493
18.3k
  int size;
1494
18.3k
  isl_ctx *ctx;
1495
18.3k
  isl_vec *div;
1496
18.3k
1497
18.3k
  if (!aff)
1498
0
    return NULL;
1499
18.3k
1500
18.3k
  if (isl_aff_is_nan(aff))
1501
0
    return aff;
1502
18.3k
  if (isl_int_is_one(aff->v->el[0]))
1503
18.3k
    
return aff14.1k
;
1504
4.17k
1505
4.17k
  aff = isl_aff_cow(aff);
1506
4.17k
  if (!aff)
1507
0
    return NULL;
1508
4.17k
1509
4.17k
  aff->v = isl_vec_cow(aff->v);
1510
4.17k
  if (!aff->v)
1511
0
    return isl_aff_free(aff);
1512
4.17k
1513
4.17k
  if (isl_aff_is_cst(aff)) {
1514
192
    isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
1515
192
    isl_int_set_si(aff->v->el[0], 1);
1516
192
    return aff;
1517
192
  }
1518
3.97k
1519
3.97k
  div = isl_vec_copy(aff->v);
1520
3.97k
  div = isl_vec_cow(div);
1521
3.97k
  if (!div)
1522
0
    return isl_aff_free(aff);
1523
3.97k
1524
3.97k
  ctx = isl_aff_get_ctx(aff);
1525
3.97k
  isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
1526
17.0k
  for (i = 1; i < aff->v->size; 
++i13.0k
) {
1527
13.0k
    isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
1528
13.0k
    isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
1529
13.0k
    if (isl_int_gt(div->el[i], aff->v->el[0])) {
1530
1.49k
      isl_int_sub(div->el[i], div->el[i], div->el[0]);
1531
1.49k
      isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
1532
1.49k
    }
1533
13.0k
  }
1534
3.97k
1535
3.97k
  aff->ls = isl_local_space_add_div(aff->ls, div);
1536
3.97k
  if (!aff->ls)
1537
0
    return isl_aff_free(aff);
1538
3.97k
1539
3.97k
  size = aff->v->size;
1540
3.97k
  aff->v = isl_vec_extend(aff->v, size + 1);
1541
3.97k
  if (!aff->v)
1542
0
    return isl_aff_free(aff);
1543
3.97k
  isl_int_set_si(aff->v->el[0], 1);
1544
3.97k
  isl_int_set_si(aff->v->el[size], 1);
1545
18.3k
1546
18.3k
  aff = isl_aff_normalize(aff);
1547
18.3k
1548
18.3k
  return aff;
1549
18.3k
}
1550
1551
/* Compute
1552
 *
1553
 *  aff mod m = aff - m * floor(aff/m)
1554
 */
1555
__isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
1556
0
{
1557
0
  isl_aff *res;
1558
0
1559
0
  res = isl_aff_copy(aff);
1560
0
  aff = isl_aff_scale_down(aff, m);
1561
0
  aff = isl_aff_floor(aff);
1562
0
  aff = isl_aff_scale(aff, m);
1563
0
  res = isl_aff_sub(res, aff);
1564
0
1565
0
  return res;
1566
0
}
1567
1568
/* Compute
1569
 *
1570
 *  aff mod m = aff - m * floor(aff/m)
1571
 *
1572
 * with m an integer value.
1573
 */
1574
__isl_give isl_aff *isl_aff_mod_val(__isl_take isl_aff *aff,
1575
  __isl_take isl_val *m)
1576
117
{
1577
117
  isl_aff *res;
1578
117
1579
117
  if (!aff || !m)
1580
0
    goto error;
1581
117
1582
117
  if (!isl_val_is_int(m))
1583
117
    
isl_die0
(isl_val_get_ctx(m), isl_error_invalid,
1584
117
      "expecting integer modulo", goto error);
1585
117
1586
117
  res = isl_aff_copy(aff);
1587
117
  aff = isl_aff_scale_down_val(aff, isl_val_copy(m));
1588
117
  aff = isl_aff_floor(aff);
1589
117
  aff = isl_aff_scale_val(aff, m);
1590
117
  res = isl_aff_sub(res, aff);
1591
117
1592
117
  return res;
1593
0
error:
1594
0
  isl_aff_free(aff);
1595
0
  isl_val_free(m);
1596
0
  return NULL;
1597
117
}
1598
1599
/* Compute
1600
 *
1601
 *  pwaff mod m = pwaff - m * floor(pwaff/m)
1602
 */
1603
__isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
1604
2.98k
{
1605
2.98k
  isl_pw_aff *res;
1606
2.98k
1607
2.98k
  res = isl_pw_aff_copy(pwaff);
1608
2.98k
  pwaff = isl_pw_aff_scale_down(pwaff, m);
1609
2.98k
  pwaff = isl_pw_aff_floor(pwaff);
1610
2.98k
  pwaff = isl_pw_aff_scale(pwaff, m);
1611
2.98k
  res = isl_pw_aff_sub(res, pwaff);
1612
2.98k
1613
2.98k
  return res;
1614
2.98k
}
1615
1616
/* Compute
1617
 *
1618
 *  pa mod m = pa - m * floor(pa/m)
1619
 *
1620
 * with m an integer value.
1621
 */
1622
__isl_give isl_pw_aff *isl_pw_aff_mod_val(__isl_take isl_pw_aff *pa,
1623
  __isl_take isl_val *m)
1624
2.98k
{
1625
2.98k
  if (!pa || !m)
1626
0
    goto error;
1627
2.98k
  if (!isl_val_is_int(m))
1628
2.98k
    
isl_die0
(isl_pw_aff_get_ctx(pa), isl_error_invalid,
1629
2.98k
      "expecting integer modulo", goto error);
1630
2.98k
  pa = isl_pw_aff_mod(pa, m->n);
1631
2.98k
  isl_val_free(m);
1632
2.98k
  return pa;
1633
0
error:
1634
0
  isl_pw_aff_free(pa);
1635
0
  isl_val_free(m);
1636
0
  return NULL;
1637
2.98k
}
1638
1639
/* Given f, return ceil(f).
1640
 * If f is an integer expression, then just return f.
1641
 * Otherwise, let f be the expression
1642
 *
1643
 *  e/m
1644
 *
1645
 * then return
1646
 *
1647
 *  floor((e + m - 1)/m)
1648
 *
1649
 * As a special case, ceil(NaN) = NaN.
1650
 */
1651
__isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
1652
3.20k
{
1653
3.20k
  if (!aff)
1654
0
    return NULL;
1655
3.20k
1656
3.20k
  if (isl_aff_is_nan(aff))
1657
0
    return aff;
1658
3.20k
  if (isl_int_is_one(aff->v->el[0]))
1659
3.20k
    
return aff3.12k
;
1660
81
1661
81
  aff = isl_aff_cow(aff);
1662
81
  if (!aff)
1663
0
    return NULL;
1664
81
  aff->v = isl_vec_cow(aff->v);
1665
81
  if (!aff->v)
1666
0
    return isl_aff_free(aff);
1667
81
1668
81
  isl_int_add(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
1669
81
  isl_int_sub_ui(aff->v->el[1], aff->v->el[1], 1);
1670
3.20k
  aff = isl_aff_floor(aff);
1671
3.20k
1672
3.20k
  return aff;
1673
3.20k
}
1674
1675
/* Apply the expansion computed by isl_merge_divs.
1676
 * The expansion itself is given by "exp" while the resulting
1677
 * list of divs is given by "div".
1678
 */
1679
__isl_give isl_aff *isl_aff_expand_divs(__isl_take isl_aff *aff,
1680
  __isl_take isl_mat *div, int *exp)
1681
46.1k
{
1682
46.1k
  int old_n_div;
1683
46.1k
  int new_n_div;
1684
46.1k
  int offset;
1685
46.1k
1686
46.1k
  aff = isl_aff_cow(aff);
1687
46.1k
  if (!aff || !div)
1688
0
    goto error;
1689
46.1k
1690
46.1k
  old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1691
46.1k
  new_n_div = isl_mat_rows(div);
1692
46.1k
  offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
1693
46.1k
1694
46.1k
  aff->v = isl_vec_expand(aff->v, offset, old_n_div, exp, new_n_div);
1695
46.1k
  aff->ls = isl_local_space_replace_divs(aff->ls, div);
1696
46.1k
  if (!aff->v || !aff->ls)
1697
0
    return isl_aff_free(aff);
1698
46.1k
  return aff;
1699
0
error:
1700
0
  isl_aff_free(aff);
1701
0
  isl_mat_free(div);
1702
0
  return NULL;
1703
46.1k
}
1704
1705
/* Add two affine expressions that live in the same local space.
1706
 */
1707
static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
1708
  __isl_take isl_aff *aff2)
1709
61.8k
{
1710
61.8k
  isl_int gcd, f;
1711
61.8k
1712
61.8k
  aff1 = isl_aff_cow(aff1);
1713
61.8k
  if (!aff1 || !aff2)
1714
0
    goto error;
1715
61.8k
1716
61.8k
  aff1->v = isl_vec_cow(aff1->v);
1717
61.8k
  if (!aff1->v)
1718
0
    goto error;
1719
61.8k
1720
61.8k
  isl_int_init(gcd);
1721
61.8k
  isl_int_init(f);
1722
61.8k
  isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
1723
61.8k
  isl_int_divexact(f, aff2->v->el[0], gcd);
1724
61.8k
  isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
1725
61.8k
  isl_int_divexact(f, aff1->v->el[0], gcd);
1726
61.8k
  isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
1727
61.8k
  isl_int_divexact(f, aff2->v->el[0], gcd);
1728
61.8k
  isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
1729
61.8k
  isl_int_clear(f);
1730
61.8k
  isl_int_clear(gcd);
1731
61.8k
1732
61.8k
  isl_aff_free(aff2);
1733
61.8k
  return aff1;
1734
0
error:
1735
0
  isl_aff_free(aff1);
1736
0
  isl_aff_free(aff2);
1737
0
  return NULL;
1738
61.8k
}
1739
1740
/* Return the sum of "aff1" and "aff2".
1741
 *
1742
 * If either of the two is NaN, then the result is NaN.
1743
 */
1744
__isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
1745
  __isl_take isl_aff *aff2)
1746
61.8k
{
1747
61.8k
  isl_ctx *ctx;
1748
61.8k
  int *exp1 = NULL;
1749
61.8k
  int *exp2 = NULL;
1750
61.8k
  isl_mat *div;
1751
61.8k
  int n_div1, n_div2;
1752
61.8k
1753
61.8k
  if (!aff1 || !aff2)
1754
0
    goto error;
1755
61.8k
1756
61.8k
  ctx = isl_aff_get_ctx(aff1);
1757
61.8k
  if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
1758
61.8k
    
isl_die0
(ctx, isl_error_invalid,
1759
61.8k
      "spaces don't match", goto error);
1760
61.8k
1761
61.8k
  if (isl_aff_is_nan(aff1)) {
1762
2
    isl_aff_free(aff2);
1763
2
    return aff1;
1764
2
  }
1765
61.8k
  if (isl_aff_is_nan(aff2)) {
1766
32
    isl_aff_free(aff1);
1767
32
    return aff2;
1768
32
  }
1769
61.8k
1770
61.8k
  n_div1 = isl_aff_dim(aff1, isl_dim_div);
1771
61.8k
  n_div2 = isl_aff_dim(aff2, isl_dim_div);
1772
61.8k
  if (n_div1 == 0 && 
n_div2 == 048.7k
)
1773
42.0k
    return add_expanded(aff1, aff2);
1774
19.7k
1775
19.7k
  exp1 = isl_alloc_array(ctx, int, n_div1);
1776
19.7k
  exp2 = isl_alloc_array(ctx, int, n_div2);
1777
19.7k
  if ((n_div1 && 
!exp113.0k
) || (n_div2 &&
!exp27.23k
))
1778
0
    goto error;
1779
19.7k
1780
19.7k
  div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
1781
19.7k
  aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
1782
19.7k
  aff2 = isl_aff_expand_divs(aff2, div, exp2);
1783
19.7k
  free(exp1);
1784
19.7k
  free(exp2);
1785
19.7k
1786
19.7k
  return add_expanded(aff1, aff2);
1787
0
error:
1788
0
  free(exp1);
1789
0
  free(exp2);
1790
0
  isl_aff_free(aff1);
1791
0
  isl_aff_free(aff2);
1792
0
  return NULL;
1793
61.8k
}
1794
1795
__isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
1796
  __isl_take isl_aff *aff2)
1797
704
{
1798
704
  return isl_aff_add(aff1, isl_aff_neg(aff2));
1799
704
}
1800
1801
/* Return the result of scaling "aff" by a factor of "f".
1802
 *
1803
 * As a special case, f * NaN = NaN.
1804
 */
1805
__isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
1806
21.2k
{
1807
21.2k
  isl_int gcd;
1808
21.2k
1809
21.2k
  if (!aff)
1810
0
    return NULL;
1811
21.2k
  if (isl_aff_is_nan(aff))
1812
0
    return aff;
1813
21.2k
1814
21.2k
  if (isl_int_is_one(f))
1815
21.2k
    
return aff11.6k
;
1816
9.58k
1817
9.58k
  aff = isl_aff_cow(aff);
1818
9.58k
  if (!aff)
1819
0
    return NULL;
1820
9.58k
  aff->v = isl_vec_cow(aff->v);
1821
9.58k
  if (!aff->v)
1822
0
    return isl_aff_free(aff);
1823
9.58k
1824
9.58k
  if (isl_int_is_pos(f) && 
isl_int_is_divisible_by8.28k
(aff->v->el[0], f)) {
1825
135
    isl_int_divexact(aff->v->el[0], aff->v->el[0], f);
1826
135
    return aff;
1827
135
  }
1828
9.45k
1829
9.45k
  isl_int_init(gcd);
1830
9.45k
  isl_int_gcd(gcd, aff->v->el[0], f);
1831
9.45k
  isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
1832
9.45k
  isl_int_divexact(gcd, f, gcd);
1833
9.45k
  isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1834
9.45k
  isl_int_clear(gcd);
1835
21.2k
1836
21.2k
  return aff;
1837
21.2k
}
1838
1839
/* Multiple "aff" by "v".
1840
 */
1841
__isl_give isl_aff *isl_aff_scale_val(__isl_take isl_aff *aff,
1842
  __isl_take isl_val *v)
1843
514
{
1844
514
  if (!aff || !v)
1845
0
    goto error;
1846
514
1847
514
  if (isl_val_is_one(v)) {
1848
63
    isl_val_free(v);
1849
63
    return aff;
1850
63
  }
1851
451
1852
451
  if (!isl_val_is_rat(v))
1853
451
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
1854
451
      "expecting rational factor", goto error);
1855
451
1856
451
  aff = isl_aff_scale(aff, v->n);
1857
451
  aff = isl_aff_scale_down(aff, v->d);
1858
451
1859
451
  isl_val_free(v);
1860
451
  return aff;
1861
0
error:
1862
0
  isl_aff_free(aff);
1863
0
  isl_val_free(v);
1864
0
  return NULL;
1865
514
}
1866
1867
/* Return the result of scaling "aff" down by a factor of "f".
1868
 *
1869
 * As a special case, NaN/f = NaN.
1870
 */
1871
__isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
1872
20.2k
{
1873
20.2k
  isl_int gcd;
1874
20.2k
1875
20.2k
  if (!aff)
1876
0
    return NULL;
1877
20.2k
  if (isl_aff_is_nan(aff))
1878
0
    return aff;
1879
20.2k
1880
20.2k
  if (isl_int_is_one(f))
1881
20.2k
    
return aff16.1k
;
1882
4.07k
1883
4.07k
  aff = isl_aff_cow(aff);
1884
4.07k
  if (!aff)
1885
0
    return NULL;
1886
4.07k
1887
4.07k
  if (isl_int_is_zero(f))
1888
4.07k
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
1889
4.07k
      "cannot scale down by zero", return isl_aff_free(aff));
1890
4.07k
1891
4.07k
  aff->v = isl_vec_cow(aff->v);
1892
4.07k
  if (!aff->v)
1893
0
    return isl_aff_free(aff);
1894
4.07k
1895
4.07k
  isl_int_init(gcd);
1896
4.07k
  isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
1897
4.07k
  isl_int_gcd(gcd, gcd, f);
1898
4.07k
  isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1899
4.07k
  isl_int_divexact(gcd, f, gcd);
1900
4.07k
  isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
1901
4.07k
  isl_int_clear(gcd);
1902
20.2k
1903
20.2k
  return aff;
1904
20.2k
}
1905
1906
/* Divide "aff" by "v".
1907
 */
1908
__isl_give isl_aff *isl_aff_scale_down_val(__isl_take isl_aff *aff,
1909
  __isl_take isl_val *v)
1910
317
{
1911
317
  if (!aff || !v)
1912
0
    goto error;
1913
317
1914
317
  if (isl_val_is_one(v)) {
1915
12
    isl_val_free(v);
1916
12
    return aff;
1917
12
  }
1918
305
1919
305
  if (!isl_val_is_rat(v))
1920
305
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
1921
305
      "expecting rational factor", goto error);
1922
305
  if (!isl_val_is_pos(v))
1923
305
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
1924
305
      "factor needs to be positive", goto error);
1925
305
1926
305
  aff = isl_aff_scale(aff, v->d);
1927
305
  aff = isl_aff_scale_down(aff, v->n);
1928
305
1929
305
  isl_val_free(v);
1930
305
  return aff;
1931
0
error:
1932
0
  isl_aff_free(aff);
1933
0
  isl_val_free(v);
1934
0
  return NULL;
1935
317
}
1936
1937
__isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
1938
3
{
1939
3
  isl_int v;
1940
3
1941
3
  if (f == 1)
1942
0
    return aff;
1943
3
1944
3
  isl_int_init(v);
1945
3
  isl_int_set_ui(v, f);
1946
3
  aff = isl_aff_scale_down(aff, v);
1947
3
  isl_int_clear(v);
1948
3
1949
3
  return aff;
1950
3
}
1951
1952
__isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
1953
  enum isl_dim_type type, unsigned pos, const char *s)
1954
0
{
1955
0
  aff = isl_aff_cow(aff);
1956
0
  if (!aff)
1957
0
    return NULL;
1958
0
  if (type == isl_dim_out)
1959
0
    isl_die(aff->v->ctx, isl_error_invalid,
1960
0
      "cannot set name of output/set dimension",
1961
0
      return isl_aff_free(aff));
1962
0
  if (type == isl_dim_in)
1963
0
    type = isl_dim_set;
1964
0
  aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
1965
0
  if (!aff->ls)
1966
0
    return isl_aff_free(aff);
1967
0
1968
0
  return aff;
1969
0
}
1970
1971
__isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
1972
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1973
0
{
1974
0
  aff = isl_aff_cow(aff);
1975
0
  if (!aff)
1976
0
    goto error;
1977
0
  if (type == isl_dim_out)
1978
0
    isl_die(aff->v->ctx, isl_error_invalid,
1979
0
      "cannot set name of output/set dimension",
1980
0
      goto error);
1981
0
  if (type == isl_dim_in)
1982
0
    type = isl_dim_set;
1983
0
  aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
1984
0
  if (!aff->ls)
1985
0
    return isl_aff_free(aff);
1986
0
1987
0
  return aff;
1988
0
error:
1989
0
  isl_id_free(id);
1990
0
  isl_aff_free(aff);
1991
0
  return NULL;
1992
0
}
1993
1994
/* Replace the identifier of the input tuple of "aff" by "id".
1995
 * type is currently required to be equal to isl_dim_in
1996
 */
1997
__isl_give isl_aff *isl_aff_set_tuple_id(__isl_take isl_aff *aff,
1998
  enum isl_dim_type type, __isl_take isl_id *id)
1999
0
{
2000
0
  aff = isl_aff_cow(aff);
2001
0
  if (!aff)
2002
0
    goto error;
2003
0
  if (type != isl_dim_out)
2004
0
    isl_die(aff->v->ctx, isl_error_invalid,
2005
0
      "cannot only set id of input tuple", goto error);
2006
0
  aff->ls = isl_local_space_set_tuple_id(aff->ls, isl_dim_set, id);
2007
0
  if (!aff->ls)
2008
0
    return isl_aff_free(aff);
2009
0
2010
0
  return aff;
2011
0
error:
2012
0
  isl_id_free(id);
2013
0
  isl_aff_free(aff);
2014
0
  return NULL;
2015
0
}
2016
2017
/* Exploit the equalities in "eq" to simplify the affine expression
2018
 * and the expressions of the integer divisions in the local space.
2019
 * The integer divisions in this local space are assumed to appear
2020
 * as regular dimensions in "eq".
2021
 */
2022
static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
2023
  __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
2024
135k
{
2025
135k
  int i, j;
2026
135k
  unsigned total;
2027
135k
  unsigned n_div;
2028
135k
2029
135k
  if (!eq)
2030
0
    goto error;
2031
135k
  if (eq->n_eq == 0) {
2032
132k
    isl_basic_set_free(eq);
2033
132k
    return aff;
2034
132k
  }
2035
3.15k
2036
3.15k
  aff = isl_aff_cow(aff);
2037
3.15k
  if (!aff)
2038
0
    goto error;
2039
3.15k
2040
3.15k
  aff->ls = isl_local_space_substitute_equalities(aff->ls,
2041
3.15k
              isl_basic_set_copy(eq));
2042
3.15k
  aff->v = isl_vec_cow(aff->v);
2043
3.15k
  if (!aff->ls || !aff->v)
2044
0
    goto error;
2045
3.15k
2046
3.15k
  total = 1 + isl_space_dim(eq->dim, isl_dim_all);
2047
3.15k
  n_div = eq->n_div;
2048
6.59k
  for (i = 0; i < eq->n_eq; 
++i3.44k
) {
2049
3.44k
    j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
2050
3.44k
    if (j < 0 || j == 0 || j >= total)
2051
499
      continue;
2052
2.94k
2053
2.94k
    isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
2054
2.94k
        &aff->v->el[0]);
2055
2.94k
  }
2056
3.15k
2057
3.15k
  isl_basic_set_free(eq);
2058
3.15k
  aff = isl_aff_normalize(aff);
2059
3.15k
  return aff;
2060
0
error:
2061
0
  isl_basic_set_free(eq);
2062
0
  isl_aff_free(aff);
2063
0
  return NULL;
2064
135k
}
2065
2066
/* Exploit the equalities in "eq" to simplify the affine expression
2067
 * and the expressions of the integer divisions in the local space.
2068
 */
2069
__isl_give isl_aff *isl_aff_substitute_equalities(__isl_take isl_aff *aff,
2070
  __isl_take isl_basic_set *eq)
2071
41.5k
{
2072
41.5k
  int n_div;
2073
41.5k
2074
41.5k
  if (!aff || !eq)
2075
0
    goto error;
2076
41.5k
  n_div = isl_local_space_dim(aff->ls, isl_dim_div);
2077
41.5k
  if (n_div > 0)
2078
6.83k
    eq = isl_basic_set_add_dims(eq, isl_dim_set, n_div);
2079
41.5k
  return isl_aff_substitute_equalities_lifted(aff, eq);
2080
0
error:
2081
0
  isl_basic_set_free(eq);
2082
0
  isl_aff_free(aff);
2083
0
  return NULL;
2084
41.5k
}
2085
2086
/* Look for equalities among the variables shared by context and aff
2087
 * and the integer divisions of aff, if any.
2088
 * The equalities are then used to eliminate coefficients and/or integer
2089
 * divisions from aff.
2090
 */
2091
__isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
2092
  __isl_take isl_set *context)
2093
94.2k
{
2094
94.2k
  isl_basic_set *hull;
2095
94.2k
  int n_div;
2096
94.2k
2097
94.2k
  if (!aff)
2098
0
    goto error;
2099
94.2k
  n_div = isl_local_space_dim(aff->ls, isl_dim_div);
2100
94.2k
  if (n_div > 0) {
2101
20.4k
    isl_basic_set *bset;
2102
20.4k
    isl_local_space *ls;
2103
20.4k
    context = isl_set_add_dims(context, isl_dim_set, n_div);
2104
20.4k
    ls = isl_aff_get_domain_local_space(aff);
2105
20.4k
    bset = isl_basic_set_from_local_space(ls);
2106
20.4k
    bset = isl_basic_set_lift(bset);
2107
20.4k
    bset = isl_basic_set_flatten(bset);
2108
20.4k
    context = isl_set_intersect(context,
2109
20.4k
              isl_set_from_basic_set(bset));
2110
20.4k
  }
2111
94.2k
2112
94.2k
  hull = isl_set_affine_hull(context);
2113
94.2k
  return isl_aff_substitute_equalities_lifted(aff, hull);
2114
0
error:
2115
0
  isl_aff_free(aff);
2116
0
  isl_set_free(context);
2117
0
  return NULL;
2118
94.2k
}
2119
2120
__isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
2121
  __isl_take isl_set *context)
2122
0
{
2123
0
  isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
2124
0
  dom_context = isl_set_intersect_params(dom_context, context);
2125
0
  return isl_aff_gist(aff, dom_context);
2126
0
}
2127
2128
/* Return a basic set containing those elements in the space
2129
 * of aff where it is positive.  "rational" should not be set.
2130
 *
2131
 * If "aff" is NaN, then it is not positive.
2132
 */
2133
static __isl_give isl_basic_set *aff_pos_basic_set(__isl_take isl_aff *aff,
2134
  int rational)
2135
144
{
2136
144
  isl_constraint *ineq;
2137
144
  isl_basic_set *bset;
2138
144
  isl_val *c;
2139
144
2140
144
  if (!aff)
2141
0
    return NULL;
2142
144
  if (isl_aff_is_nan(aff)) {
2143
0
    isl_space *space = isl_aff_get_domain_space(aff);
2144
0
    isl_aff_free(aff);
2145
0
    return isl_basic_set_empty(space);
2146
0
  }
2147
144
  if (rational)
2148
144
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_unsupported,
2149
144
      "rational sets not supported", goto error);
2150
144
2151
144
  ineq = isl_inequality_from_aff(aff);
2152
144
  c = isl_constraint_get_constant_val(ineq);
2153
144
  c = isl_val_sub_ui(c, 1);
2154
144
  ineq = isl_constraint_set_constant_val(ineq, c);
2155
144
2156
144
  bset = isl_basic_set_from_constraint(ineq);
2157
144
  bset = isl_basic_set_simplify(bset);
2158
144
  return bset;
2159
0
error:
2160
0
  isl_aff_free(aff);
2161
0
  return NULL;
2162
144
}
2163
2164
/* Return a basic set containing those elements in the space
2165
 * of aff where it is non-negative.
2166
 * If "rational" is set, then return a rational basic set.
2167
 *
2168
 * If "aff" is NaN, then it is not non-negative (it's not negative either).
2169
 */
2170
static __isl_give isl_basic_set *aff_nonneg_basic_set(
2171
  __isl_take isl_aff *aff, int rational)
2172
16.1k
{
2173
16.1k
  isl_constraint *ineq;
2174
16.1k
  isl_basic_set *bset;
2175
16.1k
2176
16.1k
  if (!aff)
2177
0
    return NULL;
2178
16.1k
  if (isl_aff_is_nan(aff)) {
2179
0
    isl_space *space = isl_aff_get_domain_space(aff);
2180
0
    isl_aff_free(aff);
2181
0
    return isl_basic_set_empty(space);
2182
0
  }
2183
16.1k
2184
16.1k
  ineq = isl_inequality_from_aff(aff);
2185
16.1k
2186
16.1k
  bset = isl_basic_set_from_constraint(ineq);
2187
16.1k
  if (rational)
2188
24
    bset = isl_basic_set_set_rational(bset);
2189
16.1k
  bset = isl_basic_set_simplify(bset);
2190
16.1k
  return bset;
2191
16.1k
}
2192
2193
/* Return a basic set containing those elements in the space
2194
 * of aff where it is non-negative.
2195
 */
2196
__isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
2197
564
{
2198
564
  return aff_nonneg_basic_set(aff, 0);
2199
564
}
2200
2201
/* Return a basic set containing those elements in the domain space
2202
 * of "aff" where it is positive.
2203
 */
2204
__isl_give isl_basic_set *isl_aff_pos_basic_set(__isl_take isl_aff *aff)
2205
114
{
2206
114
  aff = isl_aff_add_constant_num_si(aff, -1);
2207
114
  return isl_aff_nonneg_basic_set(aff);
2208
114
}
2209
2210
/* Return a basic set containing those elements in the domain space
2211
 * of aff where it is negative.
2212
 */
2213
__isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff)
2214
114
{
2215
114
  aff = isl_aff_neg(aff);
2216
114
  return isl_aff_pos_basic_set(aff);
2217
114
}
2218
2219
/* Return a basic set containing those elements in the space
2220
 * of aff where it is zero.
2221
 * If "rational" is set, then return a rational basic set.
2222
 *
2223
 * If "aff" is NaN, then it is not zero.
2224
 */
2225
static __isl_give isl_basic_set *aff_zero_basic_set(__isl_take isl_aff *aff,
2226
  int rational)
2227
8.59k
{
2228
8.59k
  isl_constraint *ineq;
2229
8.59k
  isl_basic_set *bset;
2230
8.59k
2231
8.59k
  if (!aff)
2232
0
    return NULL;
2233
8.59k
  if (isl_aff_is_nan(aff)) {
2234
0
    isl_space *space = isl_aff_get_domain_space(aff);
2235
0
    isl_aff_free(aff);
2236
0
    return isl_basic_set_empty(space);
2237
0
  }
2238
8.59k
2239
8.59k
  ineq = isl_equality_from_aff(aff);
2240
8.59k
2241
8.59k
  bset = isl_basic_set_from_constraint(ineq);
2242
8.59k
  if (rational)
2243
173
    bset = isl_basic_set_set_rational(bset);
2244
8.59k
  bset = isl_basic_set_simplify(bset);
2245
8.59k
  return bset;
2246
8.59k
}
2247
2248
/* Return a basic set containing those elements in the space
2249
 * of aff where it is zero.
2250
 */
2251
__isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
2252
70
{
2253
70
  return aff_zero_basic_set(aff, 0);
2254
70
}
2255
2256
/* Return a basic set containing those elements in the shared space
2257
 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
2258
 */
2259
__isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
2260
  __isl_take isl_aff *aff2)
2261
450
{
2262
450
  aff1 = isl_aff_sub(aff1, aff2);
2263
450
2264
450
  return isl_aff_nonneg_basic_set(aff1);
2265
450
}
2266
2267
/* Return a basic set containing those elements in the shared domain space
2268
 * of "aff1" and "aff2" where "aff1" is greater than "aff2".
2269
 */
2270
__isl_give isl_basic_set *isl_aff_gt_basic_set(__isl_take isl_aff *aff1,
2271
  __isl_take isl_aff *aff2)
2272
0
{
2273
0
  aff1 = isl_aff_sub(aff1, aff2);
2274
0
2275
0
  return isl_aff_pos_basic_set(aff1);
2276
0
}
2277
2278
/* Return a set containing those elements in the shared space
2279
 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
2280
 */
2281
__isl_give isl_set *isl_aff_ge_set(__isl_take isl_aff *aff1,
2282
  __isl_take isl_aff *aff2)
2283
368
{
2284
368
  return isl_set_from_basic_set(isl_aff_ge_basic_set(aff1, aff2));
2285
368
}
2286
2287
/* Return a set containing those elements in the shared domain space
2288
 * of aff1 and aff2 where aff1 is greater than aff2.
2289
 *
2290
 * If either of the two inputs is NaN, then the result is empty,
2291
 * as comparisons with NaN always return false.
2292
 */
2293
__isl_give isl_set *isl_aff_gt_set(__isl_take isl_aff *aff1,
2294
  __isl_take isl_aff *aff2)
2295
0
{
2296
0
  return isl_set_from_basic_set(isl_aff_gt_basic_set(aff1, aff2));
2297
0
}
2298
2299
/* Return a basic set containing those elements in the shared space
2300
 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
2301
 */
2302
__isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
2303
  __isl_take isl_aff *aff2)
2304
36
{
2305
36
  return isl_aff_ge_basic_set(aff2, aff1);
2306
36
}
2307
2308
/* Return a basic set containing those elements in the shared domain space
2309
 * of "aff1" and "aff2" where "aff1" is smaller than "aff2".
2310
 */
2311
__isl_give isl_basic_set *isl_aff_lt_basic_set(__isl_take isl_aff *aff1,
2312
  __isl_take isl_aff *aff2)
2313
0
{
2314
0
  return isl_aff_gt_basic_set(aff2, aff1);
2315
0
}
2316
2317
/* Return a set containing those elements in the shared space
2318
 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
2319
 */
2320
__isl_give isl_set *isl_aff_le_set(__isl_take isl_aff *aff1,
2321
  __isl_take isl_aff *aff2)
2322
190
{
2323
190
  return isl_aff_ge_set(aff2, aff1);
2324
190
}
2325
2326
/* Return a set containing those elements in the shared domain space
2327
 * of "aff1" and "aff2" where "aff1" is smaller than "aff2".
2328
 */
2329
__isl_give isl_set *isl_aff_lt_set(__isl_take isl_aff *aff1,
2330
  __isl_take isl_aff *aff2)
2331
0
{
2332
0
  return isl_set_from_basic_set(isl_aff_lt_basic_set(aff1, aff2));
2333
0
}
2334
2335
/* Return a basic set containing those elements in the shared space
2336
 * of aff1 and aff2 where aff1 and aff2 are equal.
2337
 */
2338
__isl_give isl_basic_set *isl_aff_eq_basic_set(__isl_take isl_aff *aff1,
2339
  __isl_take isl_aff *aff2)
2340
34
{
2341
34
  aff1 = isl_aff_sub(aff1, aff2);
2342
34
2343
34
  return isl_aff_zero_basic_set(aff1);
2344
34
}
2345
2346
/* Return a set containing those elements in the shared space
2347
 * of aff1 and aff2 where aff1 and aff2 are equal.
2348
 */
2349
__isl_give isl_set *isl_aff_eq_set(__isl_take isl_aff *aff1,
2350
  __isl_take isl_aff *aff2)
2351
34
{
2352
34
  return isl_set_from_basic_set(isl_aff_eq_basic_set(aff1, aff2));
2353
34
}
2354
2355
/* Return a set containing those elements in the shared domain space
2356
 * of aff1 and aff2 where aff1 and aff2 are not equal.
2357
 *
2358
 * If either of the two inputs is NaN, then the result is empty,
2359
 * as comparisons with NaN always return false.
2360
 */
2361
__isl_give isl_set *isl_aff_ne_set(__isl_take isl_aff *aff1,
2362
  __isl_take isl_aff *aff2)
2363
0
{
2364
0
  isl_set *set_lt, *set_gt;
2365
0
2366
0
  set_lt = isl_aff_lt_set(isl_aff_copy(aff1),
2367
0
        isl_aff_copy(aff2));
2368
0
  set_gt = isl_aff_gt_set(aff1, aff2);
2369
0
  return isl_set_union_disjoint(set_lt, set_gt);
2370
0
}
2371
2372
__isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
2373
  __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
2374
0
{
2375
0
  aff1 = isl_aff_add(aff1, aff2);
2376
0
  aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
2377
0
  return aff1;
2378
0
}
2379
2380
int isl_aff_is_empty(__isl_keep isl_aff *aff)
2381
219k
{
2382
219k
  if (!aff)
2383
0
    return -1;
2384
219k
2385
219k
  return 0;
2386
219k
}
2387
2388
/* Check whether the given affine expression has non-zero coefficient
2389
 * for any dimension in the given range or if any of these dimensions
2390
 * appear with non-zero coefficients in any of the integer divisions
2391
 * involved in the affine expression.
2392
 */
2393
isl_bool isl_aff_involves_dims(__isl_keep isl_aff *aff,
2394
  enum isl_dim_type type, unsigned first, unsigned n)
2395
26.7k
{
2396
26.7k
  int i;
2397
26.7k
  isl_ctx *ctx;
2398
26.7k
  int *active = NULL;
2399
26.7k
  isl_bool involves = isl_bool_false;
2400
26.7k
2401
26.7k
  if (!aff)
2402
0
    return isl_bool_error;
2403
26.7k
  if (n == 0)
2404
0
    return isl_bool_false;
2405
26.7k
2406
26.7k
  ctx = isl_aff_get_ctx(aff);
2407
26.7k
  if (first + n > isl_aff_dim(aff, type))
2408
26.7k
    
isl_die0
(ctx, isl_error_invalid,
2409
26.7k
      "range out of bounds", return isl_bool_error);
2410
26.7k
2411
26.7k
  active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
2412
26.7k
  if (!active)
2413
0
    goto error;
2414
26.7k
2415
26.7k
  first += isl_local_space_offset(aff->ls, type) - 1;
2416
48.6k
  for (i = 0; i < n; 
++i21.8k
)
2417
26.8k
    if (active[first + i]) {
2418
5.05k
      involves = isl_bool_true;
2419
5.05k
      break;
2420
5.05k
    }
2421
26.7k
2422
26.7k
  free(active);
2423
26.7k
2424
26.7k
  return involves;
2425
0
error:
2426
0
  free(active);
2427
0
  return isl_bool_error;
2428
26.7k
}
2429
2430
__isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
2431
  enum isl_dim_type type, unsigned first, unsigned n)
2432
1.37k
{
2433
1.37k
  isl_ctx *ctx;
2434
1.37k
2435
1.37k
  if (!aff)
2436
0
    return NULL;
2437
1.37k
  if (type == isl_dim_out)
2438
1.37k
    
isl_die0
(aff->v->ctx, isl_error_invalid,
2439
1.37k
      "cannot drop output/set dimension",
2440
1.37k
      return isl_aff_free(aff));
2441
1.37k
  if (type == isl_dim_in)
2442
1.37k
    type = isl_dim_set;
2443
1.37k
  if (n == 0 && 
!isl_local_space_is_named_or_nested(aff->ls, type)0
)
2444
0
    return aff;
2445
1.37k
2446
1.37k
  ctx = isl_aff_get_ctx(aff);
2447
1.37k
  if (first + n > isl_local_space_dim(aff->ls, type))
2448
1.37k
    
isl_die0
(ctx, isl_error_invalid, "range out of bounds",
2449
1.37k
      return isl_aff_free(aff));
2450
1.37k
2451
1.37k
  aff = isl_aff_cow(aff);
2452
1.37k
  if (!aff)
2453
0
    return NULL;
2454
1.37k
2455
1.37k
  aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
2456
1.37k
  if (!aff->ls)
2457
0
    return isl_aff_free(aff);
2458
1.37k
2459
1.37k
  first += 1 + isl_local_space_offset(aff->ls, type);
2460
1.37k
  aff->v = isl_vec_drop_els(aff->v, first, n);
2461
1.37k
  if (!aff->v)
2462
0
    return isl_aff_free(aff);
2463
1.37k
2464
1.37k
  return aff;
2465
1.37k
}
2466
2467
/* Project the domain of the affine expression onto its parameter space.
2468
 * The affine expression may not involve any of the domain dimensions.
2469
 */
2470
__isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
2471
0
{
2472
0
  isl_space *space;
2473
0
  unsigned n;
2474
0
  int involves;
2475
0
2476
0
  n = isl_aff_dim(aff, isl_dim_in);
2477
0
  involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
2478
0
  if (involves < 0)
2479
0
    return isl_aff_free(aff);
2480
0
  if (involves)
2481
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2482
0
        "affine expression involves some of the domain dimensions",
2483
0
        return isl_aff_free(aff));
2484
0
  aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
2485
0
  space = isl_aff_get_domain_space(aff);
2486
0
  space = isl_space_params(space);
2487
0
  aff = isl_aff_reset_domain_space(aff, space);
2488
0
  return aff;
2489
0
}
2490
2491
__isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
2492
  enum isl_dim_type type, unsigned first, unsigned n)
2493
7.50k
{
2494
7.50k
  isl_ctx *ctx;
2495
7.50k
2496
7.50k
  if (!aff)
2497
0
    return NULL;
2498
7.50k
  if (type == isl_dim_out)
2499
7.50k
    
isl_die0
(aff->v->ctx, isl_error_invalid,
2500
7.50k
      "cannot insert output/set dimensions",
2501
7.50k
      return isl_aff_free(aff));
2502
7.50k
  if (type == isl_dim_in)
2503
7.50k
    type = isl_dim_set;
2504
7.50k
  if (n == 0 && 
!isl_local_space_is_named_or_nested(aff->ls, type)1.65k
)
2505
1.65k
    return aff;
2506
5.85k
2507
5.85k
  ctx = isl_aff_get_ctx(aff);
2508
5.85k
  if (first > isl_local_space_dim(aff->ls, type))
2509
5.85k
    
isl_die0
(ctx, isl_error_invalid, "position out of bounds",
2510
5.85k
      return isl_aff_free(aff));
2511
5.85k
2512
5.85k
  aff = isl_aff_cow(aff);
2513
5.85k
  if (!aff)
2514
0
    return NULL;
2515
5.85k
2516
5.85k
  aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
2517
5.85k
  if (!aff->ls)
2518
0
    return isl_aff_free(aff);
2519
5.85k
2520
5.85k
  first += 1 + isl_local_space_offset(aff->ls, type);
2521
5.85k
  aff->v = isl_vec_insert_zero_els(aff->v, first, n);
2522
5.85k
  if (!aff->v)
2523
0
    return isl_aff_free(aff);
2524
5.85k
2525
5.85k
  return aff;
2526
5.85k
}
2527
2528
__isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
2529
  enum isl_dim_type type, unsigned n)
2530
0
{
2531
0
  unsigned pos;
2532
0
2533
0
  pos = isl_aff_dim(aff, type);
2534
0
2535
0
  return isl_aff_insert_dims(aff, type, pos, n);
2536
0
}
2537
2538
__isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
2539
  enum isl_dim_type type, unsigned n)
2540
3.35k
{
2541
3.35k
  unsigned pos;
2542
3.35k
2543
3.35k
  pos = isl_pw_aff_dim(pwaff, type);
2544
3.35k
2545
3.35k
  return isl_pw_aff_insert_dims(pwaff, type, pos, n);
2546
3.35k
}
2547
2548
/* Move the "n" dimensions of "src_type" starting at "src_pos" of "aff"
2549
 * to dimensions of "dst_type" at "dst_pos".
2550
 *
2551
 * We only support moving input dimensions to parameters and vice versa.
2552
 */
2553
__isl_give isl_aff *isl_aff_move_dims(__isl_take isl_aff *aff,
2554
  enum isl_dim_type dst_type, unsigned dst_pos,
2555
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2556
0
{
2557
0
  unsigned g_dst_pos;
2558
0
  unsigned g_src_pos;
2559
0
2560
0
  if (!aff)
2561
0
    return NULL;
2562
0
  if (n == 0 &&
2563
0
      !isl_local_space_is_named_or_nested(aff->ls, src_type) &&
2564
0
      !isl_local_space_is_named_or_nested(aff->ls, dst_type))
2565
0
    return aff;
2566
0
2567
0
  if (dst_type == isl_dim_out || src_type == isl_dim_out)
2568
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2569
0
      "cannot move output/set dimension",
2570
0
      return isl_aff_free(aff));
2571
0
  if (dst_type == isl_dim_div || src_type == isl_dim_div)
2572
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2573
0
      "cannot move divs", return isl_aff_free(aff));
2574
0
  if (dst_type == isl_dim_in)
2575
0
    dst_type = isl_dim_set;
2576
0
  if (src_type == isl_dim_in)
2577
0
    src_type = isl_dim_set;
2578
0
2579
0
  if (src_pos + n > isl_local_space_dim(aff->ls, src_type))
2580
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2581
0
      "range out of bounds", return isl_aff_free(aff));
2582
0
  if (dst_type == src_type)
2583
0
    isl_die(isl_aff_get_ctx(aff), isl_error_unsupported,
2584
0
      "moving dims within the same type not supported",
2585
0
      return isl_aff_free(aff));
2586
0
2587
0
  aff = isl_aff_cow(aff);
2588
0
  if (!aff)
2589
0
    return NULL;
2590
0
2591
0
  g_src_pos = 1 + isl_local_space_offset(aff->ls, src_type) + src_pos;
2592
0
  g_dst_pos = 1 + isl_local_space_offset(aff->ls, dst_type) + dst_pos;
2593
0
  if (dst_type > src_type)
2594
0
    g_dst_pos -= n;
2595
0
2596
0
  aff->v = isl_vec_move_els(aff->v, g_dst_pos, g_src_pos, n);
2597
0
  aff->ls = isl_local_space_move_dims(aff->ls, dst_type, dst_pos,
2598
0
            src_type, src_pos, n);
2599
0
  if (!aff->v || !aff->ls)
2600
0
    return isl_aff_free(aff);
2601
0
2602
0
  aff = sort_divs(aff);
2603
0
2604
0
  return aff;
2605
0
}
2606
2607
__isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
2608
60.5k
{
2609
60.5k
  isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
2610
60.5k
  return isl_pw_aff_alloc(dom, aff);
2611
60.5k
}
2612
2613
2.55k
#define isl_aff_involves_nan isl_aff_is_nan
2614
2615
#undef PW
2616
203k
#define PW isl_pw_aff
2617
#undef EL
2618
80.5k
#define EL isl_aff
2619
#undef EL_IS_ZERO
2620
#define EL_IS_ZERO is_empty
2621
#undef ZERO
2622
#define ZERO empty
2623
#undef IS_ZERO
2624
#define IS_ZERO is_empty
2625
#undef FIELD
2626
1.18M
#define FIELD aff
2627
#undef DEFAULT_IS_ZERO
2628
9.28k
#define DEFAULT_IS_ZERO 0
2629
2630
#define NO_EVAL
2631
#define NO_OPT
2632
#define NO_LIFT
2633
#define NO_MORPH
2634
2635
#include <isl_pw_templ.c>
2636
#include <isl_pw_hash.c>
2637
#include <isl_pw_union_opt.c>
2638
2639
#undef UNION
2640
7.47k
#define UNION isl_union_pw_aff
2641
#undef PART
2642
54.3k
#define PART isl_pw_aff
2643
#undef PARTS
2644
#define PARTS pw_aff
2645
2646
#include <isl_union_single.c>
2647
#include <isl_union_neg.c>
2648
2649
static __isl_give isl_set *align_params_pw_pw_set_and(
2650
  __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
2651
  __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
2652
            __isl_take isl_pw_aff *pwaff2))
2653
20.0k
{
2654
20.0k
  isl_bool equal_params;
2655
20.0k
2656
20.0k
  if (!pwaff1 || !pwaff2)
2657
0
    goto error;
2658
20.0k
  equal_params = isl_space_has_equal_params(pwaff1->dim, pwaff2->dim);
2659
20.0k
  if (equal_params < 0)
2660
0
    goto error;
2661
20.0k
  if (equal_params)
2662
18.4k
    return fn(pwaff1, pwaff2);
2663
1.54k
  if (!isl_space_has_named_params(pwaff1->dim) ||
2664
1.54k
      !isl_space_has_named_params(pwaff2->dim))
2665
1.54k
    
isl_die0
(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
2666
1.54k
      "unaligned unnamed parameters", goto error);
2667
1.54k
  pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
2668
1.54k
  pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
2669
1.54k
  return fn(pwaff1, pwaff2);
2670
0
error:
2671
0
  isl_pw_aff_free(pwaff1);
2672
0
  isl_pw_aff_free(pwaff2);
2673
0
  return NULL;
2674
20.0k
}
2675
2676
/* Align the parameters of the to isl_pw_aff arguments and
2677
 * then apply a function "fn" on them that returns an isl_map.
2678
 */
2679
static __isl_give isl_map *align_params_pw_pw_map_and(
2680
  __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2,
2681
  __isl_give isl_map *(*fn)(__isl_take isl_pw_aff *pa1,
2682
            __isl_take isl_pw_aff *pa2))
2683
2
{
2684
2
  isl_bool equal_params;
2685
2
2686
2
  if (!pa1 || !pa2)
2687
0
    goto error;
2688
2
  equal_params = isl_space_has_equal_params(pa1->dim, pa2->dim);
2689
2
  if (equal_params < 0)
2690
0
    goto error;
2691
2
  if (equal_params)
2692
2
    return fn(pa1, pa2);
2693
0
  if (!isl_space_has_named_params(pa1->dim) ||
2694
0
      !isl_space_has_named_params(pa2->dim))
2695
0
    isl_die(isl_pw_aff_get_ctx(pa1), isl_error_invalid,
2696
0
      "unaligned unnamed parameters", goto error);
2697
0
  pa1 = isl_pw_aff_align_params(pa1, isl_pw_aff_get_space(pa2));
2698
0
  pa2 = isl_pw_aff_align_params(pa2, isl_pw_aff_get_space(pa1));
2699
0
  return fn(pa1, pa2);
2700
0
error:
2701
0
  isl_pw_aff_free(pa1);
2702
0
  isl_pw_aff_free(pa2);
2703
0
  return NULL;
2704
2
}
2705
2706
/* Compute a piecewise quasi-affine expression with a domain that
2707
 * is the union of those of pwaff1 and pwaff2 and such that on each
2708
 * cell, the quasi-affine expression is the maximum of those of pwaff1
2709
 * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
2710
 * cell, then the associated expression is the defined one.
2711
 */
2712
static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
2713
  __isl_take isl_pw_aff *pwaff2)
2714
175
{
2715
175
  return isl_pw_aff_union_opt_cmp(pwaff1, pwaff2, &isl_aff_ge_set);
2716
175
}
2717
2718
__isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
2719
  __isl_take isl_pw_aff *pwaff2)
2720
175
{
2721
175
  return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
2722
175
              &pw_aff_union_max);
2723
175
}
2724
2725
/* Compute a piecewise quasi-affine expression with a domain that
2726
 * is the union of those of pwaff1 and pwaff2 and such that on each
2727
 * cell, the quasi-affine expression is the minimum of those of pwaff1
2728
 * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
2729
 * cell, then the associated expression is the defined one.
2730
 */
2731
static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
2732
  __isl_take isl_pw_aff *pwaff2)
2733
184
{
2734
184
  return isl_pw_aff_union_opt_cmp(pwaff1, pwaff2, &isl_aff_le_set);
2735
184
}
2736
2737
__isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
2738
  __isl_take isl_pw_aff *pwaff2)
2739
184
{
2740
184
  return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
2741
184
              &pw_aff_union_min);
2742
184
}
2743
2744
__isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
2745
  __isl_take isl_pw_aff *pwaff2, int max)
2746
359
{
2747
359
  if (max)
2748
175
    return isl_pw_aff_union_max(pwaff1, pwaff2);
2749
184
  else
2750
184
    return isl_pw_aff_union_min(pwaff1, pwaff2);
2751
359
}
2752
2753
/* Construct a map with as domain the domain of pwaff and
2754
 * one-dimensional range corresponding to the affine expressions.
2755
 */
2756
static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2757
21.5k
{
2758
21.5k
  int i;
2759
21.5k
  isl_space *dim;
2760
21.5k
  isl_map *map;
2761
21.5k
2762
21.5k
  if (!pwaff)
2763
0
    return NULL;
2764
21.5k
2765
21.5k
  dim = isl_pw_aff_get_space(pwaff);
2766
21.5k
  map = isl_map_empty(dim);
2767
21.5k
2768
43.2k
  for (i = 0; i < pwaff->n; 
++i21.7k
) {
2769
21.7k
    isl_basic_map *bmap;
2770
21.7k
    isl_map *map_i;
2771
21.7k
2772
21.7k
    bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
2773
21.7k
    map_i = isl_map_from_basic_map(bmap);
2774
21.7k
    map_i = isl_map_intersect_domain(map_i,
2775
21.7k
            isl_set_copy(pwaff->p[i].set));
2776
21.7k
    map = isl_map_union_disjoint(map, map_i);
2777
21.7k
  }
2778
21.5k
2779
21.5k
  isl_pw_aff_free(pwaff);
2780
21.5k
2781
21.5k
  return map;
2782
21.5k
}
2783
2784
/* Construct a map with as domain the domain of pwaff and
2785
 * one-dimensional range corresponding to the affine expressions.
2786
 */
2787
__isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2788
21.5k
{
2789
21.5k
  if (!pwaff)
2790
0
    return NULL;
2791
21.5k
  if (isl_space_is_set(pwaff->dim))
2792
21.5k
    
isl_die0
(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
2793
21.5k
      "space of input is not a map", goto error);
2794
21.5k
  return map_from_pw_aff(pwaff);
2795
0
error:
2796
0
  isl_pw_aff_free(pwaff);
2797
0
  return NULL;
2798
21.5k
}
2799
2800
/* Construct a one-dimensional set with as parameter domain
2801
 * the domain of pwaff and the single set dimension
2802
 * corresponding to the affine expressions.
2803
 */
2804
__isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2805
7
{
2806
7
  if (!pwaff)
2807
0
    return NULL;
2808
7
  if (!isl_space_is_set(pwaff->dim))
2809
7
    
isl_die0
(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
2810
7
      "space of input is not a set", goto error);
2811
7
  return map_from_pw_aff(pwaff);
2812
0
error:
2813
0
  isl_pw_aff_free(pwaff);
2814
0
  return NULL;
2815
7
}
2816
2817
/* Return a set containing those elements in the domain
2818
 * of "pwaff" where it satisfies "fn" (if complement is 0) or
2819
 * does not satisfy "fn" (if complement is 1).
2820
 *
2821
 * The pieces with a NaN never belong to the result since
2822
 * NaN does not satisfy any property.
2823
 */
2824
static __isl_give isl_set *pw_aff_locus(__isl_take isl_pw_aff *pwaff,
2825
  __isl_give isl_basic_set *(*fn)(__isl_take isl_aff *aff, int rational),
2826
  int complement)
2827
23.4k
{
2828
23.4k
  int i;
2829
23.4k
  isl_set *set;
2830
23.4k
2831
23.4k
  if (!pwaff)
2832
0
    return NULL;
2833
23.4k
2834
23.4k
  set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
2835
23.4k
2836
47.6k
  for (i = 0; i < pwaff->n; 
++i24.2k
) {
2837
24.2k
    isl_basic_set *bset;
2838
24.2k
    isl_set *set_i, *locus;
2839
24.2k
    isl_bool rational;
2840
24.2k
2841
24.2k
    if (isl_aff_is_nan(pwaff->p[i].aff))
2842
0
      continue;
2843
24.2k
2844
24.2k
    rational = isl_set_has_rational(pwaff->p[i].set);
2845
24.2k
    bset = fn(isl_aff_copy(pwaff->p[i].aff), rational);
2846
24.2k
    locus = isl_set_from_basic_set(bset);
2847
24.2k
    set_i = isl_set_copy(pwaff->p[i].set);
2848
24.2k
    if (complement)
2849
124
      set_i = isl_set_subtract(set_i, locus);
2850
24.1k
    else
2851
24.1k
      set_i = isl_set_intersect(set_i, locus);
2852
24.2k
    set = isl_set_union_disjoint(set, set_i);
2853
24.2k
  }
2854
23.4k
2855
23.4k
  isl_pw_aff_free(pwaff);
2856
23.4k
2857
23.4k
  return set;
2858
23.4k
}
2859
2860
/* Return a set containing those elements in the domain
2861
 * of "pa" where it is positive.
2862
 */
2863
__isl_give isl_set *isl_pw_aff_pos_set(__isl_take isl_pw_aff *pa)
2864
136
{
2865
136
  return pw_aff_locus(pa, &aff_pos_basic_set, 0);
2866
136
}
2867
2868
/* Return a set containing those elements in the domain
2869
 * of pwaff where it is non-negative.
2870
 */
2871
__isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
2872
14.9k
{
2873
14.9k
  return pw_aff_locus(pwaff, &aff_nonneg_basic_set, 0);
2874
14.9k
}
2875
2876
/* Return a set containing those elements in the domain
2877
 * of pwaff where it is zero.
2878
 */
2879
__isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
2880
8.23k
{
2881
8.23k
  return pw_aff_locus(pwaff, &aff_zero_basic_set, 0);
2882
8.23k
}
2883
2884
/* Return a set containing those elements in the domain
2885
 * of pwaff where it is not zero.
2886
 */
2887
__isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
2888
70
{
2889
70
  return pw_aff_locus(pwaff, &aff_zero_basic_set, 1);
2890
70
}
2891
2892
/* Return a set containing those elements in the shared domain
2893
 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2894
 *
2895
 * We compute the difference on the shared domain and then construct
2896
 * the set of values where this difference is non-negative.
2897
 * If strict is set, we first subtract 1 from the difference.
2898
 * If equal is set, we only return the elements where pwaff1 and pwaff2
2899
 * are equal.
2900
 */
2901
static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
2902
  __isl_take isl_pw_aff *pwaff2, int strict, int equal)
2903
16.0k
{
2904
16.0k
  isl_set *set1, *set2;
2905
16.0k
2906
16.0k
  set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
2907
16.0k
  set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
2908
16.0k
  set1 = isl_set_intersect(set1, set2);
2909
16.0k
  pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
2910
16.0k
  pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
2911
16.0k
  pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
2912
16.0k
2913
16.0k
  if (strict) {
2914
9.80k
    isl_space *dim = isl_set_get_space(set1);
2915
9.80k
    isl_aff *aff;
2916
9.80k
    aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2917
9.80k
    aff = isl_aff_add_constant_si(aff, -1);
2918
9.80k
    pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
2919
9.80k
  } else
2920
6.27k
    isl_set_free(set1);
2921
16.0k
2922
16.0k
  if (equal)
2923
1.21k
    return isl_pw_aff_zero_set(pwaff1);
2924
14.8k
  return isl_pw_aff_nonneg_set(pwaff1);
2925
14.8k
}
2926
2927
/* Return a set containing those elements in the shared domain
2928
 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2929
 */
2930
static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
2931
  __isl_take isl_pw_aff *pwaff2)
2932
1.21k
{
2933
1.21k
  return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
2934
1.21k
}
2935
2936
__isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
2937
  __isl_take isl_pw_aff *pwaff2)
2938
1.21k
{
2939
1.21k
  return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
2940
1.21k
}
2941
2942
/* Return a set containing those elements in the shared domain
2943
 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2944
 */
2945
static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
2946
  __isl_take isl_pw_aff *pwaff2)
2947
5.05k
{
2948
5.05k
  return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
2949
5.05k
}
2950
2951
__isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
2952
  __isl_take isl_pw_aff *pwaff2)
2953
5.05k
{
2954
5.05k
  return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
2955
5.05k
}
2956
2957
/* Return a set containing those elements in the shared domain
2958
 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2959
 */
2960
static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
2961
  __isl_take isl_pw_aff *pwaff2)
2962
9.80k
{
2963
9.80k
  return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
2964
9.80k
}
2965
2966
__isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
2967
  __isl_take isl_pw_aff *pwaff2)
2968
9.80k
{
2969
9.80k
  return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
2970
9.80k
}
2971
2972
__isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
2973
  __isl_take isl_pw_aff *pwaff2)
2974
3.83k
{
2975
3.83k
  return isl_pw_aff_ge_set(pwaff2, pwaff1);
2976
3.83k
}
2977
2978
__isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
2979
  __isl_take isl_pw_aff *pwaff2)
2980
5.66k
{
2981
5.66k
  return isl_pw_aff_gt_set(pwaff2, pwaff1);
2982
5.66k
}
2983
2984
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
2985
 * where the function values are ordered in the same way as "order",
2986
 * which returns a set in the shared domain of its two arguments.
2987
 * The parameters of "pa1" and "pa2" are assumed to have been aligned.
2988
 *
2989
 * Let "pa1" and "pa2" be defined on domains A and B respectively.
2990
 * We first pull back the two functions such that they are defined on
2991
 * the domain [A -> B].  Then we apply "order", resulting in a set
2992
 * in the space [A -> B].  Finally, we unwrap this set to obtain
2993
 * a map in the space A -> B.
2994
 */
2995
static __isl_give isl_map *isl_pw_aff_order_map_aligned(
2996
  __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2,
2997
  __isl_give isl_set *(*order)(__isl_take isl_pw_aff *pa1,
2998
    __isl_take isl_pw_aff *pa2))
2999
2
{
3000
2
  isl_space *space1, *space2;
3001
2
  isl_multi_aff *ma;
3002
2
  isl_set *set;
3003
2
3004
2
  space1 = isl_space_domain(isl_pw_aff_get_space(pa1));
3005
2
  space2 = isl_space_domain(isl_pw_aff_get_space(pa2));
3006
2
  space1 = isl_space_map_from_domain_and_range(space1, space2);
3007
2
  ma = isl_multi_aff_domain_map(isl_space_copy(space1));
3008
2
  pa1 = isl_pw_aff_pullback_multi_aff(pa1, ma);
3009
2
  ma = isl_multi_aff_range_map(space1);
3010
2
  pa2 = isl_pw_aff_pullback_multi_aff(pa2, ma);
3011
2
  set = order(pa1, pa2);
3012
2
3013
2
  return isl_set_unwrap(set);
3014
2
}
3015
3016
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3017
 * where the function values are equal.
3018
 * The parameters of "pa1" and "pa2" are assumed to have been aligned.
3019
 */
3020
static __isl_give isl_map *isl_pw_aff_eq_map_aligned(__isl_take isl_pw_aff *pa1,
3021
  __isl_take isl_pw_aff *pa2)
3022
2
{
3023
2
  return isl_pw_aff_order_map_aligned(pa1, pa2, &isl_pw_aff_eq_set);
3024
2
}
3025
3026
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3027
 * where the function values are equal.
3028
 */
3029
__isl_give isl_map *isl_pw_aff_eq_map(__isl_take isl_pw_aff *pa1,
3030
  __isl_take isl_pw_aff *pa2)
3031
2
{
3032
2
  return align_params_pw_pw_map_and(pa1, pa2, &isl_pw_aff_eq_map_aligned);
3033
2
}
3034
3035
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3036
 * where the function value of "pa1" is less than the function value of "pa2".
3037
 * The parameters of "pa1" and "pa2" are assumed to have been aligned.
3038
 */
3039
static __isl_give isl_map *isl_pw_aff_lt_map_aligned(__isl_take isl_pw_aff *pa1,
3040
  __isl_take isl_pw_aff *pa2)
3041
0
{
3042
0
  return isl_pw_aff_order_map_aligned(pa1, pa2, &isl_pw_aff_lt_set);
3043
0
}
3044
3045
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3046
 * where the function value of "pa1" is less than the function value of "pa2".
3047
 */
3048
__isl_give isl_map *isl_pw_aff_lt_map(__isl_take isl_pw_aff *pa1,
3049
  __isl_take isl_pw_aff *pa2)
3050
0
{
3051
0
  return align_params_pw_pw_map_and(pa1, pa2, &isl_pw_aff_lt_map_aligned);
3052
0
}
3053
3054
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3055
 * where the function value of "pa1" is greater than the function value
3056
 * of "pa2".
3057
 * The parameters of "pa1" and "pa2" are assumed to have been aligned.
3058
 */
3059
static __isl_give isl_map *isl_pw_aff_gt_map_aligned(__isl_take isl_pw_aff *pa1,
3060
  __isl_take isl_pw_aff *pa2)
3061
0
{
3062
0
  return isl_pw_aff_order_map_aligned(pa1, pa2, &isl_pw_aff_gt_set);
3063
0
}
3064
3065
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3066
 * where the function value of "pa1" is greater than the function value
3067
 * of "pa2".
3068
 */
3069
__isl_give isl_map *isl_pw_aff_gt_map(__isl_take isl_pw_aff *pa1,
3070
  __isl_take isl_pw_aff *pa2)
3071
0
{
3072
0
  return align_params_pw_pw_map_and(pa1, pa2, &isl_pw_aff_gt_map_aligned);
3073
0
}
3074
3075
/* Return a set containing those elements in the shared domain
3076
 * of the elements of list1 and list2 where each element in list1
3077
 * has the relation specified by "fn" with each element in list2.
3078
 */
3079
static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
3080
  __isl_take isl_pw_aff_list *list2,
3081
  __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
3082
            __isl_take isl_pw_aff *pwaff2))
3083
4.97k
{
3084
4.97k
  int i, j;
3085
4.97k
  isl_ctx *ctx;
3086
4.97k
  isl_set *set;
3087
4.97k
3088
4.97k
  if (!list1 || !list2)
3089
0
    goto error;
3090
4.97k
3091
4.97k
  ctx = isl_pw_aff_list_get_ctx(list1);
3092
4.97k
  if (list1->n < 1 || list2->n < 1)
3093
4.97k
    
isl_die0
(ctx, isl_error_invalid,
3094
4.97k
      "list should contain at least one element", goto error);
3095
4.97k
3096
4.97k
  set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
3097
10.0k
  for (i = 0; i < list1->n; 
++i5.10k
)
3098
10.3k
    
for (j = 0; 5.10k
j < list2->n;
++j5.29k
) {
3099
5.29k
      isl_set *set_ij;
3100
5.10k
3101
5.10k
      set_ij = fn(isl_pw_aff_copy(list1->p[i]),
3102
5.10k
            isl_pw_aff_copy(list2->p[j]));
3103
5.10k
      set = isl_set_intersect(set, set_ij);
3104
5.10k
    }
3105
4.97k
3106
4.97k
  isl_pw_aff_list_free(list1);
3107
4.97k
  isl_pw_aff_list_free(list2);
3108
4.97k
  return set;
3109
0
error:
3110
0
  isl_pw_aff_list_free(list1);
3111
0
  isl_pw_aff_list_free(list2);
3112
0
  return NULL;
3113
4.97k
}
3114
3115
/* Return a set containing those elements in the shared domain
3116
 * of the elements of list1 and list2 where each element in list1
3117
 * is equal to each element in list2.
3118
 */
3119
__isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
3120
  __isl_take isl_pw_aff_list *list2)
3121
495
{
3122
495
  return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
3123
495
}
3124
3125
__isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
3126
  __isl_take isl_pw_aff_list *list2)
3127
12
{
3128
12
  return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
3129
12
}
3130
3131
/* Return a set containing those elements in the shared domain
3132
 * of the elements of list1 and list2 where each element in list1
3133
 * is less than or equal to each element in list2.
3134
 */
3135
__isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
3136
  __isl_take isl_pw_aff_list *list2)
3137
2.93k
{
3138
2.93k
  return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
3139
2.93k
}
3140
3141
__isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
3142
  __isl_take isl_pw_aff_list *list2)
3143
350
{
3144
350
  return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
3145
350
}
3146
3147
__isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
3148
  __isl_take isl_pw_aff_list *list2)
3149
1.12k
{
3150
1.12k
  return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
3151
1.12k
}
3152
3153
__isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
3154
  __isl_take isl_pw_aff_list *list2)
3155
53
{
3156
53
  return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
3157
53
}
3158
3159
3160
/* Return a set containing those elements in the shared domain
3161
 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
3162
 */
3163
static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
3164
  __isl_take isl_pw_aff *pwaff2)
3165
3.96k
{
3166
3.96k
  isl_set *set_lt, *set_gt;
3167
3.96k
3168
3.96k
  set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
3169
3.96k
           isl_pw_aff_copy(pwaff2));
3170
3.96k
  set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
3171
3.96k
  return isl_set_union_disjoint(set_lt, set_gt);
3172
3.96k
}
3173
3174
__isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
3175
  __isl_take isl_pw_aff *pwaff2)
3176
3.96k
{
3177
3.96k
  return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
3178
3.96k
}
3179
3180
__isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
3181
  isl_int v)
3182
3.39k
{
3183
3.39k
  int i;
3184
3.39k
3185
3.39k
  if (isl_int_is_one(v))
3186
3.39k
    
return pwaff0
;
3187
3.39k
  if (!isl_int_is_pos(v))
3188
3.39k
    
isl_die0
(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
3189
3.39k
      "factor needs to be positive",
3190
3.39k
      return isl_pw_aff_free(pwaff));
3191
3.39k
  pwaff = isl_pw_aff_cow(pwaff);
3192
3.39k
  if (!pwaff)
3193
0
    return NULL;
3194
3.39k
  if (pwaff->n == 0)
3195
0
    return pwaff;
3196
3.39k
3197
7.02k
  
for (i = 0; 3.39k
i < pwaff->n;
++i3.63k
) {
3198
3.63k
    pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
3199
3.63k
    if (!pwaff->p[i].aff)
3200
0
      return isl_pw_aff_free(pwaff);
3201
3.63k
  }
3202
3.39k
3203
3.39k
  return pwaff;
3204
3.39k
}
3205
3206
__isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
3207
7.13k
{
3208
7.13k
  int i;
3209
7.13k
3210
7.13k
  pwaff = isl_pw_aff_cow(pwaff);
3211
7.13k
  if (!pwaff)
3212
0
    return NULL;
3213
7.13k
  if (pwaff->n == 0)
3214
0
    return pwaff;
3215
7.13k
3216
14.5k
  
for (i = 0; 7.13k
i < pwaff->n;
++i7.41k
) {
3217
7.41k
    pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
3218
7.41k
    if (!pwaff->p[i].aff)
3219
0
      return isl_pw_aff_free(pwaff);
3220
7.41k
  }
3221
7.13k
3222
7.13k
  return pwaff;
3223
7.13k
}
3224
3225
__isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
3226
75
{
3227
75
  int i;
3228
75
3229
75
  pwaff = isl_pw_aff_cow(pwaff);
3230
75
  if (!pwaff)
3231
0
    return NULL;
3232
75
  if (pwaff->n == 0)
3233
0
    return pwaff;
3234
75
3235
152
  
for (i = 0; 75
i < pwaff->n;
++i77
) {
3236
77
    pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
3237
77
    if (!pwaff->p[i].aff)
3238
0
      return isl_pw_aff_free(pwaff);
3239
77
  }
3240
75
3241
75
  return pwaff;
3242
75
}
3243
3244
/* Assuming that "cond1" and "cond2" are disjoint,
3245
 * return an affine expression that is equal to pwaff1 on cond1
3246
 * and to pwaff2 on cond2.
3247
 */
3248
static __isl_give isl_pw_aff *isl_pw_aff_select(
3249
  __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
3250
  __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
3251
137
{
3252
137
  pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
3253
137
  pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
3254
137
3255
137
  return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
3256
137
}
3257
3258
/* Return an affine expression that is equal to pwaff_true for elements
3259
 * where "cond" is non-zero and to pwaff_false for elements where "cond"
3260
 * is zero.
3261
 * That is, return cond ? pwaff_true : pwaff_false;
3262
 *
3263
 * If "cond" involves and NaN, then we conservatively return a NaN
3264
 * on its entire domain.  In principle, we could consider the pieces
3265
 * where it is NaN separately from those where it is not.
3266
 *
3267
 * If "pwaff_true" and "pwaff_false" are obviously equal to each other,
3268
 * then only use the domain of "cond" to restrict the domain.
3269
 */
3270
__isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
3271
  __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
3272
76
{
3273
76
  isl_set *cond_true, *cond_false;
3274
76
  isl_bool equal;
3275
76
3276
76
  if (!cond)
3277
0
    goto error;
3278
76
  if (isl_pw_aff_involves_nan(cond)) {
3279
0
    isl_space *space = isl_pw_aff_get_domain_space(cond);
3280
0
    isl_local_space *ls = isl_local_space_from_space(space);
3281
0
    isl_pw_aff_free(cond);
3282
0
    isl_pw_aff_free(pwaff_true);
3283
0
    isl_pw_aff_free(pwaff_false);
3284
0
    return isl_pw_aff_nan_on_domain(ls);
3285
0
  }
3286
76
3287
76
  pwaff_true = isl_pw_aff_align_params(pwaff_true,
3288
76
              isl_pw_aff_get_space(pwaff_false));
3289
76
  pwaff_false = isl_pw_aff_align_params(pwaff_false,
3290
76
              isl_pw_aff_get_space(pwaff_true));
3291
76
  equal = isl_pw_aff_plain_is_equal(pwaff_true, pwaff_false);
3292
76
  if (equal < 0)
3293
0
    goto error;
3294
76
  if (equal) {
3295
6
    isl_set *dom;
3296
6
3297
6
    dom = isl_set_coalesce(isl_pw_aff_domain(cond));
3298
6
    isl_pw_aff_free(pwaff_false);
3299
6
    return isl_pw_aff_intersect_domain(pwaff_true, dom);
3300
6
  }
3301
70
3302
70
  cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
3303
70
  cond_false = isl_pw_aff_zero_set(cond);
3304
70
  return isl_pw_aff_select(cond_true, pwaff_true,
3305
70
         cond_false, pwaff_false);
3306
0
error:
3307
0
  isl_pw_aff_free(cond);
3308
0
  isl_pw_aff_free(pwaff_true);
3309
0
  isl_pw_aff_free(pwaff_false);
3310
0
  return NULL;
3311
76
}
3312
3313
isl_bool isl_aff_is_cst(__isl_keep isl_aff *aff)
3314
42.3k
{
3315
42.3k
  if (!aff)
3316
0
    return isl_bool_error;
3317
42.3k
3318
42.3k
  return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
3319
42.3k
}
3320
3321
/* Check whether pwaff is a piecewise constant.
3322
 */
3323
isl_bool isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
3324
227
{
3325
227
  int i;
3326
227
3327
227
  if (!pwaff)
3328
0
    return isl_bool_error;
3329
227
3330
454
  
for (i = 0; 227
i < pwaff->n;
++i227
) {
3331
227
    isl_bool is_cst = isl_aff_is_cst(pwaff->p[i].aff);
3332
227
    if (is_cst < 0 || !is_cst)
3333
0
      return is_cst;
3334
227
  }
3335
227
3336
227
  return isl_bool_true;
3337
227
}
3338
3339
/* Are all elements of "mpa" piecewise constants?
3340
 */
3341
isl_bool isl_multi_pw_aff_is_cst(__isl_keep isl_multi_pw_aff *mpa)
3342
0
{
3343
0
  int i;
3344
0
3345
0
  if (!mpa)
3346
0
    return isl_bool_error;
3347
0
3348
0
  for (i = 0; i < mpa->n; ++i) {
3349
0
    isl_bool is_cst = isl_pw_aff_is_cst(mpa->p[i]);
3350
0
    if (is_cst < 0 || !is_cst)
3351
0
      return is_cst;
3352
0
  }
3353
0
3354
0
  return isl_bool_true;
3355
0
}
3356
3357
/* Return the product of "aff1" and "aff2".
3358
 *
3359
 * If either of the two is NaN, then the result is NaN.
3360
 *
3361
 * Otherwise, at least one of "aff1" or "aff2" needs to be a constant.
3362
 */
3363
__isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
3364
  __isl_take isl_aff *aff2)
3365
18.8k
{
3366
18.8k
  if (!aff1 || !aff2)
3367
0
    goto error;
3368
18.8k
3369
18.8k
  if (isl_aff_is_nan(aff1)) {
3370
2
    isl_aff_free(aff2);
3371
2
    return aff1;
3372
2
  }
3373
18.8k
  if (isl_aff_is_nan(aff2)) {
3374
2
    isl_aff_free(aff1);
3375
2
    return aff2;
3376
2
  }
3377
18.8k
3378
18.8k
  if (!isl_aff_is_cst(aff2) && 
isl_aff_is_cst(aff1)3.10k
)
3379
3.10k
    return isl_aff_mul(aff2, aff1);
3380
15.7k
3381
15.7k
  if (!isl_aff_is_cst(aff2))
3382
15.7k
    
isl_die0
(isl_aff_get_ctx(aff1), isl_error_invalid,
3383
15.7k
      "at least one affine expression should be constant",
3384
15.7k
      goto error);
3385
15.7k
3386
15.7k
  aff1 = isl_aff_cow(aff1);
3387
15.7k
  if (!aff1 || !aff2)
3388
0
    goto error;
3389
15.7k
3390
15.7k
  aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
3391
15.7k
  aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
3392
15.7k
3393
15.7k
  isl_aff_free(aff2);
3394
15.7k
  return aff1;
3395
0
error:
3396
0
  isl_aff_free(aff1);
3397
0
  isl_aff_free(aff2);
3398
0
  return NULL;
3399
18.8k
}
3400
3401
/* Divide "aff1" by "aff2", assuming "aff2" is a constant.
3402
 *
3403
 * If either of the two is NaN, then the result is NaN.
3404
 */
3405
__isl_give isl_aff *isl_aff_div(__isl_take isl_aff *aff1,
3406
  __isl_take isl_aff *aff2)
3407
140
{
3408
140
  int is_cst;
3409
140
  int neg;
3410
140
3411
140
  if (!aff1 || !aff2)
3412
0
    goto error;
3413
140
3414
140
  if (isl_aff_is_nan(aff1)) {
3415
2
    isl_aff_free(aff2);
3416
2
    return aff1;
3417
2
  }
3418
138
  if (isl_aff_is_nan(aff2)) {
3419
2
    isl_aff_free(aff1);
3420
2
    return aff2;
3421
2
  }
3422
136
3423
136
  is_cst = isl_aff_is_cst(aff2);
3424
136
  if (is_cst < 0)
3425
0
    goto error;
3426
136
  if (!is_cst)
3427
136
    
isl_die0
(isl_aff_get_ctx(aff2), isl_error_invalid,
3428
136
      "second argument should be a constant", goto error);
3429
136
3430
136
  if (!aff2)
3431
0
    goto error;
3432
136
3433
136
  neg = isl_int_is_neg(aff2->v->el[1]);
3434
136
  if (neg) {
3435
13
    isl_int_neg(aff2->v->el[0], aff2->v->el[0]);
3436
13
    isl_int_neg(aff2->v->el[1], aff2->v->el[1]);
3437
13
  }
3438
136
3439
136
  aff1 = isl_aff_scale(aff1, aff2->v->el[0]);
3440
136
  aff1 = isl_aff_scale_down(aff1, aff2->v->el[1]);
3441
136
3442
136
  if (neg) {
3443
13
    isl_int_neg(aff2->v->el[0], aff2->v->el[0]);
3444
13
    isl_int_neg(aff2->v->el[1], aff2->v->el[1]);
3445
13
  }
3446
136
3447
136
  isl_aff_free(aff2);
3448
136
  return aff1;
3449
0
error:
3450
0
  isl_aff_free(aff1);
3451
0
  isl_aff_free(aff2);
3452
0
  return NULL;
3453
140
}
3454
3455
static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
3456
  __isl_take isl_pw_aff *pwaff2)
3457
58.8k
{
3458
58.8k
  return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
3459
58.8k
}
3460
3461
__isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
3462
  __isl_take isl_pw_aff *pwaff2)
3463
58.8k
{
3464
58.8k
  return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
3465
58.8k
}
3466
3467
__isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
3468
  __isl_take isl_pw_aff *pwaff2)
3469
3.07k
{
3470
3.07k
  return isl_pw_aff_union_add_(pwaff1, pwaff2);
3471
3.07k
}
3472
3473
static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
3474
  __isl_take isl_pw_aff *pwaff2)
3475
15.3k
{
3476
15.3k
  return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
3477
15.3k
}
3478
3479
__isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
3480
  __isl_take isl_pw_aff *pwaff2)
3481
15.3k
{
3482
15.3k
  return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
3483
15.3k
}
3484
3485
static __isl_give isl_pw_aff *pw_aff_div(__isl_take isl_pw_aff *pa1,
3486
  __isl_take isl_pw_aff *pa2)
3487
115
{
3488
115
  return isl_pw_aff_on_shared_domain(pa1, pa2, &isl_aff_div);
3489
115
}
3490
3491
/* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
3492
 */
3493
__isl_give isl_pw_aff *isl_pw_aff_div(__isl_take isl_pw_aff *pa1,
3494
  __isl_take isl_pw_aff *pa2)
3495
115
{
3496
115
  int is_cst;
3497
115
3498
115
  is_cst = isl_pw_aff_is_cst(pa2);
3499
115
  if (is_cst < 0)
3500
0
    goto error;
3501
115
  if (!is_cst)
3502
115
    
isl_die0
(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3503
115
      "second argument should be a piecewise constant",
3504
115
      goto error);
3505
115
  return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_div);
3506
0
error:
3507
0
  isl_pw_aff_free(pa1);
3508
0
  isl_pw_aff_free(pa2);
3509
0
  return NULL;
3510
115
}
3511
3512
/* Compute the quotient of the integer division of "pa1" by "pa2"
3513
 * with rounding towards zero.
3514
 * "pa2" is assumed to be a piecewise constant.
3515
 *
3516
 * In particular, return
3517
 *
3518
 *  pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
3519
 *
3520
 */
3521
__isl_give isl_pw_aff *isl_pw_aff_tdiv_q(__isl_take isl_pw_aff *pa1,
3522
  __isl_take isl_pw_aff *pa2)
3523
75
{
3524
75
  int is_cst;
3525
75
  isl_set *cond;
3526
75
  isl_pw_aff *f, *c;
3527
75
3528
75
  is_cst = isl_pw_aff_is_cst(pa2);
3529
75
  if (is_cst < 0)
3530
0
    goto error;
3531
75
  if (!is_cst)
3532
75
    
isl_die0
(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3533
75
      "second argument should be a piecewise constant",
3534
75
      goto error);
3535
75
3536
75
  pa1 = isl_pw_aff_div(pa1, pa2);
3537
75
3538
75
  cond = isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1));
3539
75
  f = isl_pw_aff_floor(isl_pw_aff_copy(pa1));
3540
75
  c = isl_pw_aff_ceil(pa1);
3541
75
  return isl_pw_aff_cond(isl_set_indicator_function(cond), f, c);
3542
0
error:
3543
0
  isl_pw_aff_free(pa1);
3544
0
  isl_pw_aff_free(pa2);
3545
0
  return NULL;
3546
75
}
3547
3548
/* Compute the remainder of the integer division of "pa1" by "pa2"
3549
 * with rounding towards zero.
3550
 * "pa2" is assumed to be a piecewise constant.
3551
 *
3552
 * In particular, return
3553
 *
3554
 *  pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
3555
 *
3556
 */
3557
__isl_give isl_pw_aff *isl_pw_aff_tdiv_r(__isl_take isl_pw_aff *pa1,
3558
  __isl_take isl_pw_aff *pa2)
3559
36
{
3560
36
  int is_cst;
3561
36
  isl_pw_aff *res;
3562
36
3563
36
  is_cst = isl_pw_aff_is_cst(pa2);
3564
36
  if (is_cst < 0)
3565
0
    goto error;
3566
36
  if (!is_cst)
3567
36
    
isl_die0
(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3568
36
      "second argument should be a piecewise constant",
3569
36
      goto error);
3570
36
  res = isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1), isl_pw_aff_copy(pa2));
3571
36
  res = isl_pw_aff_mul(pa2, res);
3572
36
  res = isl_pw_aff_sub(pa1, res);
3573
36
  return res;
3574
0
error:
3575
0
  isl_pw_aff_free(pa1);
3576
0
  isl_pw_aff_free(pa2);
3577
0
  return NULL;
3578
36
}
3579
3580
/* Does either of "pa1" or "pa2" involve any NaN2?
3581
 */
3582
static isl_bool either_involves_nan(__isl_keep isl_pw_aff *pa1,
3583
  __isl_keep isl_pw_aff *pa2)
3584
69
{
3585
69
  isl_bool has_nan;
3586
69
3587
69
  has_nan = isl_pw_aff_involves_nan(pa1);
3588
69
  if (has_nan < 0 || has_nan)
3589
1
    return has_nan;
3590
68
  return isl_pw_aff_involves_nan(pa2);
3591
68
}
3592
3593
/* Replace "pa1" and "pa2" (at least one of which involves a NaN)
3594
 * by a NaN on their shared domain.
3595
 *
3596
 * In principle, the result could be refined to only being NaN
3597
 * on the parts of this domain where at least one of "pa1" or "pa2" is NaN.
3598
 */
3599
static __isl_give isl_pw_aff *replace_by_nan(__isl_take isl_pw_aff *pa1,
3600
  __isl_take isl_pw_aff *pa2)
3601
2
{
3602
2
  isl_local_space *ls;
3603
2
  isl_set *dom;
3604
2
  isl_pw_aff *pa;
3605
2
3606
2
  dom = isl_set_intersect(isl_pw_aff_domain(pa1), isl_pw_aff_domain(pa2));
3607
2
  ls = isl_local_space_from_space(isl_set_get_space(dom));
3608
2
  pa = isl_pw_aff_nan_on_domain(ls);
3609
2
  pa = isl_pw_aff_intersect_domain(pa, dom);
3610
2
3611
2
  return pa;
3612
2
}
3613
3614
static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
3615
  __isl_take isl_pw_aff *pwaff2)
3616
7
{
3617
7
  isl_set *le;
3618
7
  isl_set *dom;
3619
7
3620
7
  dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
3621
7
        isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
3622
7
  le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
3623
7
        isl_pw_aff_copy(pwaff2));
3624
7
  dom = isl_set_subtract(dom, isl_set_copy(le));
3625
7
  return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
3626
7
}
3627
3628
static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
3629
  __isl_take isl_pw_aff *pwaff2)
3630
60
{
3631
60
  isl_set *ge;
3632
60
  isl_set *dom;
3633
60
3634
60
  dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
3635
60
        isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
3636
60
  ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
3637
60
        isl_pw_aff_copy(pwaff2));
3638
60
  dom = isl_set_subtract(dom, isl_set_copy(ge));
3639
60
  return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
3640
60
}
3641
3642
/* Return an expression for the minimum (if "max" is not set) or
3643
 * the maximum (if "max" is set) of "pa1" and "pa2".
3644
 * If either expression involves any NaN, then return a NaN
3645
 * on the shared domain as result.
3646
 */
3647
static __isl_give isl_pw_aff *pw_aff_min_max(__isl_take isl_pw_aff *pa1,
3648
  __isl_take isl_pw_aff *pa2, int max)
3649
69
{
3650
69
  isl_bool has_nan;
3651
69
3652
69
  has_nan = either_involves_nan(pa1, pa2);
3653
69
  if (has_nan < 0)
3654
0
    pa1 = isl_pw_aff_free(pa1);
3655
69
  else if (has_nan)
3656
2
    return replace_by_nan(pa1, pa2);
3657
67
3658
67
  if (max)
3659
60
    return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_max);
3660
7
  else
3661
7
    return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_min);
3662
69
}
3663
3664
/* Return an expression for the minimum of "pwaff1" and "pwaff2".
3665
 */
3666
__isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
3667
  __isl_take isl_pw_aff *pwaff2)
3668
9
{
3669
9
  return pw_aff_min_max(pwaff1, pwaff2, 0);
3670
9
}
3671
3672
/* Return an expression for the maximum of "pwaff1" and "pwaff2".
3673
 */
3674
__isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
3675
  __isl_take isl_pw_aff *pwaff2)
3676
60
{
3677
60
  return pw_aff_min_max(pwaff1, pwaff2, 1);
3678
60
}
3679
3680
static __isl_give isl_pw_aff *pw_aff_list_reduce(
3681
  __isl_take isl_pw_aff_list *list,
3682
  __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
3683
          __isl_take isl_pw_aff *pwaff2))
3684
6
{
3685
6
  int i;
3686
6
  isl_ctx *ctx;
3687
6
  isl_pw_aff *res;
3688
6
3689
6
  if (!list)
3690
0
    return NULL;
3691
6
3692
6
  ctx = isl_pw_aff_list_get_ctx(list);
3693
6
  if (list->n < 1)
3694
6
    
isl_die0
(ctx, isl_error_invalid,
3695
6
      "list should contain at least one element", goto error);
3696
6
3697
6
  res = isl_pw_aff_copy(list->p[0]);
3698
12
  for (i = 1; i < list->n; 
++i6
)
3699
6
    res = fn(res, isl_pw_aff_copy(list->p[i]));
3700
6
3701
6
  isl_pw_aff_list_free(list);
3702
6
  return res;
3703
0
error:
3704
0
  isl_pw_aff_list_free(list);
3705
0
  return NULL;
3706
6
}
3707
3708
/* Return an isl_pw_aff that maps each element in the intersection of the
3709
 * domains of the elements of list to the minimal corresponding affine
3710
 * expression.
3711
 */
3712
__isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
3713
5
{
3714
5
  return pw_aff_list_reduce(list, &isl_pw_aff_min);
3715
5
}
3716
3717
/* Return an isl_pw_aff that maps each element in the intersection of the
3718
 * domains of the elements of list to the maximal corresponding affine
3719
 * expression.
3720
 */
3721
__isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
3722
1
{
3723
1
  return pw_aff_list_reduce(list, &isl_pw_aff_max);
3724
1
}
3725
3726
/* Mark the domains of "pwaff" as rational.
3727
 */
3728
__isl_give isl_pw_aff *isl_pw_aff_set_rational(__isl_take isl_pw_aff *pwaff)
3729
225
{
3730
225
  int i;
3731
225
3732
225
  pwaff = isl_pw_aff_cow(pwaff);
3733
225
  if (!pwaff)
3734
0
    return NULL;
3735
225
  if (pwaff->n == 0)
3736
0
    return pwaff;
3737
225
3738
450
  
for (i = 0; 225
i < pwaff->n;
++i225
) {
3739
225
    pwaff->p[i].set = isl_set_set_rational(pwaff->p[i].set);
3740
225
    if (!pwaff->p[i].set)
3741
0
      return isl_pw_aff_free(pwaff);
3742
225
  }
3743
225
3744
225
  return pwaff;
3745
225
}
3746
3747
/* Mark the domains of the elements of "list" as rational.
3748
 */
3749
__isl_give isl_pw_aff_list *isl_pw_aff_list_set_rational(
3750
  __isl_take isl_pw_aff_list *list)
3751
48
{
3752
48
  int i, n;
3753
48
3754
48
  if (!list)
3755
0
    return NULL;
3756
48
  if (list->n == 0)
3757
0
    return list;
3758
48
3759
48
  n = list->n;
3760
98
  for (i = 0; i < n; 
++i50
) {
3761
50
    isl_pw_aff *pa;
3762
50
3763
50
    pa = isl_pw_aff_list_get_pw_aff(list, i);
3764
50
    pa = isl_pw_aff_set_rational(pa);
3765
50
    list = isl_pw_aff_list_set_pw_aff(list, i, pa);
3766
50
  }
3767
48
3768
48
  return list;
3769
48
}
3770
3771
/* Do the parameters of "aff" match those of "space"?
3772
 */
3773
isl_bool isl_aff_matching_params(__isl_keep isl_aff *aff,
3774
  __isl_keep isl_space *space)
3775
939k
{
3776
939k
  isl_space *aff_space;
3777
939k
  isl_bool match;
3778
939k
3779
939k
  if (!aff || !space)
3780
0
    return isl_bool_error;
3781
939k
3782
939k
  aff_space = isl_aff_get_domain_space(aff);
3783
939k
3784
939k
  match = isl_space_has_equal_params(space, aff_space);
3785
939k
3786
939k
  isl_space_free(aff_space);
3787
939k
  return match;
3788
939k
}
3789
3790
/* Check that the domain space of "aff" matches "space".
3791
 */
3792
isl_stat isl_aff_check_match_domain_space(__isl_keep isl_aff *aff,
3793
  __isl_keep isl_space *space)
3794
939k
{
3795
939k
  isl_space *aff_space;
3796
939k
  isl_bool match;
3797
939k
3798
939k
  if (!aff || !space)
3799
0
    return isl_stat_error;
3800
939k
3801
939k
  aff_space = isl_aff_get_domain_space(aff);
3802
939k
3803
939k
  match = isl_space_has_equal_params(space, aff_space);
3804
939k
  if (match < 0)
3805
0
    goto error;
3806
939k
  if (!match)
3807
939k
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
3808
939k
      "parameters don't match", goto error);
3809
939k
  match = isl_space_tuple_is_equal(space, isl_dim_in,
3810
939k
          aff_space, isl_dim_set);
3811
939k
  if (match < 0)
3812
0
    goto error;
3813
939k
  if (!match)
3814
939k
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
3815
939k
      "domains don't match", goto error);
3816
939k
  isl_space_free(aff_space);
3817
939k
  return isl_stat_ok;
3818
0
error:
3819
0
  isl_space_free(aff_space);
3820
0
  return isl_stat_error;
3821
939k
}
3822
3823
#undef BASE
3824
#define BASE aff
3825
#undef DOMBASE
3826
#define DOMBASE set
3827
#define NO_DOMAIN
3828
3829
#include <isl_multi_templ.c>
3830
#include <isl_multi_apply_set.c>
3831
#include <isl_multi_cmp.c>
3832
#include <isl_multi_floor.c>
3833
#include <isl_multi_gist.c>
3834
3835
#undef NO_DOMAIN
3836
3837
/* Construct an isl_multi_aff living in "space" that corresponds
3838
 * to the affine transformation matrix "mat".
3839
 */
3840
__isl_give isl_multi_aff *isl_multi_aff_from_aff_mat(
3841
  __isl_take isl_space *space, __isl_take isl_mat *mat)
3842
2
{
3843
2
  isl_ctx *ctx;
3844
2
  isl_local_space *ls = NULL;
3845
2
  isl_multi_aff *ma = NULL;
3846
2
  int n_row, n_col, n_out, total;
3847
2
  int i;
3848
2
3849
2
  if (!space || !mat)
3850
0
    goto error;
3851
2
3852
2
  ctx = isl_mat_get_ctx(mat);
3853
2
3854
2
  n_row = isl_mat_rows(mat);
3855
2
  n_col = isl_mat_cols(mat);
3856
2
  if (n_row < 1)
3857
2
    
isl_die0
(ctx, isl_error_invalid,
3858
2
      "insufficient number of rows", goto error);
3859
2
  if (n_col < 1)
3860
2
    
isl_die0
(ctx, isl_error_invalid,
3861
2
      "insufficient number of columns", goto error);
3862
2
  n_out = isl_space_dim(space, isl_dim_out);
3863
2
  total = isl_space_dim(space, isl_dim_all);
3864
2
  if (1 + n_out != n_row || 2 + total != n_row + n_col)
3865
2
    
isl_die0
(ctx, isl_error_invalid,
3866
2
      "dimension mismatch", goto error);
3867
2
3868
2
  ma = isl_multi_aff_zero(isl_space_copy(space));
3869
2
  ls = isl_local_space_from_space(isl_space_domain(space));
3870
2
3871
4
  for (i = 0; i < n_row - 1; 
++i2
) {
3872
2
    isl_vec *v;
3873
2
    isl_aff *aff;
3874
2
3875
2
    v = isl_vec_alloc(ctx, 1 + n_col);
3876
2
    if (!v)
3877
0
      goto error;
3878
2
    isl_int_set(v->el[0], mat->row[0][0]);
3879
2
    isl_seq_cpy(v->el + 1, mat->row[1 + i], n_col);
3880
2
    v = isl_vec_normalize(v);
3881
2
    aff = isl_aff_alloc_vec(isl_local_space_copy(ls), v);
3882
2
    ma = isl_multi_aff_set_aff(ma, i, aff);
3883
2
  }
3884
2
3885
2
  isl_local_space_free(ls);
3886
2
  isl_mat_free(mat);
3887
2
  return ma;
3888
0
error:
3889
0
  isl_local_space_free(ls);
3890
0
  isl_mat_free(mat);
3891
0
  isl_multi_aff_free(ma);
3892
0
  return NULL;
3893
2
}
3894
3895
/* Remove any internal structure of the domain of "ma".
3896
 * If there is any such internal structure in the input,
3897
 * then the name of the corresponding space is also removed.
3898
 */
3899
__isl_give isl_multi_aff *isl_multi_aff_flatten_domain(
3900
  __isl_take isl_multi_aff *ma)
3901
0
{
3902
0
  isl_space *space;
3903
0
3904
0
  if (!ma)
3905
0
    return NULL;
3906
0
3907
0
  if (!ma->space->nested[0])
3908
0
    return ma;
3909
0
3910
0
  space = isl_multi_aff_get_space(ma);
3911
0
  space = isl_space_flatten_domain(space);
3912
0
  ma = isl_multi_aff_reset_space(ma, space);
3913
0
3914
0
  return ma;
3915
0
}
3916
3917
/* Given a map space, return an isl_multi_aff that maps a wrapped copy
3918
 * of the space to its domain.
3919
 */
3920
__isl_give isl_multi_aff *isl_multi_aff_domain_map(__isl_take isl_space *space)
3921
747
{
3922
747
  int i, n_in;
3923
747
  isl_local_space *ls;
3924
747
  isl_multi_aff *ma;
3925
747
3926
747
  if (!space)
3927
0
    return NULL;
3928
747
  if (!isl_space_is_map(space))
3929
747
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
3930
747
      "not a map space", goto error);
3931
747
3932
747
  n_in = isl_space_dim(space, isl_dim_in);
3933
747
  space = isl_space_domain_map(space);
3934
747
3935
747
  ma = isl_multi_aff_alloc(isl_space_copy(space));
3936
747
  if (n_in == 0) {
3937
4
    isl_space_free(space);
3938
4
    return ma;
3939
4
  }
3940
743
3941
743
  space = isl_space_domain(space);
3942
743
  ls = isl_local_space_from_space(space);
3943
1.84k
  for (i = 0; i < n_in; 
++i1.10k
) {
3944
1.10k
    isl_aff *aff;
3945
1.10k
3946
1.10k
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3947
1.10k
            isl_dim_set, i);
3948
1.10k
    ma = isl_multi_aff_set_aff(ma, i, aff);
3949
1.10k
  }
3950
743
  isl_local_space_free(ls);
3951
743
  return ma;
3952
0
error:
3953
0
  isl_space_free(space);
3954
0
  return NULL;
3955
747
}
3956
3957
/* Given a map space, return an isl_multi_aff that maps a wrapped copy
3958
 * of the space to its range.
3959
 */
3960
__isl_give isl_multi_aff *isl_multi_aff_range_map(__isl_take isl_space *space)
3961
2
{
3962
2
  int i, n_in, n_out;
3963
2
  isl_local_space *ls;
3964
2
  isl_multi_aff *ma;
3965
2
3966
2
  if (!space)
3967
0
    return NULL;
3968
2
  if (!isl_space_is_map(space))
3969
2
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
3970
2
      "not a map space", goto error);
3971
2
3972
2
  n_in = isl_space_dim(space, isl_dim_in);
3973
2
  n_out = isl_space_dim(space, isl_dim_out);
3974
2
  space = isl_space_range_map(space);
3975
2
3976
2
  ma = isl_multi_aff_alloc(isl_space_copy(space));
3977
2
  if (n_out == 0) {
3978
0
    isl_space_free(space);
3979
0
    return ma;
3980
0
  }
3981
2
3982
2
  space = isl_space_domain(space);
3983
2
  ls = isl_local_space_from_space(space);
3984
6
  for (i = 0; i < n_out; 
++i4
) {
3985
4
    isl_aff *aff;
3986
4
3987
4
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3988
4
            isl_dim_set, n_in + i);
3989
4
    ma = isl_multi_aff_set_aff(ma, i, aff);
3990
4
  }
3991
2
  isl_local_space_free(ls);
3992
2
  return ma;
3993
0
error:
3994
0
  isl_space_free(space);
3995
0
  return NULL;
3996
2
}
3997
3998
/* Given a map space, return an isl_pw_multi_aff that maps a wrapped copy
3999
 * of the space to its range.
4000
 */
4001
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_range_map(
4002
  __isl_take isl_space *space)
4003
0
{
4004
0
  return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_range_map(space));
4005
0
}
4006
4007
/* Given the space of a set and a range of set dimensions,
4008
 * construct an isl_multi_aff that projects out those dimensions.
4009
 */
4010
__isl_give isl_multi_aff *isl_multi_aff_project_out_map(
4011
  __isl_take isl_space *space, enum isl_dim_type type,
4012
  unsigned first, unsigned n)
4013
2.43k
{
4014
2.43k
  int i, dim;
4015
2.43k
  isl_local_space *ls;
4016
2.43k
  isl_multi_aff *ma;
4017
2.43k
4018
2.43k
  if (!space)
4019
0
    return NULL;
4020
2.43k
  if (!isl_space_is_set(space))
4021
2.43k
    
isl_die0
(isl_space_get_ctx(space), isl_error_unsupported,
4022
2.43k
      "expecting set space", goto error);
4023
2.43k
  if (type != isl_dim_set)
4024
2.43k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
4025
2.43k
      "only set dimensions can be projected out", goto error);
4026
2.43k
4027
2.43k
  dim = isl_space_dim(space, isl_dim_set);
4028
2.43k
  if (first + n > dim)
4029
2.43k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
4030
2.43k
      "range out of bounds", goto error);
4031
2.43k
4032
2.43k
  space = isl_space_from_domain(space);
4033
2.43k
  space = isl_space_add_dims(space, isl_dim_out, dim - n);
4034
2.43k
4035
2.43k
  if (dim == n)
4036
0
    return isl_multi_aff_alloc(space);
4037
2.43k
4038
2.43k
  ma = isl_multi_aff_alloc(isl_space_copy(space));
4039
2.43k
  space = isl_space_domain(space);
4040
2.43k
  ls = isl_local_space_from_space(space);
4041
2.43k
4042
5.54k
  for (i = 0; i < first; 
++i3.11k
) {
4043
3.11k
    isl_aff *aff;
4044
3.11k
4045
3.11k
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
4046
3.11k
            isl_dim_set, i);
4047
3.11k
    ma = isl_multi_aff_set_aff(ma, i, aff);
4048
3.11k
  }
4049
2.43k
4050
2.47k
  for (i = 0; i < dim - (first + n); 
++i39
) {
4051
39
    isl_aff *aff;
4052
39
4053
39
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
4054
39
            isl_dim_set, first + n + i);
4055
39
    ma = isl_multi_aff_set_aff(ma, first + i, aff);
4056
39
  }
4057
2.43k
4058
2.43k
  isl_local_space_free(ls);
4059
2.43k
  return ma;
4060
0
error:
4061
0
  isl_space_free(space);
4062
0
  return NULL;
4063
2.43k
}
4064
4065
/* Given the space of a set and a range of set dimensions,
4066
 * construct an isl_pw_multi_aff that projects out those dimensions.
4067
 */
4068
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_project_out_map(
4069
  __isl_take isl_space *space, enum isl_dim_type type,
4070
  unsigned first, unsigned n)
4071
2.36k
{
4072
2.36k
  isl_multi_aff *ma;
4073
2.36k
4074
2.36k
  ma = isl_multi_aff_project_out_map(space, type, first, n);
4075
2.36k
  return isl_pw_multi_aff_from_multi_aff(ma);
4076
2.36k
}
4077
4078
/* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
4079
 * domain.
4080
 */
4081
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
4082
  __isl_take isl_multi_aff *ma)
4083
5.60k
{
4084
5.60k
  isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
4085
5.60k
  return isl_pw_multi_aff_alloc(dom, ma);
4086
5.60k
}
4087
4088
/* Create a piecewise multi-affine expression in the given space that maps each
4089
 * input dimension to the corresponding output dimension.
4090
 */
4091
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity(
4092
  __isl_take isl_space *space)
4093
25
{
4094
25
  return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space));
4095
25
}
4096
4097
/* Exploit the equalities in "eq" to simplify the affine expressions.
4098
 */
4099
static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
4100
  __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
4101
2.89k
{
4102
2.89k
  int i;
4103
2.89k
4104
2.89k
  maff = isl_multi_aff_cow(maff);
4105
2.89k
  if (!maff || !eq)
4106
0
    goto error;
4107
2.89k
4108
9.10k
  
for (i = 0; 2.89k
i < maff->n;
++i6.21k
) {
4109
6.21k
    maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
4110
6.21k
                isl_basic_set_copy(eq));
4111
6.21k
    if (!maff->p[i])
4112
0
      goto error;
4113
6.21k
  }
4114
2.89k
4115
2.89k
  isl_basic_set_free(eq);
4116
2.89k
  return maff;
4117
0
error:
4118
0
  isl_basic_set_free(eq);
4119
0
  isl_multi_aff_free(maff);
4120
0
  return NULL;
4121
2.89k
}
4122
4123
__isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
4124
  isl_int f)
4125
0
{
4126
0
  int i;
4127
0
4128
0
  maff = isl_multi_aff_cow(maff);
4129
0
  if (!maff)
4130
0
    return NULL;
4131
0
4132
0
  for (i = 0; i < maff->n; ++i) {
4133
0
    maff->p[i] = isl_aff_scale(maff->p[i], f);
4134
0
    if (!maff->p[i])
4135
0
      return isl_multi_aff_free(maff);
4136
0
  }
4137
0
4138
0
  return maff;
4139
0
}
4140
4141
__isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
4142
  __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
4143
2
{
4144
2
  maff1 = isl_multi_aff_add(maff1, maff2);
4145
2
  maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
4146
2
  return maff1;
4147
2
}
4148
4149
int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
4150
28.9k
{
4151
28.9k
  if (!maff)
4152
0
    return -1;
4153
28.9k
4154
28.9k
  return 0;
4155
28.9k
}
4156
4157
/* Return the set of domain elements where "ma1" is lexicographically
4158
 * smaller than or equal to "ma2".
4159
 */
4160
__isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1,
4161
  __isl_take isl_multi_aff *ma2)
4162
525
{
4163
525
  return isl_multi_aff_lex_ge_set(ma2, ma1);
4164
525
}
4165
4166
/* Return the set of domain elements where "ma1" is lexicographically
4167
 * smaller than "ma2".
4168
 */
4169
__isl_give isl_set *isl_multi_aff_lex_lt_set(__isl_take isl_multi_aff *ma1,
4170
  __isl_take isl_multi_aff *ma2)
4171
0
{
4172
0
  return isl_multi_aff_lex_gt_set(ma2, ma1);
4173
0
}
4174
4175
/* Return the set of domain elements where "ma1" and "ma2"
4176
 * satisfy "order".
4177
 */
4178
static __isl_give isl_set *isl_multi_aff_order_set(
4179
  __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2,
4180
  __isl_give isl_map *order(__isl_take isl_space *set_space))
4181
1.28k
{
4182
1.28k
  isl_space *space;
4183
1.28k
  isl_map *map1, *map2;
4184
1.28k
  isl_map *map, *ge;
4185
1.28k
4186
1.28k
  map1 = isl_map_from_multi_aff(ma1);
4187
1.28k
  map2 = isl_map_from_multi_aff(ma2);
4188
1.28k
  map = isl_map_range_product(map1, map2);
4189
1.28k
  space = isl_space_range(isl_map_get_space(map));
4190
1.28k
  space = isl_space_domain(isl_space_unwrap(space));
4191
1.28k
  ge = order(space);
4192
1.28k
  map = isl_map_intersect_range(map, isl_map_wrap(ge));
4193
1.28k
4194
1.28k
  return isl_map_domain(map);
4195
1.28k
}
4196
4197
/* Return the set of domain elements where "ma1" is lexicographically
4198
 * greater than or equal to "ma2".
4199
 */
4200
__isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1,
4201
  __isl_take isl_multi_aff *ma2)
4202
1.28k
{
4203
1.28k
  return isl_multi_aff_order_set(ma1, ma2, &isl_map_lex_ge);
4204
1.28k
}
4205
4206
/* Return the set of domain elements where "ma1" is lexicographically
4207
 * greater than "ma2".
4208
 */
4209
__isl_give isl_set *isl_multi_aff_lex_gt_set(__isl_take isl_multi_aff *ma1,
4210
  __isl_take isl_multi_aff *ma2)
4211
0
{
4212
0
  return isl_multi_aff_order_set(ma1, ma2, &isl_map_lex_gt);
4213
0
}
4214
4215
#undef PW
4216
27.4k
#define PW isl_pw_multi_aff
4217
#undef EL
4218
3.65k
#define EL isl_multi_aff
4219
#undef EL_IS_ZERO
4220
#define EL_IS_ZERO is_empty
4221
#undef ZERO
4222
#define ZERO empty
4223
#undef IS_ZERO
4224
#define IS_ZERO is_empty
4225
#undef FIELD
4226
115k
#define FIELD maff
4227
#undef DEFAULT_IS_ZERO
4228
0
#define DEFAULT_IS_ZERO 0
4229
4230
#define NO_SUB
4231
#define NO_EVAL
4232
#define NO_OPT
4233
#define NO_INVOLVES_DIMS
4234
#define NO_INSERT_DIMS
4235
#define NO_LIFT
4236
#define NO_MORPH
4237
4238
#include <isl_pw_templ.c>
4239
#include <isl_pw_union_opt.c>
4240
4241
#undef NO_SUB
4242
4243
#undef UNION
4244
12.2k
#define UNION isl_union_pw_multi_aff
4245
#undef PART
4246
33.2k
#define PART isl_pw_multi_aff
4247
#undef PARTS
4248
#define PARTS pw_multi_aff
4249
4250
#include <isl_union_multi.c>
4251
#include <isl_union_neg.c>
4252
4253
static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax(
4254
  __isl_take isl_pw_multi_aff *pma1,
4255
  __isl_take isl_pw_multi_aff *pma2)
4256
984
{
4257
984
  return isl_pw_multi_aff_union_opt_cmp(pma1, pma2,
4258
984
              &isl_multi_aff_lex_ge_set);
4259
984
}
4260
4261
/* Given two piecewise multi affine expressions, return a piecewise
4262
 * multi-affine expression defined on the union of the definition domains
4263
 * of the inputs that is equal to the lexicographic maximum of the two
4264
 * inputs on each cell.  If only one of the two inputs is defined on
4265
 * a given cell, then it is considered to be the maximum.
4266
 */
4267
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmax(
4268
  __isl_take isl_pw_multi_aff *pma1,
4269
  __isl_take isl_pw_multi_aff *pma2)
4270
984
{
4271
984
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4272
984
                &pw_multi_aff_union_lexmax);
4273
984
}
4274
4275
static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin(
4276
  __isl_take isl_pw_multi_aff *pma1,
4277
  __isl_take isl_pw_multi_aff *pma2)
4278
606
{
4279
606
  return isl_pw_multi_aff_union_opt_cmp(pma1, pma2,
4280
606
              &isl_multi_aff_lex_le_set);
4281
606
}
4282
4283
/* Given two piecewise multi affine expressions, return a piecewise
4284
 * multi-affine expression defined on the union of the definition domains
4285
 * of the inputs that is equal to the lexicographic minimum of the two
4286
 * inputs on each cell.  If only one of the two inputs is defined on
4287
 * a given cell, then it is considered to be the minimum.
4288
 */
4289
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmin(
4290
  __isl_take isl_pw_multi_aff *pma1,
4291
  __isl_take isl_pw_multi_aff *pma2)
4292
606
{
4293
606
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4294
606
                &pw_multi_aff_union_lexmin);
4295
606
}
4296
4297
static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
4298
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4299
1
{
4300
1
  return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
4301
1
            &isl_multi_aff_add);
4302
1
}
4303
4304
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
4305
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4306
1
{
4307
1
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4308
1
            &pw_multi_aff_add);
4309
1
}
4310
4311
static __isl_give isl_pw_multi_aff *pw_multi_aff_sub(
4312
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4313
0
{
4314
0
  return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
4315
0
            &isl_multi_aff_sub);
4316
0
}
4317
4318
/* Subtract "pma2" from "pma1" and return the result.
4319
 */
4320
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_sub(
4321
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4322
0
{
4323
0
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4324
0
            &pw_multi_aff_sub);
4325
0
}
4326
4327
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
4328
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4329
805
{
4330
805
  return isl_pw_multi_aff_union_add_(pma1, pma2);
4331
805
}
4332
4333
/* Compute the sum of "upa1" and "upa2" on the union of their domains,
4334
 * with the actual sum on the shared domain and
4335
 * the defined expression on the symmetric difference of the domains.
4336
 */
4337
__isl_give isl_union_pw_aff *isl_union_pw_aff_union_add(
4338
  __isl_take isl_union_pw_aff *upa1, __isl_take isl_union_pw_aff *upa2)
4339
250
{
4340
250
  return isl_union_pw_aff_union_add_(upa1, upa2);
4341
250
}
4342
4343
/* Compute the sum of "upma1" and "upma2" on the union of their domains,
4344
 * with the actual sum on the shared domain and
4345
 * the defined expression on the symmetric difference of the domains.
4346
 */
4347
__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_union_add(
4348
  __isl_take isl_union_pw_multi_aff *upma1,
4349
  __isl_take isl_union_pw_multi_aff *upma2)
4350
128
{
4351
128
  return isl_union_pw_multi_aff_union_add_(upma1, upma2);
4352
128
}
4353
4354
/* Given two piecewise multi-affine expressions A -> B and C -> D,
4355
 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
4356
 */
4357
static __isl_give isl_pw_multi_aff *pw_multi_aff_product(
4358
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4359
1
{
4360
1
  int i, j, n;
4361
1
  isl_space *space;
4362
1
  isl_pw_multi_aff *res;
4363
1
4364
1
  if (!pma1 || !pma2)
4365
0
    goto error;
4366
1
4367
1
  n = pma1->n * pma2->n;
4368
1
  space = isl_space_product(isl_space_copy(pma1->dim),
4369
1
          isl_space_copy(pma2->dim));
4370
1
  res = isl_pw_multi_aff_alloc_size(space, n);
4371
1
4372
3
  for (i = 0; i < pma1->n; 
++i2
) {
4373
4
    for (j = 0; j < pma2->n; 
++j2
) {
4374
2
      isl_set *domain;
4375
2
      isl_multi_aff *ma;
4376
2
4377
2
      domain = isl_set_product(isl_set_copy(pma1->p[i].set),
4378
2
             isl_set_copy(pma2->p[j].set));
4379
2
      ma = isl_multi_aff_product(
4380
2
          isl_multi_aff_copy(pma1->p[i].maff),
4381
2
          isl_multi_aff_copy(pma2->p[j].maff));
4382
2
      res = isl_pw_multi_aff_add_piece(res, domain, ma);
4383
2
    }
4384
2
  }
4385
1
4386
1
  isl_pw_multi_aff_free(pma1);
4387
1
  isl_pw_multi_aff_free(pma2);
4388
1
  return res;
4389
0
error:
4390
0
  isl_pw_multi_aff_free(pma1);
4391
0
  isl_pw_multi_aff_free(pma2);
4392
0
  return NULL;
4393
1
}
4394
4395
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_product(
4396
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4397
1
{
4398
1
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4399
1
            &pw_multi_aff_product);
4400
1
}
4401
4402
/* Construct a map mapping the domain of the piecewise multi-affine expression
4403
 * to its range, with each dimension in the range equated to the
4404
 * corresponding affine expression on its cell.
4405
 *
4406
 * If the domain of "pma" is rational, then so is the constructed "map".
4407
 */
4408
__isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
4409
7.74k
{
4410
7.74k
  int i;
4411
7.74k
  isl_map *map;
4412
7.74k
4413
7.74k
  if (!pma)
4414
0
    return NULL;
4415
7.74k
4416
7.74k
  map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
4417
7.74k
4418
16.0k
  for (i = 0; i < pma->n; 
++i8.28k
) {
4419
8.28k
    isl_bool rational;
4420
8.28k
    isl_multi_aff *maff;
4421
8.28k
    isl_basic_map *bmap;
4422
8.28k
    isl_map *map_i;
4423
8.28k
4424
8.28k
    rational = isl_set_is_rational(pma->p[i].set);
4425
8.28k
    if (rational < 0)
4426
0
      map = isl_map_free(map);
4427
8.28k
    maff = isl_multi_aff_copy(pma->p[i].maff);
4428
8.28k
    bmap = isl_basic_map_from_multi_aff2(maff, rational);
4429
8.28k
    map_i = isl_map_from_basic_map(bmap);
4430
8.28k
    map_i = isl_map_intersect_domain(map_i,
4431
8.28k
            isl_set_copy(pma->p[i].set));
4432
8.28k
    map = isl_map_union_disjoint(map, map_i);
4433
8.28k
  }
4434
7.74k
4435
7.74k
  isl_pw_multi_aff_free(pma);
4436
7.74k
  return map;
4437
7.74k
}
4438
4439
__isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
4440
7
{
4441
7
  if (!pma)
4442
0
    return NULL;
4443
7
4444
7
  if (!isl_space_is_set(pma->dim))
4445
7
    
isl_die0
(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4446
7
      "isl_pw_multi_aff cannot be converted into an isl_set",
4447
7
      goto error);
4448
7
4449
7
  return isl_map_from_pw_multi_aff(pma);
4450
0
error:
4451
0
  isl_pw_multi_aff_free(pma);
4452
0
  return NULL;
4453
7
}
4454
4455
/* Subtract the initial "n" elements in "ma" with coefficients in "c" and
4456
 * denominator "denom".
4457
 * "denom" is allowed to be negative, in which case the actual denominator
4458
 * is -denom and the expressions are added instead.
4459
 */
4460
static __isl_give isl_aff *subtract_initial(__isl_take isl_aff *aff,
4461
  __isl_keep isl_multi_aff *ma, int n, isl_int *c, isl_int denom)
4462
9.89k
{
4463
9.89k
  int i, first;
4464
9.89k
  int sign;
4465
9.89k
  isl_int d;
4466
9.89k
4467
9.89k
  first = isl_seq_first_non_zero(c, n);
4468
9.89k
  if (first == -1)
4469
9.88k
    return aff;
4470
3
4471
3
  sign = isl_int_sgn(denom);
4472
3
  isl_int_init(d);
4473
3
  isl_int_abs(d, denom);
4474
6
  for (i = first; i < n; 
++i3
) {
4475
3
    isl_aff *aff_i;
4476
3
4477
3
    if (isl_int_is_zero(c[i]))
4478
3
      
continue0
;
4479
3
    aff_i = isl_multi_aff_get_aff(ma, i);
4480
3
    aff_i = isl_aff_scale(aff_i, c[i]);
4481
3
    aff_i = isl_aff_scale_down(aff_i, d);
4482
3
    if (sign >= 0)
4483
2
      aff = isl_aff_sub(aff, aff_i);
4484
1
    else
4485
1
      aff = isl_aff_add(aff, aff_i);
4486
3
  }
4487
3
  isl_int_clear(d);
4488
9.89k
4489
9.89k
  return aff;
4490
9.89k
}
4491
4492
/* Extract an affine expression that expresses the output dimension "pos"
4493
 * of "bmap" in terms of the parameters and input dimensions from
4494
 * equality "eq".
4495
 * Note that this expression may involve integer divisions defined
4496
 * in terms of parameters and input dimensions.
4497
 * The equality may also involve references to earlier (but not later)
4498
 * output dimensions.  These are replaced by the corresponding elements
4499
 * in "ma".
4500
 *
4501
 * If the equality is of the form
4502
 *
4503
 *  f(i) + h(j) + a x + g(i) = 0,
4504
 *
4505
 * with f(i) a linear combinations of the parameters and input dimensions,
4506
 * g(i) a linear combination of integer divisions defined in terms of the same
4507
 * and h(j) a linear combinations of earlier output dimensions,
4508
 * then the affine expression is
4509
 *
4510
 *  (-f(i) - g(i))/a - h(j)/a
4511
 *
4512
 * If the equality is of the form
4513
 *
4514
 *  f(i) + h(j) - a x + g(i) = 0,
4515
 *
4516
 * then the affine expression is
4517
 *
4518
 *  (f(i) + g(i))/a - h(j)/(-a)
4519
 *
4520
 *
4521
 * If "div" refers to an integer division (i.e., it is smaller than
4522
 * the number of integer divisions), then the equality constraint
4523
 * does involve an integer division (the one at position "div") that
4524
 * is defined in terms of output dimensions.  However, this integer
4525
 * division can be eliminated by exploiting a pair of constraints
4526
 * x >= l and x <= l + n, with n smaller than the coefficient of "div"
4527
 * in the equality constraint.  "ineq" refers to inequality x >= l, i.e.,
4528
 * -l + x >= 0.
4529
 * In particular, let
4530
 *
4531
 *  x = e(i) + m floor(...)
4532
 *
4533
 * with e(i) the expression derived above and floor(...) the integer
4534
 * division involving output dimensions.
4535
 * From
4536
 *
4537
 *  l <= x <= l + n,
4538
 *
4539
 * we have
4540
 *
4541
 *  0 <= x - l <= n
4542
 *
4543
 * This means
4544
 *
4545
 *  e(i) + m floor(...) - l = (e(i) + m floor(...) - l) mod m
4546
 *                          = (e(i) - l) mod m
4547
 *
4548
 * Therefore,
4549
 *
4550
 *  x - l = (e(i) - l) mod m
4551
 *
4552
 * or
4553
 *
4554
 *  x = ((e(i) - l) mod m) + l
4555
 *
4556
 * The variable "shift" below contains the expression -l, which may
4557
 * also involve a linear combination of earlier output dimensions.
4558
 */
4559
static __isl_give isl_aff *extract_aff_from_equality(
4560
  __isl_keep isl_basic_map *bmap, int pos, int eq, int div, int ineq,
4561
  __isl_keep isl_multi_aff *ma)
4562
9.82k
{
4563
9.82k
  unsigned o_out;
4564
9.82k
  unsigned n_div, n_out;
4565
9.82k
  isl_ctx *ctx;
4566
9.82k
  isl_local_space *ls;
4567
9.82k
  isl_aff *aff, *shift;
4568
9.82k
  isl_val *mod;
4569
9.82k
4570
9.82k
  ctx = isl_basic_map_get_ctx(bmap);
4571
9.82k
  ls = isl_basic_map_get_local_space(bmap);
4572
9.82k
  ls = isl_local_space_domain(ls);
4573
9.82k
  aff = isl_aff_alloc(isl_local_space_copy(ls));
4574
9.82k
  if (!aff)
4575
0
    goto error;
4576
9.82k
  o_out = isl_basic_map_offset(bmap, isl_dim_out);
4577
9.82k
  n_out = isl_basic_map_dim(bmap, isl_dim_out);
4578
9.82k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
4579
9.82k
  if (isl_int_is_neg(bmap->eq[eq][o_out + pos])) {
4580
305
    isl_seq_cpy(aff->v->el + 1, bmap->eq[eq], o_out);
4581
305
    isl_seq_cpy(aff->v->el + 1 + o_out,
4582
305
          bmap->eq[eq] + o_out + n_out, n_div);
4583
9.52k
  } else {
4584
9.52k
    isl_seq_neg(aff->v->el + 1, bmap->eq[eq], o_out);
4585
9.52k
    isl_seq_neg(aff->v->el + 1 + o_out,
4586
9.52k
          bmap->eq[eq] + o_out + n_out, n_div);
4587
9.52k
  }
4588
9.82k
  if (div < n_div)
4589
9.82k
    
isl_int_set_si64
(aff->v->el[1 + o_out + div], 0);
4590
9.82k
  isl_int_abs(aff->v->el[0], bmap->eq[eq][o_out + pos]);
4591
9.82k
  aff = subtract_initial(aff, ma, pos, bmap->eq[eq] + o_out,
4592
9.82k
          bmap->eq[eq][o_out + pos]);
4593
9.82k
  if (div < n_div) {
4594
64
    shift = isl_aff_alloc(isl_local_space_copy(ls));
4595
64
    if (!shift)
4596
0
      goto error;
4597
64
    isl_seq_cpy(shift->v->el + 1, bmap->ineq[ineq], o_out);
4598
64
    isl_seq_cpy(shift->v->el + 1 + o_out,
4599
64
          bmap->ineq[ineq] + o_out + n_out, n_div);
4600
64
    isl_int_set_si(shift->v->el[0], 1);
4601
64
    shift = subtract_initial(shift, ma, pos,
4602
64
          bmap->ineq[ineq] + o_out, ctx->negone);
4603
64
    aff = isl_aff_add(aff, isl_aff_copy(shift));
4604
64
    mod = isl_val_int_from_isl_int(ctx,
4605
64
              bmap->eq[eq][o_out + n_out + div]);
4606
64
    mod = isl_val_abs(mod);
4607
64
    aff = isl_aff_mod_val(aff, mod);
4608
64
    aff = isl_aff_sub(aff, shift);
4609
64
  }
4610
9.82k
4611
9.82k
  isl_local_space_free(ls);
4612
9.82k
  return aff;
4613
0
error:
4614
0
  isl_local_space_free(ls);
4615
0
  isl_aff_free(aff);
4616
0
  return NULL;
4617
9.82k
}
4618
4619
/* Given a basic map with output dimensions defined
4620
 * in terms of the parameters input dimensions and earlier
4621
 * output dimensions using an equality (and possibly a pair on inequalities),
4622
 * extract an isl_aff that expresses output dimension "pos" in terms
4623
 * of the parameters and input dimensions.
4624
 * Note that this expression may involve integer divisions defined
4625
 * in terms of parameters and input dimensions.
4626
 * "ma" contains the expressions corresponding to earlier output dimensions.
4627
 *
4628
 * This function shares some similarities with
4629
 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
4630
 */
4631
static __isl_give isl_aff *extract_isl_aff_from_basic_map(
4632
  __isl_keep isl_basic_map *bmap, int pos, __isl_keep isl_multi_aff *ma)
4633
9.82k
{
4634
9.82k
  int eq, div, ineq;
4635
9.82k
  isl_aff *aff;
4636
9.82k
4637
9.82k
  if (!bmap)
4638
0
    return NULL;
4639
9.82k
  eq = isl_basic_map_output_defining_equality(bmap, pos, &div, &ineq);
4640
9.82k
  if (eq >= bmap->n_eq)
4641
9.82k
    
isl_die0
(isl_basic_map_get_ctx(bmap), isl_error_invalid,
4642
9.82k
      "unable to find suitable equality", return NULL);
4643
9.82k
  aff = extract_aff_from_equality(bmap, pos, eq, div, ineq, ma);
4644
9.82k
4645
9.82k
  aff = isl_aff_remove_unused_divs(aff);
4646
9.82k
  return aff;
4647
9.82k
}
4648
4649
/* Given a basic map where each output dimension is defined
4650
 * in terms of the parameters and input dimensions using an equality,
4651
 * extract an isl_multi_aff that expresses the output dimensions in terms
4652
 * of the parameters and input dimensions.
4653
 */
4654
static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
4655
  __isl_take isl_basic_map *bmap)
4656
6.42k
{
4657
6.42k
  int i;
4658
6.42k
  unsigned n_out;
4659
6.42k
  isl_multi_aff *ma;
4660
6.42k
4661
6.42k
  if (!bmap)
4662
0
    return NULL;
4663
6.42k
4664
6.42k
  ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
4665
6.42k
  n_out = isl_basic_map_dim(bmap, isl_dim_out);
4666
6.42k
4667
16.2k
  for (i = 0; i < n_out; 
++i9.82k
) {
4668
9.82k
    isl_aff *aff;
4669
9.82k
4670
9.82k
    aff = extract_isl_aff_from_basic_map(bmap, i, ma);
4671
9.82k
    ma = isl_multi_aff_set_aff(ma, i, aff);
4672
9.82k
  }
4673
6.42k
4674
6.42k
  isl_basic_map_free(bmap);
4675
6.42k
4676
6.42k
  return ma;
4677
6.42k
}
4678
4679
/* Given a basic set where each set dimension is defined
4680
 * in terms of the parameters using an equality,
4681
 * extract an isl_multi_aff that expresses the set dimensions in terms
4682
 * of the parameters.
4683
 */
4684
__isl_give isl_multi_aff *isl_multi_aff_from_basic_set_equalities(
4685
  __isl_take isl_basic_set *bset)
4686
9
{
4687
9
  return extract_isl_multi_aff_from_basic_map(bset);
4688
9
}
4689
4690
/* Create an isl_pw_multi_aff that is equivalent to
4691
 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
4692
 * The given basic map is such that each output dimension is defined
4693
 * in terms of the parameters and input dimensions using an equality.
4694
 *
4695
 * Since some applications expect the result of isl_pw_multi_aff_from_map
4696
 * to only contain integer affine expressions, we compute the floor
4697
 * of the expression before returning.
4698
 *
4699
 * Remove all constraints involving local variables without
4700
 * an explicit representation (resulting in the removal of those
4701
 * local variables) prior to the actual extraction to ensure
4702
 * that the local spaces in which the resulting affine expressions
4703
 * are created do not contain any unknown local variables.
4704
 * Removing such constraints is safe because constraints involving
4705
 * unknown local variables are not used to determine whether
4706
 * a basic map is obviously single-valued.
4707
 */
4708
static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
4709
  __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
4710
6.41k
{
4711
6.41k
  isl_multi_aff *ma;
4712
6.41k
4713
6.41k
  bmap = isl_basic_map_drop_constraint_involving_unknown_divs(bmap);
4714
6.41k
  ma = extract_isl_multi_aff_from_basic_map(bmap);
4715
6.41k
  ma = isl_multi_aff_floor(ma);
4716
6.41k
  return isl_pw_multi_aff_alloc(domain, ma);
4717
6.41k
}
4718
4719
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4720
 * This obviously only works if the input "map" is single-valued.
4721
 * If so, we compute the lexicographic minimum of the image in the form
4722
 * of an isl_pw_multi_aff.  Since the image is unique, it is equal
4723
 * to its lexicographic minimum.
4724
 * If the input is not single-valued, we produce an error.
4725
 */
4726
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_base(
4727
  __isl_take isl_map *map)
4728
17
{
4729
17
  int i;
4730
17
  int sv;
4731
17
  isl_pw_multi_aff *pma;
4732
17
4733
17
  sv = isl_map_is_single_valued(map);
4734
17
  if (sv < 0)
4735
0
    goto error;
4736
17
  if (!sv)
4737
17
    
isl_die0
(isl_map_get_ctx(map), isl_error_invalid,
4738
17
      "map is not single-valued", goto error);
4739
17
  map = isl_map_make_disjoint(map);
4740
17
  if (!map)
4741
0
    return NULL;
4742
17
4743
17
  pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
4744
17
4745
78
  for (i = 0; i < map->n; 
++i61
) {
4746
61
    isl_pw_multi_aff *pma_i;
4747
61
    isl_basic_map *bmap;
4748
61
    bmap = isl_basic_map_copy(map->p[i]);
4749
61
    pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
4750
61
    pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
4751
61
  }
4752
17
4753
17
  isl_map_free(map);
4754
17
  return pma;
4755
0
error:
4756
0
  isl_map_free(map);
4757
0
  return NULL;
4758
17
}
4759
4760
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4761
 * taking into account that the output dimension at position "d"
4762
 * can be represented as
4763
 *
4764
 *  x = floor((e(...) + c1) / m)
4765
 *
4766
 * given that constraint "i" is of the form
4767
 *
4768
 *  e(...) + c1 - m x >= 0
4769
 *
4770
 *
4771
 * Let "map" be of the form
4772
 *
4773
 *  A -> B
4774
 *
4775
 * We construct a mapping
4776
 *
4777
 *  A -> [A -> x = floor(...)]
4778
 *
4779
 * apply that to the map, obtaining
4780
 *
4781
 *  [A -> x = floor(...)] -> B
4782
 *
4783
 * and equate dimension "d" to x.
4784
 * We then compute a isl_pw_multi_aff representation of the resulting map
4785
 * and plug in the mapping above.
4786
 */
4787
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_div(
4788
  __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i)
4789
14
{
4790
14
  isl_ctx *ctx;
4791
14
  isl_space *space;
4792
14
  isl_local_space *ls;
4793
14
  isl_multi_aff *ma;
4794
14
  isl_aff *aff;
4795
14
  isl_vec *v;
4796
14
  isl_map *insert;
4797
14
  int offset;
4798
14
  int n;
4799
14
  int n_in;
4800
14
  isl_pw_multi_aff *pma;
4801
14
  isl_bool is_set;
4802
14
4803
14
  is_set = isl_map_is_set(map);
4804
14
  if (is_set < 0)
4805
0
    goto error;
4806
14
4807
14
  offset = isl_basic_map_offset(hull, isl_dim_out);
4808
14
  ctx = isl_map_get_ctx(map);
4809
14
  space = isl_space_domain(isl_map_get_space(map));
4810
14
  n_in = isl_space_dim(space, isl_dim_set);
4811
14
  n = isl_space_dim(space, isl_dim_all);
4812
14
4813
14
  v = isl_vec_alloc(ctx, 1 + 1 + n);
4814
14
  if (v) {
4815
14
    isl_int_neg(v->el[0], hull->ineq[i][offset + d]);
4816
14
    isl_seq_cpy(v->el + 1, hull->ineq[i], 1 + n);
4817
14
  }
4818
14
  isl_basic_map_free(hull);
4819
14
4820
14
  ls = isl_local_space_from_space(isl_space_copy(space));
4821
14
  aff = isl_aff_alloc_vec(ls, v);
4822
14
  aff = isl_aff_floor(aff);
4823
14
  if (is_set) {
4824
1
    isl_space_free(space);
4825
1
    ma = isl_multi_aff_from_aff(aff);
4826
13
  } else {
4827
13
    ma = isl_multi_aff_identity(isl_space_map_from_set(space));
4828
13
    ma = isl_multi_aff_range_product(ma,
4829
13
            isl_multi_aff_from_aff(aff));
4830
13
  }
4831
14
4832
14
  insert = isl_map_from_multi_aff(isl_multi_aff_copy(ma));
4833
14
  map = isl_map_apply_domain(map, insert);
4834
14
  map = isl_map_equate(map, isl_dim_in, n_in, isl_dim_out, d);
4835
14
  pma = isl_pw_multi_aff_from_map(map);
4836
14
  pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma);
4837
14
4838
14
  return pma;
4839
0
error:
4840
0
  isl_map_free(map);
4841
0
  isl_basic_map_free(hull);
4842
0
  return NULL;
4843
14
}
4844
4845
/* Is constraint "c" of the form
4846
 *
4847
 *  e(...) + c1 - m x >= 0
4848
 *
4849
 * or
4850
 *
4851
 *  -e(...) + c2 + m x >= 0
4852
 *
4853
 * where m > 1 and e only depends on parameters and input dimemnsions?
4854
 *
4855
 * "offset" is the offset of the output dimensions
4856
 * "pos" is the position of output dimension x.
4857
 */
4858
static int is_potential_div_constraint(isl_int *c, int offset, int d, int total)
4859
137
{
4860
137
  if (isl_int_is_zero(c[offset + d]))
4861
137
    
return 0100
;
4862
37
  if (isl_int_is_one(c[offset + d]))
4863
37
    
return 016
;
4864
21
  if (isl_int_is_negone(c[offset + d]))
4865
21
    
return 07
;
4866
14
  if (isl_seq_first_non_zero(c + offset, d) != -1)
4867
0
    return 0;
4868
14
  if (isl_seq_first_non_zero(c + offset + d + 1,
4869
14
            total - (offset + d + 1)) != -1)
4870
0
    return 0;
4871
14
  return 1;
4872
14
}
4873
4874
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4875
 *
4876
 * As a special case, we first check if there is any pair of constraints,
4877
 * shared by all the basic maps in "map" that force a given dimension
4878
 * to be equal to the floor of some affine combination of the input dimensions.
4879
 *
4880
 * In particular, if we can find two constraints
4881
 *
4882
 *  e(...) + c1 - m x >= 0    i.e.,   m x <= e(...) + c1
4883
 *
4884
 * and
4885
 *
4886
 *  -e(...) + c2 + m x >= 0   i.e.,   m x >= e(...) - c2
4887
 *
4888
 * where m > 1 and e only depends on parameters and input dimemnsions,
4889
 * and such that
4890
 *
4891
 *  c1 + c2 < m     i.e.,   -c2 >= c1 - (m - 1)
4892
 *
4893
 * then we know that we can take
4894
 *
4895
 *  x = floor((e(...) + c1) / m)
4896
 *
4897
 * without having to perform any computation.
4898
 *
4899
 * Note that we know that
4900
 *
4901
 *  c1 + c2 >= 1
4902
 *
4903
 * If c1 + c2 were 0, then we would have detected an equality during
4904
 * simplification.  If c1 + c2 were negative, then we would have detected
4905
 * a contradiction.
4906
 */
4907
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_div(
4908
  __isl_take isl_map *map)
4909
31
{
4910
31
  int d, dim;
4911
31
  int i, j, n;
4912
31
  int offset, total;
4913
31
  isl_int sum;
4914
31
  isl_basic_map *hull;
4915
31
4916
31
  hull = isl_map_unshifted_simple_hull(isl_map_copy(map));
4917
31
  if (!hull)
4918
0
    goto error;
4919
31
4920
31
  isl_int_init(sum);
4921
31
  dim = isl_map_dim(map, isl_dim_out);
4922
31
  offset = isl_basic_map_offset(hull, isl_dim_out);
4923
31
  total = 1 + isl_basic_map_total_dim(hull);
4924
31
  n = hull->n_ineq;
4925
69
  for (d = 0; d < dim; 
++d38
) {
4926
175
    for (i = 0; i < n; 
++i123
) {
4927
137
      if (!is_potential_div_constraint(hull->ineq[i],
4928
137
              offset, d, total))
4929
123
        continue;
4930
19
      
for (j = i + 1; 14
j < n;
++j5
) {
4931
19
        if (!isl_seq_is_neg(hull->ineq[i] + 1,
4932
19
            hull->ineq[j] + 1, total - 1))
4933
5
          continue;
4934
14
        isl_int_add(sum, hull->ineq[i][0],
4935
14
            hull->ineq[j][0]);
4936
14
        if (isl_int_abs_lt(sum,
4937
14
                hull->ineq[i][offset + d]))
4938
14
          break;
4939
19
4940
19
      }
4941
14
      if (j >= n)
4942
0
        continue;
4943
14
      isl_int_clear(sum);
4944
14
      if (isl_int_is_pos(hull->ineq[j][offset + d]))
4945
14
        
j = i1
;
4946
137
      return pw_multi_aff_from_map_div(map, hull, d, j);
4947
137
    }
4948
52
  }
4949
31
  
isl_int_clear17
(sum);
4950
17
  isl_basic_map_free(hull);
4951
17
  return pw_multi_aff_from_map_base(map);
4952
0
error:
4953
0
  isl_map_free(map);
4954
0
  isl_basic_map_free(hull);
4955
0
  return NULL;
4956
31
}
4957
4958
/* Given an affine expression
4959
 *
4960
 *  [A -> B] -> f(A,B)
4961
 *
4962
 * construct an isl_multi_aff
4963
 *
4964
 *  [A -> B] -> B'
4965
 *
4966
 * such that dimension "d" in B' is set to "aff" and the remaining
4967
 * dimensions are set equal to the corresponding dimensions in B.
4968
 * "n_in" is the dimension of the space A.
4969
 * "n_out" is the dimension of the space B.
4970
 *
4971
 * If "is_set" is set, then the affine expression is of the form
4972
 *
4973
 *  [B] -> f(B)
4974
 *
4975
 * and we construct an isl_multi_aff
4976
 *
4977
 *  B -> B'
4978
 */
4979
static __isl_give isl_multi_aff *range_map(__isl_take isl_aff *aff, int d,
4980
  unsigned n_in, unsigned n_out, int is_set)
4981
4
{
4982
4
  int i;
4983
4
  isl_multi_aff *ma;
4984
4
  isl_space *space, *space2;
4985
4
  isl_local_space *ls;
4986
4
4987
4
  space = isl_aff_get_domain_space(aff);
4988
4
  ls = isl_local_space_from_space(isl_space_copy(space));
4989
4
  space2 = isl_space_copy(space);
4990
4
  if (!is_set)
4991
4
    space2 = isl_space_range(isl_space_unwrap(space2));
4992
4
  space = isl_space_map_from_domain_and_range(space, space2);
4993
4
  ma = isl_multi_aff_alloc(space);
4994
4
  ma = isl_multi_aff_set_aff(ma, d, aff);
4995
4
4996
21
  for (i = 0; i < n_out; 
++i17
) {
4997
17
    if (i == d)
4998
4
      continue;
4999
13
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
5000
13
            isl_dim_set, n_in + i);
5001
13
    ma = isl_multi_aff_set_aff(ma, i, aff);
5002
13
  }
5003
4
5004
4
  isl_local_space_free(ls);
5005
4
5006
4
  return ma;
5007
4
}
5008
5009
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
5010
 * taking into account that the dimension at position "d" can be written as
5011
 *
5012
 *  x = m a + f(..)           (1)
5013
 *
5014
 * where m is equal to "gcd".
5015
 * "i" is the index of the equality in "hull" that defines f(..).
5016
 * In particular, the equality is of the form
5017
 *
5018
 *  f(..) - x + m g(existentials) = 0
5019
 *
5020
 * or
5021
 *
5022
 *  -f(..) + x + m g(existentials) = 0
5023
 *
5024
 * We basically plug (1) into "map", resulting in a map with "a"
5025
 * in the range instead of "x".  The corresponding isl_pw_multi_aff
5026
 * defining "a" is then plugged back into (1) to obtain a definition for "x".
5027
 *
5028
 * Specifically, given the input map
5029
 *
5030
 *  A -> B
5031
 *
5032
 * We first wrap it into a set
5033
 *
5034
 *  [A -> B]
5035
 *
5036
 * and define (1) on top of the corresponding space, resulting in "aff".
5037
 * We use this to create an isl_multi_aff that maps the output position "d"
5038
 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
5039
 * We plug this into the wrapped map, unwrap the result and compute the
5040
 * corresponding isl_pw_multi_aff.
5041
 * The result is an expression
5042
 *
5043
 *  A -> T(A)
5044
 *
5045
 * We adjust that to
5046
 *
5047
 *  A -> [A -> T(A)]
5048
 *
5049
 * so that we can plug that into "aff", after extending the latter to
5050
 * a mapping
5051
 *
5052
 *  [A -> B] -> B'
5053
 *
5054
 *
5055
 * If "map" is actually a set, then there is no "A" space, meaning
5056
 * that we do not need to perform any wrapping, and that the result
5057
 * of the recursive call is of the form
5058
 *
5059
 *  [T]
5060
 *
5061
 * which is plugged into a mapping of the form
5062
 *
5063
 *  B -> B'
5064
 */
5065
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_stride(
5066
  __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i,
5067
  isl_int gcd)
5068
4
{
5069
4
  isl_set *set;
5070
4
  isl_space *space;
5071
4
  isl_local_space *ls;
5072
4
  isl_aff *aff;
5073
4
  isl_multi_aff *ma;
5074
4
  isl_pw_multi_aff *pma, *id;
5075
4
  unsigned n_in;
5076
4
  unsigned o_out;
5077
4
  unsigned n_out;
5078
4
  isl_bool is_set;
5079
4
5080
4
  is_set = isl_map_is_set(map);
5081
4
  if (is_set < 0)
5082
0
    goto error;
5083
4
5084
4
  n_in = isl_basic_map_dim(hull, isl_dim_in);
5085
4
  n_out = isl_basic_map_dim(hull, isl_dim_out);
5086
4
  o_out = isl_basic_map_offset(hull, isl_dim_out);
5087
4
5088
4
  if (is_set)
5089
0
    set = map;
5090
4
  else
5091
4
    set = isl_map_wrap(map);
5092
4
  space = isl_space_map_from_set(isl_set_get_space(set));
5093
4
  ma = isl_multi_aff_identity(space);
5094
4
  ls = isl_local_space_from_space(isl_set_get_space(set));
5095
4
  aff = isl_aff_alloc(ls);
5096
4
  if (aff) {
5097
4
    isl_int_set_si(aff->v->el[0], 1);
5098
4
    if (isl_int_is_one(hull->eq[i][o_out + d]))
5099
4
      isl_seq_neg(aff->v->el + 1, hull->eq[i],
5100
0
            aff->v->size - 1);
5101
4
    else
5102
4
      isl_seq_cpy(aff->v->el + 1, hull->eq[i],
5103
4
            aff->v->size - 1);
5104
4
    isl_int_set(aff->v->el[1 + o_out + d], gcd);
5105
4
  }
5106
4
  ma = isl_multi_aff_set_aff(ma, n_in + d, isl_aff_copy(aff));
5107
4
  set = isl_set_preimage_multi_aff(set, ma);
5108
4
5109
4
  ma = range_map(aff, d, n_in, n_out, is_set);
5110
4
5111
4
  if (is_set)
5112
0
    map = set;
5113
4
  else
5114
4
    map = isl_set_unwrap(set);
5115
4
  pma = isl_pw_multi_aff_from_map(map);
5116
4
5117
4
  if (!is_set) {
5118
4
    space = isl_pw_multi_aff_get_domain_space(pma);
5119
4
    space = isl_space_map_from_set(space);
5120
4
    id = isl_pw_multi_aff_identity(space);
5121
4
    pma = isl_pw_multi_aff_range_product(id, pma);
5122
4
  }
5123
4
  id = isl_pw_multi_aff_from_multi_aff(ma);
5124
4
  pma = isl_pw_multi_aff_pullback_pw_multi_aff(id, pma);
5125
4
5126
4
  isl_basic_map_free(hull);
5127
4
  return pma;
5128
0
error:
5129
0
  isl_map_free(map);
5130
0
  isl_basic_map_free(hull);
5131
0
  return NULL;
5132
4
}
5133
5134
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
5135
 * "hull" contains the equalities valid for "map".
5136
 *
5137
 * Check if any of the output dimensions is "strided".
5138
 * That is, we check if it can be written as
5139
 *
5140
 *  x = m a + f(..)
5141
 *
5142
 * with m greater than 1, a some combination of existentially quantified
5143
 * variables and f an expression in the parameters and input dimensions.
5144
 * If so, we remove the stride in pw_multi_aff_from_map_stride.
5145
 *
5146
 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
5147
 * special case.
5148
 */
5149
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_strides(
5150
  __isl_take isl_map *map, __isl_take isl_basic_map *hull)
5151
35
{
5152
35
  int i, j;
5153
35
  unsigned n_out;
5154
35
  unsigned o_out;
5155
35
  unsigned n_div;
5156
35
  unsigned o_div;
5157
35
  isl_int gcd;
5158
35
5159
35
  n_div = isl_basic_map_dim(hull, isl_dim_div);
5160
35
  o_div = isl_basic_map_offset(hull, isl_dim_div);
5161
35
5162
35
  if (n_div == 0) {
5163
26
    isl_basic_map_free(hull);
5164
26
    return pw_multi_aff_from_map_check_div(map);
5165
26
  }
5166
9
5167
9
  isl_int_init(gcd);
5168
9
5169
9
  n_out = isl_basic_map_dim(hull, isl_dim_out);
5170
9
  o_out = isl_basic_map_offset(hull, isl_dim_out);
5171
9
5172
29
  for (i = 0; i < n_out; 
++i20
) {
5173
103
    for (j = 0; j < hull->n_eq; 
++j79
) {
5174
83
      isl_int *eq = hull->eq[j];
5175
83
     &n