Coverage Report

Created: 2017-03-27 23:01

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
212k
{
56
212k
  isl_aff *aff;
57
212k
58
212k
  if (
!ls || 212k
!v212k
)
59
0
    goto error;
60
212k
61
212k
  
aff = 212k
isl_calloc_type212k
(v->ctx, struct isl_aff);
62
212k
  if (!aff)
63
0
    goto error;
64
212k
65
212k
  aff->ref = 1;
66
212k
  aff->ls = ls;
67
212k
  aff->v = v;
68
212k
69
212k
  return aff;
70
0
error:
71
0
  isl_local_space_free(ls);
72
0
  isl_vec_free(v);
73
0
  return NULL;
74
212k
}
75
76
__isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
77
100k
{
78
100k
  isl_ctx *ctx;
79
100k
  isl_vec *v;
80
100k
  unsigned total;
81
100k
82
100k
  if (!ls)
83
0
    return NULL;
84
100k
85
100k
  ctx = isl_local_space_get_ctx(ls);
86
100k
  if (!isl_local_space_divs_known(ls))
87
0
    isl_die(ctx, isl_error_invalid, "local space has unknown divs",
88
100k
      goto error);
89
100k
  
if (100k
!isl_local_space_is_set(ls)100k
)
90
0
    isl_die(ctx, isl_error_invalid,
91
100k
      "domain of affine expression should be a set",
92
100k
      goto error);
93
100k
94
100k
  total = isl_local_space_dim(ls, isl_dim_all);
95
100k
  v = isl_vec_alloc(ctx, 1 + 1 + total);
96
100k
  return isl_aff_alloc_vec(ls, v);
97
0
error:
98
0
  isl_local_space_free(ls);
99
0
  return NULL;
100
100k
}
101
102
__isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
103
48.1k
{
104
48.1k
  isl_aff *aff;
105
48.1k
106
48.1k
  aff = isl_aff_alloc(ls);
107
48.1k
  if (!aff)
108
0
    return NULL;
109
48.1k
110
48.1k
  
isl_int_set_si48.1k
(aff->v->el[0], 1);48.1k
111
48.1k
  isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
112
48.1k
113
48.1k
  return aff;
114
48.1k
}
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
481
{
121
481
  return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
122
481
}
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
89
{
129
89
  isl_aff *aff;
130
89
131
89
  aff = isl_aff_alloc(ls);
132
89
  if (!aff)
133
0
    return NULL;
134
89
135
89
  isl_seq_clr(aff->v->el, aff->v->size);
136
89
137
89
  return aff;
138
89
}
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
21.0k
{
154
21.0k
  isl_aff *aff;
155
21.0k
156
21.0k
  if (
!ls || 21.0k
!val21.0k
)
157
0
    goto error;
158
21.0k
  
if (21.0k
!isl_val_is_rat(val)21.0k
)
159
0
    isl_die(isl_val_get_ctx(val), isl_error_invalid,
160
21.0k
      "expecting rational value", goto error);
161
21.0k
162
21.0k
  aff = isl_aff_alloc(isl_local_space_copy(ls));
163
21.0k
  if (!aff)
164
0
    goto error;
165
21.0k
166
21.0k
  isl_seq_clr(aff->v->el + 2, aff->v->size - 2);
167
21.0k
  isl_int_set(aff->v->el[1], val->n);
168
21.0k
  isl_int_set(aff->v->el[0], val->d);
169
21.0k
170
21.0k
  isl_local_space_free(ls);
171
21.0k
  isl_val_free(val);
172
21.0k
  return aff;
173
0
error:
174
0
  isl_local_space_free(ls);
175
0
  isl_val_free(val);
176
0
  return NULL;
177
21.0k
}
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
10.1k
{
185
10.1k
  isl_space *space;
186
10.1k
  isl_aff *aff;
187
10.1k
188
10.1k
  if (!ls)
189
0
    return NULL;
190
10.1k
191
10.1k
  space = isl_local_space_get_space(ls);
192
10.1k
  if (!space)
193
0
    goto error;
194
10.1k
  
if (10.1k
isl_space_is_map(space)10.1k
)
195
0
    isl_die(isl_space_get_ctx(space), isl_error_invalid,
196
10.1k
      "expecting (parameter) set space", goto error);
197
10.1k
  
if (10.1k
pos >= isl_local_space_dim(ls, type)10.1k
)
198
0
    isl_die(isl_space_get_ctx(space), isl_error_invalid,
199
10.1k
      "position out of bounds", goto error);
200
10.1k
201
10.1k
  isl_space_free(space);
202
10.1k
  aff = isl_aff_alloc(ls);
203
10.1k
  if (!aff)
204
0
    return NULL;
205
10.1k
206
10.1k
  pos += isl_local_space_offset(aff->ls, type);
207
10.1k
208
10.1k
  isl_int_set_si(aff->v->el[0], 1);
209
10.1k
  isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
210
10.1k
  isl_int_set_si(aff->v->el[1 + pos], 1);
211
10.1k
212
10.1k
  return aff;
213
0
error:
214
0
  isl_local_space_free(ls);
215
0
  isl_space_free(space);
216
0
  return NULL;
217
10.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
466
{
225
466
  return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, type, pos));
226
466
}
227
228
__isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
229
601k
{
230
601k
  if (!aff)
231
0
    return NULL;
232
601k
233
601k
  aff->ref++;
234
601k
  return aff;
235
601k
}
236
237
__isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
238
111k
{
239
111k
  if (!aff)
240
0
    return NULL;
241
111k
242
111k
  return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
243
111k
         isl_vec_copy(aff->v));
244
111k
}
245
246
__isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
247
228k
{
248
228k
  if (!aff)
249
0
    return NULL;
250
228k
251
228k
  
if (228k
aff->ref == 1228k
)
252
116k
    return aff;
253
111k
  aff->ref--;
254
111k
  return isl_aff_dup(aff);
255
228k
}
256
257
__isl_null isl_aff *isl_aff_free(__isl_take isl_aff *aff)
258
1.07M
{
259
1.07M
  if (!aff)
260
376k
    return NULL;
261
1.07M
262
702k
  
if (702k
--aff->ref > 0702k
)
263
489k
    return NULL;
264
702k
265
212k
  isl_local_space_free(aff->ls);
266
212k
  isl_vec_free(aff->v);
267
212k
268
212k
  free(aff);
269
212k
270
212k
  return NULL;
271
702k
}
272
273
isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
274
677k
{
275
677k
  return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
276
677k
}
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 = 0
isl_hash_init0
();
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
199k
{
301
199k
  if (!aff)
302
0
    return 0;
303
199k
  
if (199k
type == isl_dim_out199k
)
304
0
    return 1;
305
199k
  
if (199k
type == isl_dim_in199k
)
306
13.1k
    type = isl_dim_set;
307
199k
  return isl_local_space_dim(aff->ls, type);
308
199k
}
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 (0
type == isl_dim_out0
)
320
0
    return -1;
321
0
  
if (0
type == isl_dim_in0
)
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
808k
{
328
808k
  return aff ? isl_local_space_get_space(aff->ls) : NULL;
329
808k
}
330
331
__isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
332
242k
{
333
242k
  isl_space *space;
334
242k
  if (!aff)
335
0
    return NULL;
336
242k
  space = isl_local_space_get_space(aff->ls);
337
242k
  space = isl_space_from_domain(space);
338
242k
  space = isl_space_add_dims(space, isl_dim_out, 1);
339
242k
  return space;
340
242k
}
341
342
__isl_give isl_local_space *isl_aff_get_domain_local_space(
343
  __isl_keep isl_aff *aff)
344
54.7k
{
345
54.7k
  return aff ? isl_local_space_copy(aff->ls) : NULL;
346
54.7k
}
347
348
__isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
349
29.0k
{
350
29.0k
  isl_local_space *ls;
351
29.0k
  if (!aff)
352
0
    return NULL;
353
29.0k
  ls = isl_local_space_copy(aff->ls);
354
29.0k
  ls = isl_local_space_from_domain(ls);
355
29.0k
  ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
356
29.0k
  return ls;
357
29.0k
}
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 (0
type == isl_dim_out0
)
368
0
    return NULL;
369
0
  
if (0
type == isl_dim_in0
)
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
40.8k
{
377
40.8k
  aff = isl_aff_cow(aff);
378
40.8k
  if (
!aff || 40.8k
!dim40.8k
)
379
0
    goto error;
380
40.8k
381
40.8k
  aff->ls = isl_local_space_reset_space(aff->ls, dim);
382
40.8k
  if (!aff->ls)
383
0
    return isl_aff_free(aff);
384
40.8k
385
40.8k
  return aff;
386
0
error:
387
0
  isl_aff_free(aff);
388
0
  isl_space_free(dim);
389
0
  return NULL;
390
40.8k
}
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
31.9k
{
399
31.9k
  isl_space_free(space);
400
31.9k
  return isl_aff_reset_domain_space(aff, domain);
401
31.9k
}
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
7.62k
{
411
7.62k
  isl_vec *res;
412
7.62k
  int i;
413
7.62k
414
7.62k
  if (
!vec || 7.62k
!r7.62k
)
415
0
    goto error;
416
7.62k
417
7.62k
  res = isl_vec_alloc(vec->ctx,
418
7.62k
          2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
419
7.62k
  if (!res)
420
0
    goto error;
421
7.62k
  isl_seq_cpy(res->el, vec->el, 2);
422
7.62k
  isl_seq_clr(res->el + 2, res->size - 2);
423
23.1k
  for (i = 0; 
i < r->len23.1k
;
++i15.5k
)
424
15.5k
    isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
425
7.62k
426
7.62k
  isl_reordering_free(r);
427
7.62k
  isl_vec_free(vec);
428
7.62k
  return res;
429
0
error:
430
0
  isl_vec_free(vec);
431
0
  isl_reordering_free(r);
432
0
  return NULL;
433
7.62k
}
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
7.62k
{
441
7.62k
  aff = isl_aff_cow(aff);
442
7.62k
  if (!aff)
443
0
    goto error;
444
7.62k
445
7.62k
  r = isl_reordering_extend(r, aff->ls->div->n_row);
446
7.62k
  aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
447
7.62k
        aff->ls->div->n_row);
448
7.62k
  aff->ls = isl_local_space_realign(aff->ls, r);
449
7.62k
450
7.62k
  if (
!aff->v || 7.62k
!aff->ls7.62k
)
451
0
    return isl_aff_free(aff);
452
7.62k
453
7.62k
  return aff;
454
0
error:
455
0
  isl_aff_free(aff);
456
0
  isl_reordering_free(r);
457
0
  return NULL;
458
7.62k
}
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 || 0
!model0
)
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 (0
!equal_params0
)
{0
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 (1
isl_int_is_zero1
(aff->v->el[0]))
502
0
    return isl_bool_false;
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
350k
{
510
350k
  if (!aff)
511
0
    return isl_bool_error;
512
350k
513
350k
  return isl_seq_first_non_zero(aff->v->el, 2) < 0;
514
350k
}
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
1.37k
{
523
1.37k
  isl_bool equal;
524
1.37k
525
1.37k
  if (
!aff1 || 1.37k
!aff21.37k
)
526
0
    return isl_bool_error;
527
1.37k
528
1.37k
  
if (1.37k
isl_aff_is_nan(aff1) || 1.37k
isl_aff_is_nan(aff2)1.37k
)
529
0
    return isl_bool_false;
530
1.37k
531
1.37k
  equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
532
1.37k
  if (
equal < 0 || 1.37k
!equal1.37k
)
533
462
    return equal;
534
1.37k
535
912
  return isl_vec_is_equal(aff1->v, aff2->v);
536
1.37k
}
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 (0
isl_aff_is_nan(aff)0
)
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_set0
(*v, aff->v->el[0]);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
4.76k
{
557
4.76k
  isl_ctx *ctx;
558
4.76k
559
4.76k
  if (!aff)
560
0
    return NULL;
561
4.76k
562
4.76k
  ctx = isl_aff_get_ctx(aff);
563
4.76k
  if (isl_aff_is_nan(aff))
564
0
    return isl_val_nan(ctx);
565
4.76k
  return isl_val_int_from_isl_int(ctx, aff->v->el[0]);
566
4.76k
}
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 (0
isl_aff_is_nan(aff)0
)
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_set0
(*v, aff->v->el[1]);0
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
5.72k
{
587
5.72k
  isl_ctx *ctx;
588
5.72k
  isl_val *v;
589
5.72k
590
5.72k
  if (!aff)
591
0
    return NULL;
592
5.72k
593
5.72k
  ctx = isl_aff_get_ctx(aff);
594
5.72k
  if (isl_aff_is_nan(aff))
595
0
    return isl_val_nan(ctx);
596
5.72k
  v = isl_val_rat_from_isl_int(ctx, aff->v->el[1], aff->v->el[0]);
597
5.72k
  return isl_val_normalize(v);
598
5.72k
}
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 (0
type == isl_dim_out0
)
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 (0
type == isl_dim_in0
)
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 (0
isl_aff_is_nan(aff)0
)
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
24.4k
{
637
24.4k
  isl_ctx *ctx;
638
24.4k
  isl_val *v;
639
24.4k
640
24.4k
  if (!aff)
641
0
    return NULL;
642
24.4k
643
24.4k
  ctx = isl_aff_get_ctx(aff);
644
24.4k
  if (type == isl_dim_out)
645
0
    isl_die(ctx, isl_error_invalid,
646
24.4k
      "output/set dimension does not have a coefficient",
647
24.4k
      return NULL);
648
24.4k
  
if (24.4k
type == isl_dim_in24.4k
)
649
19.4k
    type = isl_dim_set;
650
24.4k
651
24.4k
  if (pos >= isl_local_space_dim(aff->ls, type))
652
0
    isl_die(ctx, isl_error_invalid,
653
24.4k
      "position out of bounds", return NULL);
654
24.4k
655
24.4k
  
if (24.4k
isl_aff_is_nan(aff)24.4k
)
656
0
    return isl_val_nan(ctx);
657
24.4k
  pos += isl_local_space_offset(aff->ls, type);
658
24.4k
  v = isl_val_rat_from_isl_int(ctx, aff->v->el[1 + pos], aff->v->el[0]);
659
24.4k
  return isl_val_normalize(v);
660
24.4k
}
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
29
{
668
29
  isl_ctx *ctx;
669
29
670
29
  if (!aff)
671
0
    return 0;
672
29
673
29
  ctx = isl_aff_get_ctx(aff);
674
29
  if (type == isl_dim_out)
675
0
    isl_die(ctx, isl_error_invalid,
676
29
      "output/set dimension does not have a coefficient",
677
29
      return 0);
678
29
  
if (29
type == isl_dim_in29
)
679
21
    type = isl_dim_set;
680
29
681
29
  if (pos >= isl_local_space_dim(aff->ls, type))
682
0
    isl_die(ctx, isl_error_invalid,
683
29
      "position out of bounds", return 0);
684
29
685
29
  pos += isl_local_space_offset(aff->ls, type);
686
29
  return isl_int_sgn(aff->v->el[1 + pos]);
687
29
}
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 (0
isl_aff_is_nan(aff)0
)
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_set0
(aff->v->el[0], v);0
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
887
{
718
887
  if (!aff)
719
0
    return NULL;
720
887
  
if (887
isl_aff_is_nan(aff)887
)
721
0
    return aff;
722
887
  aff = isl_aff_cow(aff);
723
887
  if (!aff)
724
0
    return NULL;
725
887
726
887
  aff->v = isl_vec_cow(aff->v);
727
887
  if (!aff->v)
728
0
    return isl_aff_free(aff);
729
887
730
887
  
isl_int_set887
(aff->v->el[1], v);887
731
887
732
887
  return aff;
733
887
}
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
10
{
742
10
  if (
!aff || 10
!v10
)
743
0
    goto error;
744
10
745
10
  
if (10
isl_aff_is_nan(aff)10
)
{0
746
0
    isl_val_free(v);
747
0
    return aff;
748
0
  }
749
10
750
10
  
if (10
!isl_val_is_rat(v)10
)
751
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
752
10
      "expecting rational value", goto error);
753
10
754
10
  
if (10
isl_int_eq10
(aff->v->el[1], v->n) &&10
755
8
      
isl_int_eq8
(aff->v->el[0], v->d))
{8
756
8
    isl_val_free(v);
757
8
    return aff;
758
8
  }
759
10
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 (2
isl_int_eq2
(aff->v->el[0], v->d))
{2
768
2
    isl_int_set(aff->v->el[1], v->n);
769
0
  } else 
if (0
isl_int_is_one0
(v->d))
{0
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
0
  }
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
2
}
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
15.9k
{
795
15.9k
  if (isl_int_is_zero(v))
796
2.42k
    return aff;
797
15.9k
798
13.5k
  
if (13.5k
!aff13.5k
)
799
0
    return NULL;
800
13.5k
  
if (13.5k
isl_aff_is_nan(aff)13.5k
)
801
0
    return aff;
802
13.5k
  aff = isl_aff_cow(aff);
803
13.5k
  if (!aff)
804
0
    return NULL;
805
13.5k
806
13.5k
  aff->v = isl_vec_cow(aff->v);
807
13.5k
  if (!aff->v)
808
0
    return isl_aff_free(aff);
809
13.5k
810
13.5k
  
isl_int_addmul13.5k
(aff->v->el[1], aff->v->el[0], v);13.5k
811
13.5k
812
13.5k
  return aff;
813
13.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
26
{
822
26
  if (
!aff || 26
!v26
)
823
0
    goto error;
824
26
825
26
  
if (26
isl_aff_is_nan(aff) || 26
isl_val_is_zero(v)26
)
{0
826
0
    isl_val_free(v);
827
0
    return aff;
828
0
  }
829
26
830
26
  
if (26
!isl_val_is_rat(v)26
)
831
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
832
26
      "expecting rational value", goto error);
833
26
834
26
  aff = isl_aff_cow(aff);
835
26
  if (!aff)
836
0
    goto error;
837
26
838
26
  aff->v = isl_vec_cow(aff->v);
839
26
  if (!aff->v)
840
0
    goto error;
841
26
842
26
  
if (26
isl_int_is_one26
(v->d))
{26
843
26
    isl_int_addmul(aff->v->el[1], aff->v->el[0], v->n);
844
0
  } else 
if (0
isl_int_eq0
(aff->v->el[0], v->d))
{0
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
0
  }
858
26
859
26
  isl_val_free(v);
860
26
  return aff;
861
0
error:
862
0
  isl_aff_free(aff);
863
0
  isl_val_free(v);
864
0
  return NULL;
865
26
}
866
867
__isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
868
10.9k
{
869
10.9k
  isl_int t;
870
10.9k
871
10.9k
  isl_int_init(t);
872
10.9k
  isl_int_set_si(t, v);
873
10.9k
  aff = isl_aff_add_constant(aff, t);
874
10.9k
  isl_int_clear(t);
875
10.9k
876
10.9k
  return aff;
877
10.9k
}
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
61
{
885
61
  if (isl_int_is_zero(v))
886
0
    return aff;
887
61
888
61
  
if (61
!aff61
)
889
0
    return NULL;
890
61
  
if (61
isl_aff_is_nan(aff)61
)
891
0
    return aff;
892
61
  aff = isl_aff_cow(aff);
893
61
  if (!aff)
894
0
    return NULL;
895
61
896
61
  aff->v = isl_vec_cow(aff->v);
897
61
  if (!aff->v)
898
0
    return isl_aff_free(aff);
899
61
900
61
  
isl_int_add61
(aff->v->el[1], aff->v->el[1], v);61
901
61
902
61
  return aff;
903
61
}
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
61
{
911
61
  isl_int t;
912
61
913
61
  if (v == 0)
914
0
    return aff;
915
61
916
61
  
isl_int_init61
(t);61
917
61
  isl_int_set_si(t, v);
918
61
  aff = isl_aff_add_constant_num(aff, t);
919
61
  isl_int_clear(t);
920
61
921
61
  return aff;
922
61
}
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
233
{
930
233
  if (!aff)
931
0
    return NULL;
932
233
  
if (233
isl_aff_is_nan(aff)233
)
933
0
    return aff;
934
233
  aff = isl_aff_cow(aff);
935
233
  if (!aff)
936
0
    return NULL;
937
233
938
233
  aff->v = isl_vec_cow(aff->v);
939
233
  if (!aff->v)
940
0
    return isl_aff_free(aff);
941
233
942
233
  
isl_int_set_si233
(aff->v->el[1], v);233
943
233
944
233
  return aff;
945
233
}
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
1.97k
{
955
1.97k
  if (!aff)
956
0
    return NULL;
957
1.97k
958
1.97k
  
if (1.97k
type == isl_dim_out1.97k
)
959
0
    isl_die(aff->v->ctx, isl_error_invalid,
960
1.97k
      "output/set dimension does not have a coefficient",
961
1.97k
      return isl_aff_free(aff));
962
1.97k
  
if (1.97k
type == isl_dim_in1.97k
)
963
1.50k
    type = isl_dim_set;
964
1.97k
965
1.97k
  if (pos >= isl_local_space_dim(aff->ls, type))
966
0
    isl_die(aff->v->ctx, isl_error_invalid,
967
1.97k
      "position out of bounds", return isl_aff_free(aff));
968
1.97k
969
1.97k
  
if (1.97k
isl_aff_is_nan(aff)1.97k
)
970
0
    return aff;
971
1.97k
  aff = isl_aff_cow(aff);
972
1.97k
  if (!aff)
973
0
    return NULL;
974
1.97k
975
1.97k
  aff->v = isl_vec_cow(aff->v);
976
1.97k
  if (!aff->v)
977
0
    return isl_aff_free(aff);
978
1.97k
979
1.97k
  pos += isl_local_space_offset(aff->ls, type);
980
1.97k
  isl_int_set(aff->v->el[1 + pos], v);
981
1.97k
982
1.97k
  return aff;
983
1.97k
}
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
2.55k
{
993
2.55k
  if (!aff)
994
0
    return NULL;
995
2.55k
996
2.55k
  
if (2.55k
type == isl_dim_out2.55k
)
997
0
    isl_die(aff->v->ctx, isl_error_invalid,
998
2.55k
      "output/set dimension does not have a coefficient",
999
2.55k
      return isl_aff_free(aff));
1000
2.55k
  
if (2.55k
type == isl_dim_in2.55k
)
1001
2.49k
    type = isl_dim_set;
1002
2.55k
1003
2.55k
  if (
pos < 0 || 2.55k
pos >= isl_local_space_dim(aff->ls, type)2.55k
)
1004
0
    isl_die(aff->v->ctx, isl_error_invalid,
1005
2.55k
      "position out of bounds", return isl_aff_free(aff));
1006
2.55k
1007
2.55k
  
if (2.55k
isl_aff_is_nan(aff)2.55k
)
1008
0
    return aff;
1009
2.55k
  pos += isl_local_space_offset(aff->ls, type);
1010
2.55k
  if (
isl_int_cmp_si2.55k
(aff->v->el[1 + pos], v) == 02.55k
)
1011
2
    return aff;
1012
2.55k
1013
2.54k
  aff = isl_aff_cow(aff);
1014
2.54k
  if (!aff)
1015
0
    return NULL;
1016
2.54k
1017
2.54k
  aff->v = isl_vec_cow(aff->v);
1018
2.54k
  if (!aff->v)
1019
0
    return isl_aff_free(aff);
1020
2.54k
1021
2.54k
  
isl_int_set_si2.54k
(aff->v->el[1 + pos], v);2.54k
1022
2.54k
1023
2.54k
  return aff;
1024
2.54k
}
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 || 0
!v0
)
1035
0
    goto error;
1036
0
1037
0
  
if (0
type == isl_dim_out0
)
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 (0
type == isl_dim_in0
)
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 (0
isl_aff_is_nan(aff)0
)
{0
1049
0
    isl_val_free(v);
1050
0
    return aff;
1051
0
  }
1052
0
  
if (0
!isl_val_is_rat(v)0
)
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_eq0
(aff->v->el[1 + pos], v->n) &&0
1058
0
      
isl_int_eq0
(aff->v->el[0], v->d))
{0
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 (0
isl_int_eq0
(aff->v->el[0], v->d))
{0
1071
0
    isl_int_set(aff->v->el[1 + pos], v->n);
1072
0
  } else 
if (0
isl_int_is_one0
(v->d))
{0
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
12.4k
{
1100
12.4k
  if (!aff)
1101
0
    return NULL;
1102
12.4k
1103
12.4k
  
if (12.4k
type == isl_dim_out12.4k
)
1104
0
    isl_die(aff->v->ctx, isl_error_invalid,
1105
12.4k
      "output/set dimension does not have a coefficient",
1106
12.4k
      return isl_aff_free(aff));
1107
12.4k
  
if (12.4k
type == isl_dim_in12.4k
)
1108
11.0k
    type = isl_dim_set;
1109
12.4k
1110
12.4k
  if (pos >= isl_local_space_dim(aff->ls, type))
1111
0
    isl_die(aff->v->ctx, isl_error_invalid,
1112
12.4k
      "position out of bounds", return isl_aff_free(aff));
1113
12.4k
1114
12.4k
  
if (12.4k
isl_aff_is_nan(aff)12.4k
)
1115
0
    return aff;
1116
12.4k
  aff = isl_aff_cow(aff);
1117
12.4k
  if (!aff)
1118
0
    return NULL;
1119
12.4k
1120
12.4k
  aff->v = isl_vec_cow(aff->v);
1121
12.4k
  if (!aff->v)
1122
0
    return isl_aff_free(aff);
1123
12.4k
1124
12.4k
  pos += isl_local_space_offset(aff->ls, type);
1125
12.4k
  isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
1126
12.4k
1127
12.4k
  return aff;
1128
12.4k
}
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 || 0
!v0
)
1139
0
    goto error;
1140
0
1141
0
  
if (0
isl_val_is_zero(v)0
)
{0
1142
0
    isl_val_free(v);
1143
0
    return aff;
1144
0
  }
1145
0
1146
0
  
if (0
type == isl_dim_out0
)
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 (0
type == isl_dim_in0
)
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 (0
isl_aff_is_nan(aff)0
)
{0
1158
0
    isl_val_free(v);
1159
0
    return aff;
1160
0
  }
1161
0
  
if (0
!isl_val_is_rat(v)0
)
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_one0
(v->d))
{0
1175
0
    isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1176
0
  } else 
if (0
isl_int_eq0
(aff->v->el[0], v->d))
{0
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
12.4k
{
1202
12.4k
  isl_int t;
1203
12.4k
1204
12.4k
  isl_int_init(t);
1205
12.4k
  isl_int_set_si(t, v);
1206
12.4k
  aff = isl_aff_add_coefficient(aff, type, pos, t);
1207
12.4k
  isl_int_clear(t);
1208
12.4k
1209
12.4k
  return aff;
1210
12.4k
}
1211
1212
__isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
1213
30
{
1214
30
  if (!aff)
1215
0
    return NULL;
1216
30
1217
30
  return isl_local_space_get_div(aff->ls, pos);
1218
30
}
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
22.3k
{
1226
22.3k
  if (!aff)
1227
0
    return NULL;
1228
22.3k
  
if (22.3k
isl_aff_is_nan(aff)22.3k
)
1229
1
    return aff;
1230
22.3k
  aff = isl_aff_cow(aff);
1231
22.3k
  if (!aff)
1232
0
    return NULL;
1233
22.3k
  aff->v = isl_vec_cow(aff->v);
1234
22.3k
  if (!aff->v)
1235
0
    return isl_aff_free(aff);
1236
22.3k
1237
22.3k
  isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
1238
22.3k
1239
22.3k
  return aff;
1240
22.3k
}
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
23.1k
{
1251
23.1k
  int pos;
1252
23.1k
  int off;
1253
23.1k
  int n;
1254
23.1k
1255
23.1k
  if (!aff)
1256
0
    return NULL;
1257
23.1k
1258
23.1k
  n = isl_local_space_dim(aff->ls, isl_dim_div);
1259
23.1k
  off = isl_local_space_offset(aff->ls, isl_dim_div);
1260
23.1k
1261
23.1k
  pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
1262
23.1k
  if (pos == n)
1263
22.5k
    return aff;
1264
23.1k
1265
606
  aff = isl_aff_cow(aff);
1266
606
  if (!aff)
1267
0
    return NULL;
1268
606
1269
606
  aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
1270
606
  aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
1271
606
  if (
!aff->ls || 606
!aff->v606
)
1272
0
    return isl_aff_free(aff);
1273
606
1274
606
  return aff;
1275
606
}
1276
1277
/* Given two affine expressions "p" of length p_len (including the
1278
 * denominator and the constant term) and "subs" of length subs_len,
1279
 * plug in "subs" for the variable at position "pos".
1280
 * The variables of "subs" and "p" are assumed to match up to subs_len,
1281
 * but "p" may have additional variables.
1282
 * "v" is an initialized isl_int that can be used internally.
1283
 *
1284
 * In particular, if "p" represents the expression
1285
 *
1286
 *  (a i + g)/m
1287
 *
1288
 * with i the variable at position "pos" and "subs" represents the expression
1289
 *
1290
 *  f/d
1291
 *
1292
 * then the result represents the expression
1293
 *
1294
 *  (a f + d g)/(m d)
1295
 *
1296
 */
1297
void isl_seq_substitute(isl_int *p, int pos, isl_int *subs,
1298
  int p_len, int subs_len, isl_int v)
1299
424
{
1300
424
  isl_int_set(v, p[1 + pos]);
1301
424
  isl_int_set_si(p[1 + pos], 0);
1302
424
  isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
1303
424
  isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
1304
424
  isl_int_mul(p[0], p[0], subs[0]);
1305
424
}
1306
1307
/* Look for any divs in the aff->ls with a denominator equal to one
1308
 * and plug them into the affine expression and any subsequent divs
1309
 * that may reference the div.
1310
 */
1311
static __isl_give isl_aff *plug_in_integral_divs(__isl_take isl_aff *aff)
1312
18.8k
{
1313
18.8k
  int i, n;
1314
18.8k
  int len;
1315
18.8k
  isl_int v;
1316
18.8k
  isl_vec *vec;
1317
18.8k
  isl_local_space *ls;
1318
18.8k
  unsigned pos;
1319
18.8k
1320
18.8k
  if (!aff)
1321
0
    return NULL;
1322
18.8k
1323
18.8k
  n = isl_local_space_dim(aff->ls, isl_dim_div);
1324
18.8k
  len = aff->v->size;
1325
24.3k
  for (i = 0; 
i < n24.3k
;
++i5.49k
)
{5.49k
1326
5.49k
    if (
!5.49k
isl_int_is_one5.49k
(aff->ls->div->row[i][0]))
1327
5.31k
      continue;
1328
179
    ls = isl_local_space_copy(aff->ls);
1329
179
    ls = isl_local_space_substitute_seq(ls, isl_dim_div, i,
1330
179
        aff->ls->div->row[i], len, i + 1, n - (i + 1));
1331
179
    vec = isl_vec_copy(aff->v);
1332
179
    vec = isl_vec_cow(vec);
1333
179
    if (
!ls || 179
!vec179
)
1334
0
      goto error;
1335
179
1336
179
    
isl_int_init179
(v);179
1337
179
1338
179
    pos = isl_local_space_offset(aff->ls, isl_dim_div) + i;
1339
179
    isl_seq_substitute(vec->el, pos, aff->ls->div->row[i],
1340
179
          len, len, v);
1341
179
1342
179
    isl_int_clear(v);
1343
179
1344
179
    isl_vec_free(aff->v);
1345
179
    aff->v = vec;
1346
179
    isl_local_space_free(aff->ls);
1347
179
    aff->ls = ls;
1348
179
  }
1349
18.8k
1350
18.8k
  return aff;
1351
0
error:
1352
0
  isl_vec_free(vec);
1353
0
  isl_local_space_free(ls);
1354
0
  return isl_aff_free(aff);
1355
18.8k
}
1356
1357
/* Look for any divs j that appear with a unit coefficient inside
1358
 * the definitions of other divs i and plug them into the definitions
1359
 * of the divs i.
1360
 *
1361
 * In particular, an expression of the form
1362
 *
1363
 *  floor((f(..) + floor(g(..)/n))/m)
1364
 *
1365
 * is simplified to
1366
 *
1367
 *  floor((n * f(..) + g(..))/(n * m))
1368
 *
1369
 * This simplification is correct because we can move the expression
1370
 * f(..) into the inner floor in the original expression to obtain
1371
 *
1372
 *  floor(floor((n * f(..) + g(..))/n)/m)
1373
 *
1374
 * from which we can derive the simplified expression.
1375
 */
1376
static __isl_give isl_aff *plug_in_unit_divs(__isl_take isl_aff *aff)
1377
18.8k
{
1378
18.8k
  int i, j, n;
1379
18.8k
  int off;
1380
18.8k
1381
18.8k
  if (!aff)
1382
0
    return NULL;
1383
18.8k
1384
18.8k
  n = isl_local_space_dim(aff->ls, isl_dim_div);
1385
18.8k
  off = isl_local_space_offset(aff->ls, isl_dim_div);
1386
20.0k
  for (i = 1; 
i < n20.0k
;
++i1.19k
)
{1.19k
1387
4.19k
    for (j = 0; 
j < i4.19k
;
++j3.00k
)
{3.00k
1388
3.00k
      if (
!3.00k
isl_int_is_one3.00k
(aff->ls->div->row[i][1 + off + j]))
1389
2.90k
        continue;
1390
101
      aff->ls = isl_local_space_substitute_seq(aff->ls,
1391
101
        isl_dim_div, j, aff->ls->div->row[j],
1392
101
        aff->v->size, i, 1);
1393
101
      if (!aff->ls)
1394
0
        return isl_aff_free(aff);
1395
101
    }
1396
1.19k
  }
1397
18.8k
1398
18.8k
  return aff;
1399
18.8k
}
1400
1401
/* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
1402
 *
1403
 * Even though this function is only called on isl_affs with a single
1404
 * reference, we are careful to only change aff->v and aff->ls together.
1405
 */
1406
static __isl_give isl_aff *swap_div(__isl_take isl_aff *aff, int a, int b)
1407
1.23k
{
1408
1.23k
  unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
1409
1.23k
  isl_local_space *ls;
1410
1.23k
  isl_vec *v;
1411
1.23k
1412
1.23k
  ls = isl_local_space_copy(aff->ls);
1413
1.23k
  ls = isl_local_space_swap_div(ls, a, b);
1414
1.23k
  v = isl_vec_copy(aff->v);
1415
1.23k
  v = isl_vec_cow(v);
1416
1.23k
  if (
!ls || 1.23k
!v1.23k
)
1417
0
    goto error;
1418
1.23k
1419
1.23k
  
isl_int_swap1.23k
(v->el[1 + off + a], v->el[1 + off + b]);1.23k
1420
1.23k
  isl_vec_free(aff->v);
1421
1.23k
  aff->v = v;
1422
1.23k
  isl_local_space_free(aff->ls);
1423
1.23k
  aff->ls = ls;
1424
1.23k
1425
1.23k
  return aff;
1426
0
error:
1427
0
  isl_vec_free(v);
1428
0
  isl_local_space_free(ls);
1429
0
  return isl_aff_free(aff);
1430
1.23k
}
1431
1432
/* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
1433
 *
1434
 * We currently do not actually remove div "b", but simply add its
1435
 * coefficient to that of "a" and then zero it out.
1436
 */
1437
static __isl_give isl_aff *merge_divs(__isl_take isl_aff *aff, int a, int b)
1438
106
{
1439
106
  unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
1440
106
1441
106
  if (isl_int_is_zero(aff->v->el[1 + off + b]))
1442
74
    return aff;
1443
106
1444
32
  aff->v = isl_vec_cow(aff->v);
1445
32
  if (!aff->v)
1446
0
    return isl_aff_free(aff);
1447
32
1448
32
  
isl_int_add32
(aff->v->el[1 + off + a],32
1449
32
        aff->v->el[1 + off + a], aff->v->el[1 + off + b]);
1450
32
  isl_int_set_si(aff->v->el[1 + off + b], 0);
1451
32
1452
32
  return aff;
1453
32
}
1454
1455
/* Sort the divs in the local space of "aff" according to
1456
 * the comparison function "cmp_row" in isl_local_space.c,
1457
 * combining the coefficients of identical divs.
1458
 *
1459
 * Reordering divs does not change the semantics of "aff",
1460
 * so there is no need to call isl_aff_cow.
1461
 * Moreover, this function is currently only called on isl_affs
1462
 * with a single reference.
1463
 */
1464
static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff)
1465
18.8k
{
1466
18.8k
  int i, j, n;
1467
18.8k
1468
18.8k
  if (!aff)
1469
0
    return NULL;
1470
18.8k
1471
18.8k
  n = isl_aff_dim(aff, isl_dim_div);
1472
20.0k
  for (i = 1; 
i < n20.0k
;
++i1.19k
)
{1.19k
1473
2.52k
    for (j = i - 1; 
j >= 02.52k
;
--j1.33k
)
{2.16k
1474
2.16k
      int cmp = isl_mat_cmp_div(aff->ls->div, j, j + 1);
1475
2.16k
      if (cmp < 0)
1476
833
        break;
1477
1.33k
      
if (1.33k
cmp == 01.33k
)
1478
106
        aff = merge_divs(aff, j, j + 1);
1479
1.33k
      else
1480
1.23k
        aff = swap_div(aff, j, j + 1);
1481
1.33k
      if (!aff)
1482
0
        return NULL;
1483
1.33k
    }
1484
1.19k
  }
1485
18.8k
1486
18.8k
  return aff;
1487
18.8k
}
1488
1489
/* Normalize the representation of "aff".
1490
 *
1491
 * This function should only be called of "new" isl_affs, i.e.,
1492
 * with only a single reference.  We therefore do not need to
1493
 * worry about affecting other instances.
1494
 */
1495
__isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
1496
18.8k
{
1497
18.8k
  if (!aff)
1498
0
    return NULL;
1499
18.8k
  aff->v = isl_vec_normalize(aff->v);
1500
18.8k
  if (!aff->v)
1501
0
    return isl_aff_free(aff);
1502
18.8k
  aff = plug_in_integral_divs(aff);
1503
18.8k
  aff = plug_in_unit_divs(aff);
1504
18.8k
  aff = sort_divs(aff);
1505
18.8k
  aff = isl_aff_remove_unused_divs(aff);
1506
18.8k
  return aff;
1507
18.8k
}
1508
1509
/* Given f, return floor(f).
1510
 * If f is an integer expression, then just return f.
1511
 * If f is a constant, then return the constant floor(f).
1512
 * Otherwise, if f = g/m, write g = q m + r,
1513
 * create a new div d = [r/m] and return the expression q + d.
1514
 * The coefficients in r are taken to lie between -m/2 and m/2.
1515
 *
1516
 * reduce_div_coefficients performs the same normalization.
1517
 *
1518
 * As a special case, floor(NaN) = NaN.
1519
 */
1520
__isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
1521
11.1k
{
1522
11.1k
  int i;
1523
11.1k
  int size;
1524
11.1k
  isl_ctx *ctx;
1525
11.1k
  isl_vec *div;
1526
11.1k
1527
11.1k
  if (!aff)
1528
0
    return NULL;
1529
11.1k
1530
11.1k
  
if (11.1k
isl_aff_is_nan(aff)11.1k
)
1531
0
    return aff;
1532
11.1k
  
if (11.1k
isl_int_is_one11.1k
(aff->v->el[0]))
1533
7.41k
    return aff;
1534
11.1k
1535
3.74k
  aff = isl_aff_cow(aff);
1536
3.74k
  if (!aff)
1537
0
    return NULL;
1538
3.74k
1539
3.74k
  aff->v = isl_vec_cow(aff->v);
1540
3.74k
  if (!aff->v)
1541
0
    return isl_aff_free(aff);
1542
3.74k
1543
3.74k
  
if (3.74k
isl_aff_is_cst(aff)3.74k
)
{130
1544
130
    isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
1545
130
    isl_int_set_si(aff->v->el[0], 1);
1546
130
    return aff;
1547
130
  }
1548
3.74k
1549
3.61k
  div = isl_vec_copy(aff->v);
1550
3.61k
  div = isl_vec_cow(div);
1551
3.61k
  if (!div)
1552
0
    return isl_aff_free(aff);
1553
3.61k
1554
3.61k
  ctx = isl_aff_get_ctx(aff);
1555
3.61k
  isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
1556
15.4k
  for (i = 1; 
i < aff->v->size15.4k
;
++i11.8k
)
{11.8k
1557
11.8k
    isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
1558
11.8k
    isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
1559
11.8k
    if (
isl_int_gt11.8k
(div->el[i], aff->v->el[0]))
{1.28k
1560
1.28k
      isl_int_sub(div->el[i], div->el[i], div->el[0]);
1561
1.28k
      isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
1562
1.28k
    }
1563
11.8k
  }
1564
3.61k
1565
3.61k
  aff->ls = isl_local_space_add_div(aff->ls, div);
1566
3.61k
  if (!aff->ls)
1567
0
    return isl_aff_free(aff);
1568
3.61k
1569
3.61k
  size = aff->v->size;
1570
3.61k
  aff->v = isl_vec_extend(aff->v, size + 1);
1571
3.61k
  if (!aff->v)
1572
0
    return isl_aff_free(aff);
1573
3.61k
  
isl_int_set_si3.61k
(aff->v->el[0], 1);3.61k
1574
3.61k
  isl_int_set_si(aff->v->el[size], 1);
1575
3.61k
1576
3.61k
  aff = isl_aff_normalize(aff);
1577
3.61k
1578
3.61k
  return aff;
1579
3.61k
}
1580
1581
/* Compute
1582
 *
1583
 *  aff mod m = aff - m * floor(aff/m)
1584
 */
1585
__isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
1586
0
{
1587
0
  isl_aff *res;
1588
0
1589
0
  res = isl_aff_copy(aff);
1590
0
  aff = isl_aff_scale_down(aff, m);
1591
0
  aff = isl_aff_floor(aff);
1592
0
  aff = isl_aff_scale(aff, m);
1593
0
  res = isl_aff_sub(res, aff);
1594
0
1595
0
  return res;
1596
0
}
1597
1598
/* Compute
1599
 *
1600
 *  aff mod m = aff - m * floor(aff/m)
1601
 *
1602
 * with m an integer value.
1603
 */
1604
__isl_give isl_aff *isl_aff_mod_val(__isl_take isl_aff *aff,
1605
  __isl_take isl_val *m)
1606
78
{
1607
78
  isl_aff *res;
1608
78
1609
78
  if (
!aff || 78
!m78
)
1610
0
    goto error;
1611
78
1612
78
  
if (78
!isl_val_is_int(m)78
)
1613
0
    isl_die(isl_val_get_ctx(m), isl_error_invalid,
1614
78
      "expecting integer modulo", goto error);
1615
78
1616
78
  res = isl_aff_copy(aff);
1617
78
  aff = isl_aff_scale_down_val(aff, isl_val_copy(m));
1618
78
  aff = isl_aff_floor(aff);
1619
78
  aff = isl_aff_scale_val(aff, m);
1620
78
  res = isl_aff_sub(res, aff);
1621
78
1622
78
  return res;
1623
0
error:
1624
0
  isl_aff_free(aff);
1625
0
  isl_val_free(m);
1626
0
  return NULL;
1627
78
}
1628
1629
/* Compute
1630
 *
1631
 *  pwaff mod m = pwaff - m * floor(pwaff/m)
1632
 */
1633
__isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
1634
2.70k
{
1635
2.70k
  isl_pw_aff *res;
1636
2.70k
1637
2.70k
  res = isl_pw_aff_copy(pwaff);
1638
2.70k
  pwaff = isl_pw_aff_scale_down(pwaff, m);
1639
2.70k
  pwaff = isl_pw_aff_floor(pwaff);
1640
2.70k
  pwaff = isl_pw_aff_scale(pwaff, m);
1641
2.70k
  res = isl_pw_aff_sub(res, pwaff);
1642
2.70k
1643
2.70k
  return res;
1644
2.70k
}
1645
1646
/* Compute
1647
 *
1648
 *  pa mod m = pa - m * floor(pa/m)
1649
 *
1650
 * with m an integer value.
1651
 */
1652
__isl_give isl_pw_aff *isl_pw_aff_mod_val(__isl_take isl_pw_aff *pa,
1653
  __isl_take isl_val *m)
1654
2.70k
{
1655
2.70k
  if (
!pa || 2.70k
!m2.70k
)
1656
0
    goto error;
1657
2.70k
  
if (2.70k
!isl_val_is_int(m)2.70k
)
1658
0
    isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
1659
2.70k
      "expecting integer modulo", goto error);
1660
2.70k
  pa = isl_pw_aff_mod(pa, m->n);
1661
2.70k
  isl_val_free(m);
1662
2.70k
  return pa;
1663
0
error:
1664
0
  isl_pw_aff_free(pa);
1665
0
  isl_val_free(m);
1666
0
  return NULL;
1667
2.70k
}
1668
1669
/* Given f, return ceil(f).
1670
 * If f is an integer expression, then just return f.
1671
 * Otherwise, let f be the expression
1672
 *
1673
 *  e/m
1674
 *
1675
 * then return
1676
 *
1677
 *  floor((e + m - 1)/m)
1678
 *
1679
 * As a special case, ceil(NaN) = NaN.
1680
 */
1681
__isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
1682
1.33k
{
1683
1.33k
  if (!aff)
1684
0
    return NULL;
1685
1.33k
1686
1.33k
  
if (1.33k
isl_aff_is_nan(aff)1.33k
)
1687
0
    return aff;
1688
1.33k
  
if (1.33k
isl_int_is_one1.33k
(aff->v->el[0]))
1689
1.26k
    return aff;
1690
1.33k
1691
69
  aff = isl_aff_cow(aff);
1692
69
  if (!aff)
1693
0
    return NULL;
1694
69
  aff->v = isl_vec_cow(aff->v);
1695
69
  if (!aff->v)
1696
0
    return isl_aff_free(aff);
1697
69
1698
69
  
isl_int_add69
(aff->v->el[1], aff->v->el[1], aff->v->el[0]);69
1699
69
  isl_int_sub_ui(aff->v->el[1], aff->v->el[1], 1);
1700
69
  aff = isl_aff_floor(aff);
1701
69
1702
69
  return aff;
1703
69
}
1704
1705
/* Apply the expansion computed by isl_merge_divs.
1706
 * The expansion itself is given by "exp" while the resulting
1707
 * list of divs is given by "div".
1708
 */
1709
__isl_give isl_aff *isl_aff_expand_divs(__isl_take isl_aff *aff,
1710
  __isl_take isl_mat *div, int *exp)
1711
36.8k
{
1712
36.8k
  int old_n_div;
1713
36.8k
  int new_n_div;
1714
36.8k
  int offset;
1715
36.8k
1716
36.8k
  aff = isl_aff_cow(aff);
1717
36.8k
  if (
!aff || 36.8k
!div36.8k
)
1718
0
    goto error;
1719
36.8k
1720
36.8k
  old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1721
36.8k
  new_n_div = isl_mat_rows(div);
1722
36.8k
  offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
1723
36.8k
1724
36.8k
  aff->v = isl_vec_expand(aff->v, offset, old_n_div, exp, new_n_div);
1725
36.8k
  aff->ls = isl_local_space_replace_divs(aff->ls, div);
1726
36.8k
  if (
!aff->v || 36.8k
!aff->ls36.8k
)
1727
0
    return isl_aff_free(aff);
1728
36.8k
  return aff;
1729
0
error:
1730
0
  isl_aff_free(aff);
1731
0
  isl_mat_free(div);
1732
0
  return NULL;
1733
36.8k
}
1734
1735
/* Add two affine expressions that live in the same local space.
1736
 */
1737
static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
1738
  __isl_take isl_aff *aff2)
1739
54.0k
{
1740
54.0k
  isl_int gcd, f;
1741
54.0k
1742
54.0k
  aff1 = isl_aff_cow(aff1);
1743
54.0k
  if (
!aff1 || 54.0k
!aff254.0k
)
1744
0
    goto error;
1745
54.0k
1746
54.0k
  aff1->v = isl_vec_cow(aff1->v);
1747
54.0k
  if (!aff1->v)
1748
0
    goto error;
1749
54.0k
1750
54.0k
  
isl_int_init54.0k
(gcd);54.0k
1751
54.0k
  isl_int_init(f);
1752
54.0k
  isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
1753
54.0k
  isl_int_divexact(f, aff2->v->el[0], gcd);
1754
54.0k
  isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
1755
54.0k
  isl_int_divexact(f, aff1->v->el[0], gcd);
1756
54.0k
  isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
1757
54.0k
  isl_int_divexact(f, aff2->v->el[0], gcd);
1758
54.0k
  isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
1759
54.0k
  isl_int_clear(f);
1760
54.0k
  isl_int_clear(gcd);
1761
54.0k
1762
54.0k
  isl_aff_free(aff2);
1763
54.0k
  return aff1;
1764
0
error:
1765
0
  isl_aff_free(aff1);
1766
0
  isl_aff_free(aff2);
1767
0
  return NULL;
1768
54.0k
}
1769
1770
/* Return the sum of "aff1" and "aff2".
1771
 *
1772
 * If either of the two is NaN, then the result is NaN.
1773
 */
1774
__isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
1775
  __isl_take isl_aff *aff2)
1776
54.0k
{
1777
54.0k
  isl_ctx *ctx;
1778
54.0k
  int *exp1 = NULL;
1779
54.0k
  int *exp2 = NULL;
1780
54.0k
  isl_mat *div;
1781
54.0k
  int n_div1, n_div2;
1782
54.0k
1783
54.0k
  if (
!aff1 || 54.0k
!aff254.0k
)
1784
0
    goto error;
1785
54.0k
1786
54.0k
  ctx = isl_aff_get_ctx(aff1);
1787
54.0k
  if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
1788
0
    isl_die(ctx, isl_error_invalid,
1789
54.0k
      "spaces don't match", goto error);
1790
54.0k
1791
54.0k
  
if (54.0k
isl_aff_is_nan(aff1)54.0k
)
{2
1792
2
    isl_aff_free(aff2);
1793
2
    return aff1;
1794
2
  }
1795
54.0k
  
if (54.0k
isl_aff_is_nan(aff2)54.0k
)
{32
1796
32
    isl_aff_free(aff1);
1797
32
    return aff2;
1798
32
  }
1799
54.0k
1800
54.0k
  n_div1 = isl_aff_dim(aff1, isl_dim_div);
1801
54.0k
  n_div2 = isl_aff_dim(aff2, isl_dim_div);
1802
54.0k
  if (
n_div1 == 0 && 54.0k
n_div2 == 042.1k
)
1803
35.8k
    return add_expanded(aff1, aff2);
1804
54.0k
1805
18.1k
  
exp1 = 18.1k
isl_alloc_array18.1k
(ctx, int, n_div1);
1806
18.1k
  exp2 = isl_alloc_array(ctx, int, n_div2);
1807
18.1k
  if (
(n_div1 && 18.1k
!exp111.9k
) ||
(n_div2 && 18.1k
!exp26.58k
))
1808
0
    goto error;
1809
18.1k
1810
18.1k
  div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
1811
18.1k
  aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
1812
18.1k
  aff2 = isl_aff_expand_divs(aff2, div, exp2);
1813
18.1k
  free(exp1);
1814
18.1k
  free(exp2);
1815
18.1k
1816
18.1k
  return add_expanded(aff1, aff2);
1817
0
error:
1818
0
  free(exp1);
1819
0
  free(exp2);
1820
0
  isl_aff_free(aff1);
1821
0
  isl_aff_free(aff2);
1822
0
  return NULL;
1823
18.1k
}
1824
1825
__isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
1826
  __isl_take isl_aff *aff2)
1827
336
{
1828
336
  return isl_aff_add(aff1, isl_aff_neg(aff2));
1829
336
}
1830
1831
/* Return the result of scaling "aff" by a factor of "f".
1832
 *
1833
 * As a special case, f * NaN = NaN.
1834
 */
1835
__isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
1836
17.4k
{
1837
17.4k
  isl_int gcd;
1838
17.4k
1839
17.4k
  if (!aff)
1840
0
    return NULL;
1841
17.4k
  
if (17.4k
isl_aff_is_nan(aff)17.4k
)
1842
0
    return aff;
1843
17.4k
1844
17.4k
  
if (17.4k
isl_int_is_one17.4k
(f))
1845
9.41k
    return aff;
1846
17.4k
1847
8.00k
  aff = isl_aff_cow(aff);
1848
8.00k
  if (!aff)
1849
0
    return NULL;
1850
8.00k
  aff->v = isl_vec_cow(aff->v);
1851
8.00k
  if (!aff->v)
1852
0
    return isl_aff_free(aff);
1853
8.00k
1854
8.00k
  
if (8.00k
isl_int_is_pos8.00k
(f) && 8.00k
isl_int_is_divisible_by6.99k
(aff->v->el[0], f))
{66
1855
66
    isl_int_divexact(aff->v->el[0], aff->v->el[0], f);
1856
66
    return aff;
1857
66
  }
1858
8.00k
1859
7.94k
  
isl_int_init7.94k
(gcd);7.94k
1860
7.94k
  isl_int_gcd(gcd, aff->v->el[0], f);
1861
7.94k
  isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
1862
7.94k
  isl_int_divexact(gcd, f, gcd);
1863
7.94k
  isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1864
7.94k
  isl_int_clear(gcd);
1865
7.94k
1866
7.94k
  return aff;
1867
8.00k
}
1868
1869
/* Multiple "aff" by "v".
1870
 */
1871
__isl_give isl_aff *isl_aff_scale_val(__isl_take isl_aff *aff,
1872
  __isl_take isl_val *v)
1873
326
{
1874
326
  if (
!aff || 326
!v326
)
1875
0
    goto error;
1876
326
1877
326
  
if (326
isl_val_is_one(v)326
)
{23
1878
23
    isl_val_free(v);
1879
23
    return aff;
1880
23
  }
1881
326
1882
303
  
if (303
!isl_val_is_rat(v)303
)
1883
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1884
303
      "expecting rational factor", goto error);
1885
303
1886
303
  aff = isl_aff_scale(aff, v->n);
1887
303
  aff = isl_aff_scale_down(aff, v->d);
1888
303
1889
303
  isl_val_free(v);
1890
303
  return aff;
1891
0
error:
1892
0
  isl_aff_free(aff);
1893
0
  isl_val_free(v);
1894
0
  return NULL;
1895
303
}
1896
1897
/* Return the result of scaling "aff" down by a factor of "f".
1898
 *
1899
 * As a special case, NaN/f = NaN.
1900
 */
1901
__isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
1902
16.4k
{
1903
16.4k
  isl_int gcd;
1904
16.4k
1905
16.4k
  if (!aff)
1906
0
    return NULL;
1907
16.4k
  
if (16.4k
isl_aff_is_nan(aff)16.4k
)
1908
0
    return aff;
1909
16.4k
1910
16.4k
  
if (16.4k
isl_int_is_one16.4k
(f))
1911
12.8k
    return aff;
1912
16.4k
1913
3.66k
  aff = isl_aff_cow(aff);
1914
3.66k
  if (!aff)
1915
0
    return NULL;
1916
3.66k
1917
3.66k
  
if (3.66k
isl_int_is_zero3.66k
(f))
1918
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1919
3.66k
      "cannot scale down by zero", return isl_aff_free(aff));
1920
3.66k
1921
3.66k
  aff->v = isl_vec_cow(aff->v);
1922
3.66k
  if (!aff->v)
1923
0
    return isl_aff_free(aff);
1924
3.66k
1925
3.66k
  
isl_int_init3.66k
(gcd);3.66k
1926
3.66k
  isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
1927
3.66k
  isl_int_gcd(gcd, gcd, f);
1928
3.66k
  isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1929
3.66k
  isl_int_divexact(gcd, f, gcd);
1930
3.66k
  isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
1931
3.66k
  isl_int_clear(gcd);
1932
3.66k
1933
3.66k
  return aff;
1934
3.66k
}
1935
1936
/* Divide "aff" by "v".
1937
 */
1938
__isl_give isl_aff *isl_aff_scale_down_val(__isl_take isl_aff *aff,
1939
  __isl_take isl_val *v)
1940
260
{
1941
260
  if (
!aff || 260
!v260
)
1942
0
    goto error;
1943
260
1944
260
  
if (260
isl_val_is_one(v)260
)
{12
1945
12
    isl_val_free(v);
1946
12
    return aff;
1947
12
  }
1948
260
1949
248
  
if (248
!isl_val_is_rat(v)248
)
1950
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1951
248
      "expecting rational factor", goto error);
1952
248
  
if (248
!isl_val_is_pos(v)248
)
1953
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1954
248
      "factor needs to be positive", goto error);
1955
248
1956
248
  aff = isl_aff_scale(aff, v->d);
1957
248
  aff = isl_aff_scale_down(aff, v->n);
1958
248
1959
248
  isl_val_free(v);
1960
248
  return aff;
1961
0
error:
1962
0
  isl_aff_free(aff);
1963
0
  isl_val_free(v);
1964
0
  return NULL;
1965
248
}
1966
1967
__isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
1968
3
{
1969
3
  isl_int v;
1970
3
1971
3
  if (f == 1)
1972
0
    return aff;
1973
3
1974
3
  
isl_int_init3
(v);3
1975
3
  isl_int_set_ui(v, f);
1976
3
  aff = isl_aff_scale_down(aff, v);
1977
3
  isl_int_clear(v);
1978
3
1979
3
  return aff;
1980
3
}
1981
1982
__isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
1983
  enum isl_dim_type type, unsigned pos, const char *s)
1984
0
{
1985
0
  aff = isl_aff_cow(aff);
1986
0
  if (!aff)
1987
0
    return NULL;
1988
0
  
if (0
type == isl_dim_out0
)
1989
0
    isl_die(aff->v->ctx, isl_error_invalid,
1990
0
      "cannot set name of output/set dimension",
1991
0
      return isl_aff_free(aff));
1992
0
  
if (0
type == isl_dim_in0
)
1993
0
    type = isl_dim_set;
1994
0
  aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
1995
0
  if (!aff->ls)
1996
0
    return isl_aff_free(aff);
1997
0
1998
0
  return aff;
1999
0
}
2000
2001
__isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
2002
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
2003
0
{
2004
0
  aff = isl_aff_cow(aff);
2005
0
  if (!aff)
2006
0
    goto error;
2007
0
  
if (0
type == isl_dim_out0
)
2008
0
    isl_die(aff->v->ctx, isl_error_invalid,
2009
0
      "cannot set name of output/set dimension",
2010
0
      goto error);
2011
0
  
if (0
type == isl_dim_in0
)
2012
0
    type = isl_dim_set;
2013
0
  aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
2014
0
  if (!aff->ls)
2015
0
    return isl_aff_free(aff);
2016
0
2017
0
  return aff;
2018
0
error:
2019
0
  isl_id_free(id);
2020
0
  isl_aff_free(aff);
2021
0
  return NULL;
2022
0
}
2023
2024
/* Replace the identifier of the input tuple of "aff" by "id".
2025
 * type is currently required to be equal to isl_dim_in
2026
 */
2027
__isl_give isl_aff *isl_aff_set_tuple_id(__isl_take isl_aff *aff,
2028
  enum isl_dim_type type, __isl_take isl_id *id)
2029
0
{
2030
0
  aff = isl_aff_cow(aff);
2031
0
  if (!aff)
2032
0
    goto error;
2033
0
  
if (0
type != isl_dim_out0
)
2034
0
    isl_die(aff->v->ctx, isl_error_invalid,
2035
0
      "cannot only set id of input tuple", goto error);
2036
0
  aff->ls = isl_local_space_set_tuple_id(aff->ls, isl_dim_set, id);
2037
0
  if (!aff->ls)
2038
0
    return isl_aff_free(aff);
2039
0
2040
0
  return aff;
2041
0
error:
2042
0
  isl_id_free(id);
2043
0
  isl_aff_free(aff);
2044
0
  return NULL;
2045
0
}
2046
2047
/* Exploit the equalities in "eq" to simplify the affine expression
2048
 * and the expressions of the integer divisions in the local space.
2049
 * The integer divisions in this local space are assumed to appear
2050
 * as regular dimensions in "eq".
2051
 */
2052
static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
2053
  __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
2054
108k
{
2055
108k
  int i, j;
2056
108k
  unsigned total;
2057
108k
  unsigned n_div;
2058
108k
2059
108k
  if (!eq)
2060
0
    goto error;
2061
108k
  
if (108k
eq->n_eq == 0108k
)
{107k
2062
107k
    isl_basic_set_free(eq);
2063
107k
    return aff;
2064
107k
  }
2065
108k
2066
896
  aff = isl_aff_cow(aff);
2067
896
  if (!aff)
2068
0
    goto error;
2069
896
2070
896
  aff->ls = isl_local_space_substitute_equalities(aff->ls,
2071
896
              isl_basic_set_copy(eq));
2072
896
  aff->v = isl_vec_cow(aff->v);
2073
896
  if (
!aff->ls || 896
!aff->v896
)
2074
0
    goto error;
2075
896
2076
896
  total = 1 + isl_space_dim(eq->dim, isl_dim_all);
2077
896
  n_div = eq->n_div;
2078
1.94k
  for (i = 0; 
i < eq->n_eq1.94k
;
++i1.04k
)
{1.04k
2079
1.04k
    j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
2080
1.04k
    if (
j < 0 || 1.04k
j == 01.04k
||
j >= total1.04k
)
2081
323
      continue;
2082
1.04k
2083
722
    isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
2084
722
        &aff->v->el[0]);
2085
722
  }
2086
896
2087
896
  isl_basic_set_free(eq);
2088
896
  aff = isl_aff_normalize(aff);
2089
896
  return aff;
2090
0
error:
2091
0
  isl_basic_set_free(eq);
2092
0
  isl_aff_free(aff);
2093
0
  return NULL;
2094
896
}
2095
2096
/* Exploit the equalities in "eq" to simplify the affine expression
2097
 * and the expressions of the integer divisions in the local space.
2098
 */
2099
__isl_give isl_aff *isl_aff_substitute_equalities(__isl_take isl_aff *aff,
2100
  __isl_take isl_basic_set *eq)
2101
33.3k
{
2102
33.3k
  int n_div;
2103
33.3k
2104
33.3k
  if (
!aff || 33.3k
!eq33.3k
)
2105
0
    goto error;
2106
33.3k
  n_div = isl_local_space_dim(aff->ls, isl_dim_div);
2107
33.3k
  if (n_div > 0)
2108
6.27k
    eq = isl_basic_set_add_dims(eq, isl_dim_set, n_div);
2109
33.3k
  return isl_aff_substitute_equalities_lifted(aff, eq);
2110
0
error:
2111
0
  isl_basic_set_free(eq);
2112
0
  isl_aff_free(aff);
2113
0
  return NULL;
2114
33.3k
}
2115
2116
/* Look for equalities among the variables shared by context and aff
2117
 * and the integer divisions of aff, if any.
2118
 * The equalities are then used to eliminate coefficients and/or integer
2119
 * divisions from aff.
2120
 */
2121
__isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
2122
  __isl_take isl_set *context)
2123
75.3k
{
2124
75.3k
  isl_basic_set *hull;
2125
75.3k
  int n_div;
2126
75.3k
2127
75.3k
  if (!aff)
2128
0
    goto error;
2129
75.3k
  n_div = isl_local_space_dim(aff->ls, isl_dim_div);
2130
75.3k
  if (
n_div > 075.3k
)
{18.6k
2131
18.6k
    isl_basic_set *bset;
2132
18.6k
    isl_local_space *ls;
2133
18.6k
    context = isl_set_add_dims(context, isl_dim_set, n_div);
2134
18.6k
    ls = isl_aff_get_domain_local_space(aff);
2135
18.6k
    bset = isl_basic_set_from_local_space(ls);
2136
18.6k
    bset = isl_basic_set_lift(bset);
2137
18.6k
    bset = isl_basic_set_flatten(bset);
2138
18.6k
    context = isl_set_intersect(context,
2139
18.6k
              isl_set_from_basic_set(bset));
2140
18.6k
  }
2141
75.3k
2142
75.3k
  hull = isl_set_affine_hull(context);
2143
75.3k
  return isl_aff_substitute_equalities_lifted(aff, hull);
2144
0
error:
2145
0
  isl_aff_free(aff);
2146
0
  isl_set_free(context);
2147
0
  return NULL;
2148
75.3k
}
2149
2150
__isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
2151
  __isl_take isl_set *context)
2152
0
{
2153
0
  isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
2154
0
  dom_context = isl_set_intersect_params(dom_context, context);
2155
0
  return isl_aff_gist(aff, dom_context);
2156
0
}
2157
2158
/* Return a basic set containing those elements in the space
2159
 * of aff where it is positive.  "rational" should not be set.
2160
 *
2161
 * If "aff" is NaN, then it is not positive.
2162
 */
2163
static __isl_give isl_basic_set *aff_pos_basic_set(__isl_take isl_aff *aff,
2164
  int rational)
2165
102
{
2166
102
  isl_constraint *ineq;
2167
102
  isl_basic_set *bset;
2168
102
  isl_val *c;
2169
102
2170
102
  if (!aff)
2171
0
    return NULL;
2172
102
  
if (102
isl_aff_is_nan(aff)102
)
{0
2173
0
    isl_space *space = isl_aff_get_domain_space(aff);
2174
0
    isl_aff_free(aff);
2175
0
    return isl_basic_set_empty(space);
2176
0
  }
2177
102
  
if (102
rational102
)
2178
0
    isl_die(isl_aff_get_ctx(aff), isl_error_unsupported,
2179
102
      "rational sets not supported", goto error);
2180
102
2181
102
  ineq = isl_inequality_from_aff(aff);
2182
102
  c = isl_constraint_get_constant_val(ineq);
2183
102
  c = isl_val_sub_ui(c, 1);
2184
102
  ineq = isl_constraint_set_constant_val(ineq, c);
2185
102
2186
102
  bset = isl_basic_set_from_constraint(ineq);
2187
102
  bset = isl_basic_set_simplify(bset);
2188
102
  return bset;
2189
0
error:
2190
0
  isl_aff_free(aff);
2191
0
  return NULL;
2192
102
}
2193
2194
/* Return a basic set containing those elements in the space
2195
 * of aff where it is non-negative.
2196
 * If "rational" is set, then return a rational basic set.
2197
 *
2198
 * If "aff" is NaN, then it is not non-negative (it's not negative either).
2199
 */
2200
static __isl_give isl_basic_set *aff_nonneg_basic_set(
2201
  __isl_take isl_aff *aff, int rational)
2202
14.1k
{
2203
14.1k
  isl_constraint *ineq;
2204
14.1k
  isl_basic_set *bset;
2205
14.1k
2206
14.1k
  if (!aff)
2207
0
    return NULL;
2208
14.1k
  
if (14.1k
isl_aff_is_nan(aff)14.1k
)
{0
2209
0
    isl_space *space = isl_aff_get_domain_space(aff);
2210
0
    isl_aff_free(aff);
2211
0
    return isl_basic_set_empty(space);
2212
0
  }
2213
14.1k
2214
14.1k
  ineq = isl_inequality_from_aff(aff);
2215
14.1k
2216
14.1k
  bset = isl_basic_set_from_constraint(ineq);
2217
14.1k
  if (rational)
2218
24
    bset = isl_basic_set_set_rational(bset);
2219
14.1k
  bset = isl_basic_set_simplify(bset);
2220
14.1k
  return bset;
2221
14.1k
}
2222
2223
/* Return a basic set containing those elements in the space
2224
 * of aff where it is non-negative.
2225
 */
2226
__isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
2227
222
{
2228
222
  return aff_nonneg_basic_set(aff, 0);
2229
222
}
2230
2231
/* Return a basic set containing those elements in the domain space
2232
 * of "aff" where it is positive.
2233
 */
2234
__isl_give isl_basic_set *isl_aff_pos_basic_set(__isl_take isl_aff *aff)
2235
61
{
2236
61
  aff = isl_aff_add_constant_num_si(aff, -1);
2237
61
  return isl_aff_nonneg_basic_set(aff);
2238
61
}
2239
2240
/* Return a basic set containing those elements in the domain space
2241
 * of aff where it is negative.
2242
 */
2243
__isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff)
2244
61
{
2245
61
  aff = isl_aff_neg(aff);
2246
61
  return isl_aff_pos_basic_set(aff);
2247
61
}
2248
2249
/* Return a basic set containing those elements in the space
2250
 * of aff where it is zero.
2251
 * If "rational" is set, then return a rational basic set.
2252
 *
2253
 * If "aff" is NaN, then it is not zero.
2254
 */
2255
static __isl_give isl_basic_set *aff_zero_basic_set(__isl_take isl_aff *aff,
2256
  int rational)
2257
7.07k
{
2258
7.07k
  isl_constraint *ineq;
2259
7.07k
  isl_basic_set *bset;
2260
7.07k
2261
7.07k
  if (!aff)
2262
0
    return NULL;
2263
7.07k
  
if (7.07k
isl_aff_is_nan(aff)7.07k
)
{0
2264
0
    isl_space *space = isl_aff_get_domain_space(aff);
2265
0
    isl_aff_free(aff);
2266
0
    return isl_basic_set_empty(space);
2267
0
  }
2268
7.07k
2269
7.07k
  ineq = isl_equality_from_aff(aff);
2270
7.07k
2271
7.07k
  bset = isl_basic_set_from_constraint(ineq);
2272
7.07k
  if (rational)
2273
173
    bset = isl_basic_set_set_rational(bset);
2274
7.07k
  bset = isl_basic_set_simplify(bset);
2275
7.07k
  return bset;
2276
7.07k
}
2277
2278
/* Return a basic set containing those elements in the space
2279
 * of aff where it is zero.
2280
 */
2281
__isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
2282
70
{
2283
70
  return aff_zero_basic_set(aff, 0);
2284
70
}
2285
2286
/* Return a basic set containing those elements in the shared space
2287
 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
2288
 */
2289
__isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
2290
  __isl_take isl_aff *aff2)
2291
161
{
2292
161
  aff1 = isl_aff_sub(aff1, aff2);
2293
161
2294
161
  return isl_aff_nonneg_basic_set(aff1);
2295
161
}
2296
2297
/* Return a basic set containing those elements in the shared domain space
2298
 * of "aff1" and "aff2" where "aff1" is greater than "aff2".
2299
 */
2300
__isl_give isl_basic_set *isl_aff_gt_basic_set(__isl_take isl_aff *aff1,
2301
  __isl_take isl_aff *aff2)
2302
0
{
2303
0
  aff1 = isl_aff_sub(aff1, aff2);
2304
0
2305
0
  return isl_aff_pos_basic_set(aff1);
2306
0
}
2307
2308
/* Return a set containing those elements in the shared space
2309
 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
2310
 */
2311
__isl_give isl_set *isl_aff_ge_set(__isl_take isl_aff *aff1,
2312
  __isl_take isl_aff *aff2)
2313
79
{
2314
79
  return isl_set_from_basic_set(isl_aff_ge_basic_set(aff1, aff2));
2315
79
}
2316
2317
/* Return a basic 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_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
2321
  __isl_take isl_aff *aff2)
2322
36
{
2323
36
  return isl_aff_ge_basic_set(aff2, aff1);
2324
36
}
2325
2326
/* Return a basic 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_basic_set *isl_aff_lt_basic_set(__isl_take isl_aff *aff1,
2330
  __isl_take isl_aff *aff2)
2331
0
{
2332
0
  return isl_aff_gt_basic_set(aff2, aff1);
2333
0
}
2334
2335
/* Return a set containing those elements in the shared space
2336
 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
2337
 */
2338
__isl_give isl_set *isl_aff_le_set(__isl_take isl_aff *aff1,
2339
  __isl_take isl_aff *aff2)
2340
48
{
2341
48
  return isl_aff_ge_set(aff2, aff1);
2342
48
}
2343
2344
/* Return a set containing those elements in the shared domain space
2345
 * of "aff1" and "aff2" where "aff1" is smaller than "aff2".
2346
 */
2347
__isl_give isl_set *isl_aff_lt_set(__isl_take isl_aff *aff1,
2348
  __isl_take isl_aff *aff2)
2349
0
{
2350
0
  return isl_set_from_basic_set(isl_aff_lt_basic_set(aff1, aff2));
2351
0
}
2352
2353
/* Return a basic set containing those elements in the shared space
2354
 * of aff1 and aff2 where aff1 and aff2 are equal.
2355
 */
2356
__isl_give isl_basic_set *isl_aff_eq_basic_set(__isl_take isl_aff *aff1,
2357
  __isl_take isl_aff *aff2)
2358
34
{
2359
34
  aff1 = isl_aff_sub(aff1, aff2);
2360
34
2361
34
  return isl_aff_zero_basic_set(aff1);
2362
34
}
2363
2364
/* Return a set containing those elements in the shared space
2365
 * of aff1 and aff2 where aff1 and aff2 are equal.
2366
 */
2367
__isl_give isl_set *isl_aff_eq_set(__isl_take isl_aff *aff1,
2368
  __isl_take isl_aff *aff2)
2369
34
{
2370
34
  return isl_set_from_basic_set(isl_aff_eq_basic_set(aff1, aff2));
2371
34
}
2372
2373
__isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
2374
  __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
2375
0
{
2376
0
  aff1 = isl_aff_add(aff1, aff2);
2377
0
  aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
2378
0
  return aff1;
2379
0
}
2380
2381
int isl_aff_is_empty(__isl_keep isl_aff *aff)
2382
176k
{
2383
176k
  if (!aff)
2384
0
    return -1;
2385
176k
2386
176k
  return 0;
2387
176k
}
2388
2389
/* Check whether the given affine expression has non-zero coefficient
2390
 * for any dimension in the given range or if any of these dimensions
2391
 * appear with non-zero coefficients in any of the integer divisions
2392
 * involved in the affine expression.
2393
 */
2394
isl_bool isl_aff_involves_dims(__isl_keep isl_aff *aff,
2395
  enum isl_dim_type type, unsigned first, unsigned n)
2396
7.96k
{
2397
7.96k
  int i;
2398
7.96k
  isl_ctx *ctx;
2399
7.96k
  int *active = NULL;
2400
7.96k
  isl_bool involves = isl_bool_false;
2401
7.96k
2402
7.96k
  if (!aff)
2403
0
    return isl_bool_error;
2404
7.96k
  
if (7.96k
n == 07.96k
)
2405
0
    return isl_bool_false;
2406
7.96k
2407
7.96k
  ctx = isl_aff_get_ctx(aff);
2408
7.96k
  if (first + n > isl_aff_dim(aff, type))
2409
0
    isl_die(ctx, isl_error_invalid,
2410
7.96k
      "range out of bounds", return isl_bool_error);
2411
7.96k
2412
7.96k
  active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
2413
7.96k
  if (!active)
2414
0
    goto error;
2415
7.96k
2416
7.96k
  first += isl_local_space_offset(aff->ls, type) - 1;
2417
13.2k
  for (i = 0; 
i < n13.2k
;
++i5.26k
)
2418
8.05k
    
if (8.05k
active[first + i]8.05k
)
{2.79k
2419
2.79k
      involves = isl_bool_true;
2420
2.79k
      break;
2421
2.79k
    }
2422
7.96k
2423
7.96k
  free(active);
2424
7.96k
2425
7.96k
  return involves;
2426
0
error:
2427
0
  free(active);
2428
0
  return isl_bool_error;
2429
7.96k
}
2430
2431
__isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
2432
  enum isl_dim_type type, unsigned first, unsigned n)
2433
361
{
2434
361
  isl_ctx *ctx;
2435
361
2436
361
  if (!aff)
2437
0
    return NULL;
2438
361
  
if (361
type == isl_dim_out361
)
2439
0
    isl_die(aff->v->ctx, isl_error_invalid,
2440
361
      "cannot drop output/set dimension",
2441
361
      return isl_aff_free(aff));
2442
361
  
if (361
type == isl_dim_in361
)
2443
361
    type = isl_dim_set;
2444
361
  if (
n == 0 && 361
!isl_local_space_is_named_or_nested(aff->ls, type)0
)
2445
0
    return aff;
2446
361
2447
361
  ctx = isl_aff_get_ctx(aff);
2448
361
  if (first + n > isl_local_space_dim(aff->ls, type))
2449
0
    isl_die(ctx, isl_error_invalid, "range out of bounds",
2450
361
      return isl_aff_free(aff));
2451
361
2452
361
  aff = isl_aff_cow(aff);
2453
361
  if (!aff)
2454
0
    return NULL;
2455
361
2456
361
  aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
2457
361
  if (!aff->ls)
2458
0
    return isl_aff_free(aff);
2459
361
2460
361
  first += 1 + isl_local_space_offset(aff->ls, type);
2461
361
  aff->v = isl_vec_drop_els(aff->v, first, n);
2462
361
  if (!aff->v)
2463
0
    return isl_aff_free(aff);
2464
361
2465
361
  return aff;
2466
361
}
2467
2468
/* Project the domain of the affine expression onto its parameter space.
2469
 * The affine expression may not involve any of the domain dimensions.
2470
 */
2471
__isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
2472
0
{
2473
0
  isl_space *space;
2474
0
  unsigned n;
2475
0
  int involves;
2476
0
2477
0
  n = isl_aff_dim(aff, isl_dim_in);
2478
0
  involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
2479
0
  if (involves < 0)
2480
0
    return isl_aff_free(aff);
2481
0
  
if (0
involves0
)
2482
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2483
0
        "affine expression involves some of the domain dimensions",
2484
0
        return isl_aff_free(aff));
2485
0
  aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
2486
0
  space = isl_aff_get_domain_space(aff);
2487
0
  space = isl_space_params(space);
2488
0
  aff = isl_aff_reset_domain_space(aff, space);
2489
0
  return aff;
2490
0
}
2491
2492
__isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
2493
  enum isl_dim_type type, unsigned first, unsigned n)
2494
6.38k
{
2495
6.38k
  isl_ctx *ctx;
2496
6.38k
2497
6.38k
  if (!aff)
2498
0
    return NULL;
2499
6.38k
  
if (6.38k
type == isl_dim_out6.38k
)
2500
0
    isl_die(aff->v->ctx, isl_error_invalid,
2501
6.38k
      "cannot insert output/set dimensions",
2502
6.38k
      return isl_aff_free(aff));
2503
6.38k
  
if (6.38k
type == isl_dim_in6.38k
)
2504
6.38k
    type = isl_dim_set;
2505
6.38k
  if (
n == 0 && 6.38k
!isl_local_space_is_named_or_nested(aff->ls, type)1.49k
)
2506
1.49k
    return aff;
2507
6.38k
2508
4.88k
  ctx = isl_aff_get_ctx(aff);
2509
4.88k
  if (first > isl_local_space_dim(aff->ls, type))
2510
0
    isl_die(ctx, isl_error_invalid, "position out of bounds",
2511
4.88k
      return isl_aff_free(aff));
2512
4.88k
2513
4.88k
  aff = isl_aff_cow(aff);
2514
4.88k
  if (!aff)
2515
0
    return NULL;
2516
4.88k
2517
4.88k
  aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
2518
4.88k
  if (!aff->ls)
2519
0
    return isl_aff_free(aff);
2520
4.88k
2521
4.88k
  first += 1 + isl_local_space_offset(aff->ls, type);
2522
4.88k
  aff->v = isl_vec_insert_zero_els(aff->v, first, n);
2523
4.88k
  if (!aff->v)
2524
0
    return isl_aff_free(aff);
2525
4.88k
2526
4.88k
  return aff;
2527
4.88k
}
2528
2529
__isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
2530
  enum isl_dim_type type, unsigned n)
2531
0
{
2532
0
  unsigned pos;
2533
0
2534
0
  pos = isl_aff_dim(aff, type);
2535
0
2536
0
  return isl_aff_insert_dims(aff, type, pos, n);
2537
0
}
2538
2539
__isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
2540
  enum isl_dim_type type, unsigned n)
2541
2.80k
{
2542
2.80k
  unsigned pos;
2543
2.80k
2544
2.80k
  pos = isl_pw_aff_dim(pwaff, type);
2545
2.80k
2546
2.80k
  return isl_pw_aff_insert_dims(pwaff, type, pos, n);
2547
2.80k
}
2548
2549
/* Move the "n" dimensions of "src_type" starting at "src_pos" of "aff"
2550
 * to dimensions of "dst_type" at "dst_pos".
2551
 *
2552
 * We only support moving input dimensions to parameters and vice versa.
2553
 */
2554
__isl_give isl_aff *isl_aff_move_dims(__isl_take isl_aff *aff,
2555
  enum isl_dim_type dst_type, unsigned dst_pos,
2556
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2557
0
{
2558
0
  unsigned g_dst_pos;
2559
0
  unsigned g_src_pos;
2560
0
2561
0
  if (!aff)
2562
0
    return NULL;
2563
0
  
if (0
n == 0 &&0
2564
0
      !isl_local_space_is_named_or_nested(aff->ls, src_type) &&
2565
0
      !isl_local_space_is_named_or_nested(aff->ls, dst_type))
2566
0
    return aff;
2567
0
2568
0
  
if (0
dst_type == isl_dim_out || 0
src_type == isl_dim_out0
)
2569
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2570
0
      "cannot move output/set dimension",
2571
0
      return isl_aff_free(aff));
2572
0
  
if (0
dst_type == isl_dim_div || 0
src_type == isl_dim_div0
)
2573
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2574
0
      "cannot move divs", return isl_aff_free(aff));
2575
0
  
if (0
dst_type == isl_dim_in0
)
2576
0
    dst_type = isl_dim_set;
2577
0
  if (src_type == isl_dim_in)
2578
0
    src_type = isl_dim_set;
2579
0
2580
0
  if (src_pos + n > isl_local_space_dim(aff->ls, src_type))
2581
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2582
0
      "range out of bounds", return isl_aff_free(aff));
2583
0
  
if (0
dst_type == src_type0
)
2584
0
    isl_die(isl_aff_get_ctx(aff), isl_error_unsupported,
2585
0
      "moving dims within the same type not supported",
2586
0
      return isl_aff_free(aff));
2587
0
2588
0
  aff = isl_aff_cow(aff);
2589
0
  if (!aff)
2590
0
    return NULL;
2591
0
2592
0
  g_src_pos = 1 + isl_local_space_offset(aff->ls, src_type) + src_pos;
2593
0
  g_dst_pos = 1 + isl_local_space_offset(aff->ls, dst_type) + dst_pos;
2594
0
  if (dst_type > src_type)
2595
0
    g_dst_pos -= n;
2596
0
2597
0
  aff->v = isl_vec_move_els(aff->v, g_dst_pos, g_src_pos, n);
2598
0
  aff->ls = isl_local_space_move_dims(aff->ls, dst_type, dst_pos,
2599
0
            src_type, src_pos, n);
2600
0
  if (
!aff->v || 0
!aff->ls0
)
2601
0
    return isl_aff_free(aff);
2602
0
2603
0
  aff = sort_divs(aff);
2604
0
2605
0
  return aff;
2606
0
}
2607
2608
__isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
2609
51.8k
{
2610
51.8k
  isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
2611
51.8k
  return isl_pw_aff_alloc(dom, aff);
2612
51.8k
}
2613
2614
1.44k
#define isl_aff_involves_nan isl_aff_is_nan
2615
2616
#undef PW
2617
167k
#define PW isl_pw_aff
2618
#undef EL
2619
69.2k
#define EL isl_aff
2620
#undef EL_IS_ZERO
2621
#define EL_IS_ZERO is_empty
2622
#undef ZERO
2623
#define ZERO empty
2624
#undef IS_ZERO
2625
#define IS_ZERO is_empty
2626
#undef FIELD
2627
870k
#define FIELD aff
2628
#undef DEFAULT_IS_ZERO
2629
4.32k
#define DEFAULT_IS_ZERO 0
2630
2631
#define NO_EVAL
2632
#define NO_OPT
2633
#define NO_LIFT
2634
#define NO_MORPH
2635
2636
#include <isl_pw_templ.c>
2637
#include <isl_pw_hash.c>
2638
#include <isl_pw_union_opt.c>
2639
2640
#undef UNION
2641
3.63k
#define UNION isl_union_pw_aff
2642
#undef PART
2643
23.9k
#define PART isl_pw_aff
2644
#undef PARTS
2645
#define PARTS pw_aff
2646
2647
#include <isl_union_single.c>
2648
#include <isl_union_neg.c>
2649
2650
static __isl_give isl_set *align_params_pw_pw_set_and(
2651
  __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
2652
  __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
2653
            __isl_take isl_pw_aff *pwaff2))
2654
17.9k
{
2655
17.9k
  isl_bool equal_params;
2656
17.9k
2657
17.9k
  if (
!pwaff1 || 17.9k
!pwaff217.9k
)
2658
0
    goto error;
2659
17.9k
  equal_params = isl_space_has_equal_params(pwaff1->dim, pwaff2->dim);
2660
17.9k
  if (equal_params < 0)
2661
0
    goto error;
2662
17.9k
  
if (17.9k
equal_params17.9k
)
2663
16.6k
    return fn(pwaff1, pwaff2);
2664
1.27k
  
if (1.27k
!isl_space_has_named_params(pwaff1->dim) ||1.27k
2665
1.27k
      !isl_space_has_named_params(pwaff2->dim))
2666
0
    isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
2667
1.27k
      "unaligned unnamed parameters", goto error);
2668
1.27k
  pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
2669
1.27k
  pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
2670
1.27k
  return fn(pwaff1, pwaff2);
2671
0
error:
2672
0
  isl_pw_aff_free(pwaff1);
2673
0
  isl_pw_aff_free(pwaff2);
2674
0
  return NULL;
2675
1.27k
}
2676
2677
/* Align the parameters of the to isl_pw_aff arguments and
2678
 * then apply a function "fn" on them that returns an isl_map.
2679
 */
2680
static __isl_give isl_map *align_params_pw_pw_map_and(
2681
  __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2,
2682
  __isl_give isl_map *(*fn)(__isl_take isl_pw_aff *pa1,
2683
            __isl_take isl_pw_aff *pa2))
2684
0
{
2685
0
  isl_bool equal_params;
2686
0
2687
0
  if (
!pa1 || 0
!pa20
)
2688
0
    goto error;
2689
0
  equal_params = isl_space_has_equal_params(pa1->dim, pa2->dim);
2690
0
  if (equal_params < 0)
2691
0
    goto error;
2692
0
  
if (0
equal_params0
)
2693
0
    return fn(pa1, pa2);
2694
0
  
if (0
!isl_space_has_named_params(pa1->dim) ||0
2695
0
      !isl_space_has_named_params(pa2->dim))
2696
0
    isl_die(isl_pw_aff_get_ctx(pa1), isl_error_invalid,
2697
0
      "unaligned unnamed parameters", goto error);
2698
0
  pa1 = isl_pw_aff_align_params(pa1, isl_pw_aff_get_space(pa2));
2699
0
  pa2 = isl_pw_aff_align_params(pa2, isl_pw_aff_get_space(pa1));
2700
0
  return fn(pa1, pa2);
2701
0
error:
2702
0
  isl_pw_aff_free(pa1);
2703
0
  isl_pw_aff_free(pa2);
2704
0
  return NULL;
2705
0
}
2706
2707
/* Compute a piecewise quasi-affine expression with a domain that
2708
 * is the union of those of pwaff1 and pwaff2 and such that on each
2709
 * cell, the quasi-affine expression is the maximum of those of pwaff1
2710
 * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
2711
 * cell, then the associated expression is the defined one.
2712
 */
2713
static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
2714
  __isl_take isl_pw_aff *pwaff2)
2715
33
{
2716
33
  return isl_pw_aff_union_opt_cmp(pwaff1, pwaff2, &isl_aff_ge_set);
2717
33
}
2718
2719
__isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
2720
  __isl_take isl_pw_aff *pwaff2)
2721
33
{
2722
33
  return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
2723
33
              &pw_aff_union_max);
2724
33
}
2725
2726
/* Compute a piecewise quasi-affine expression with a domain that
2727
 * is the union of those of pwaff1 and pwaff2 and such that on each
2728
 * cell, the quasi-affine expression is the minimum of those of pwaff1
2729
 * and pwaff2.  If only one of pwaff1 or pwaff2 is defined on a given
2730
 * cell, then the associated expression is the defined one.
2731
 */
2732
static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
2733
  __isl_take isl_pw_aff *pwaff2)
2734
42
{
2735
42
  return isl_pw_aff_union_opt_cmp(pwaff1, pwaff2, &isl_aff_le_set);
2736
42
}
2737
2738
__isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
2739
  __isl_take isl_pw_aff *pwaff2)
2740
42
{
2741
42
  return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
2742
42
              &pw_aff_union_min);
2743
42
}
2744
2745
__isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
2746
  __isl_take isl_pw_aff *pwaff2, int max)
2747
75
{
2748
75
  if (max)
2749
33
    return isl_pw_aff_union_max(pwaff1, pwaff2);
2750
75
  else
2751
42
    return isl_pw_aff_union_min(pwaff1, pwaff2);
2752
75
}
2753
2754
/* Construct a map with as domain the domain of pwaff and
2755
 * one-dimensional range corresponding to the affine expressions.
2756
 */
2757
static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2758
11.5k
{
2759
11.5k
  int i;
2760
11.5k
  isl_space *dim;
2761
11.5k
  isl_map *map;
2762
11.5k
2763
11.5k
  if (!pwaff)
2764
0
    return NULL;
2765
11.5k
2766
11.5k
  dim = isl_pw_aff_get_space(pwaff);
2767
11.5k
  map = isl_map_empty(dim);
2768
11.5k
2769
23.1k
  for (i = 0; 
i < pwaff->n23.1k
;
++i11.6k
)
{11.6k
2770
11.6k
    isl_basic_map *bmap;
2771
11.6k
    isl_map *map_i;
2772
11.6k
2773
11.6k
    bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
2774
11.6k
    map_i = isl_map_from_basic_map(bmap);
2775
11.6k
    map_i = isl_map_intersect_domain(map_i,
2776
11.6k
            isl_set_copy(pwaff->p[i].set));
2777
11.6k
    map = isl_map_union_disjoint(map, map_i);
2778
11.6k
  }
2779
11.5k
2780
11.5k
  isl_pw_aff_free(pwaff);
2781
11.5k
2782
11.5k
  return map;
2783
11.5k
}
2784
2785
/* Construct a map with as domain the domain of pwaff and
2786
 * one-dimensional range corresponding to the affine expressions.
2787
 */
2788
__isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2789
11.5k
{
2790
11.5k
  if (!pwaff)
2791
0
    return NULL;
2792
11.5k
  
if (11.5k
isl_space_is_set(pwaff->dim)11.5k
)
2793
0
    isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
2794
11.5k
      "space of input is not a map", goto error);
2795
11.5k
  return map_from_pw_aff(pwaff);
2796
0
error:
2797
0
  isl_pw_aff_free(pwaff);
2798
0
  return NULL;
2799
11.5k
}
2800
2801
/* Construct a one-dimensional set with as parameter domain
2802
 * the domain of pwaff and the single set dimension
2803
 * corresponding to the affine expressions.
2804
 */
2805
__isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2806
7
{
2807
7
  if (!pwaff)
2808
0
    return NULL;
2809
7
  
if (7
!isl_space_is_set(pwaff->dim)7
)
2810
0
    isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
2811
7
      "space of input is not a set", goto error);
2812
7
  return map_from_pw_aff(pwaff);
2813
0
error:
2814
0
  isl_pw_aff_free(pwaff);
2815
0
  return NULL;
2816
7
}
2817
2818
/* Return a set containing those elements in the domain
2819
 * of "pwaff" where it satisfies "fn" (if complement is 0) or
2820
 * does not satisfy "fn" (if complement is 1).
2821
 *
2822
 * The pieces with a NaN never belong to the result since
2823
 * NaN does not satisfy any property.
2824
 */
2825
static __isl_give isl_set *pw_aff_locus(__isl_take isl_pw_aff *pwaff,
2826
  __isl_give isl_basic_set *(*fn)(__isl_take isl_aff *aff, int rational),
2827
  int complement)
2828
20.2k
{
2829
20.2k
  int i;
2830
20.2k
  isl_set *set;
2831
20.2k
2832
20.2k
  if (!pwaff)
2833
0
    return NULL;
2834
20.2k
2835
20.2k
  set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
2836
20.2k
2837
41.2k
  for (i = 0; 
i < pwaff->n41.2k
;
++i20.9k
)
{20.9k
2838
20.9k
    isl_basic_set *bset;
2839
20.9k
    isl_set *set_i, *locus;
2840
20.9k
    isl_bool rational;
2841
20.9k
2842
20.9k
    if (isl_aff_is_nan(pwaff->p[i].aff))
2843
0
      continue;
2844
20.9k
2845
20.9k
    rational = isl_set_has_rational(pwaff->p[i].set);
2846
20.9k
    bset = fn(isl_aff_copy(pwaff->p[i].aff), rational);
2847
20.9k
    locus = isl_set_from_basic_set(bset);
2848
20.9k
    set_i = isl_set_copy(pwaff->p[i].set);
2849
20.9k
    if (complement)
2850
100
      set_i = isl_set_subtract(set_i, locus);
2851
20.9k
    else
2852
20.8k
      set_i = isl_set_intersect(set_i, locus);
2853
20.9k
    set = isl_set_union_disjoint(set, set_i);
2854
20.9k
  }
2855
20.2k
2856
20.2k
  isl_pw_aff_free(pwaff);
2857
20.2k
2858
20.2k
  return set;
2859
20.2k
}
2860
2861
/* Return a set containing those elements in the domain
2862
 * of "pa" where it is positive.
2863
 */
2864
__isl_give isl_set *isl_pw_aff_pos_set(__isl_take isl_pw_aff *pa)
2865
94
{
2866
94
  return pw_aff_locus(pa, &aff_pos_basic_set, 0);
2867
94
}
2868
2869
/* Return a set containing those elements in the domain
2870
 * of pwaff where it is non-negative.
2871
 */
2872
__isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
2873
13.3k
{
2874
13.3k
  return pw_aff_locus(pwaff, &aff_nonneg_basic_set, 0);
2875
13.3k
}
2876
2877
/* Return a set containing those elements in the domain
2878
 * of pwaff where it is zero.
2879
 */
2880
__isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
2881
6.78k
{
2882
6.78k
  return pw_aff_locus(pwaff, &aff_zero_basic_set, 0);
2883
6.78k
}
2884
2885
/* Return a set containing those elements in the domain
2886
 * of pwaff where it is not zero.
2887
 */
2888
__isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
2889
58
{
2890
58
  return pw_aff_locus(pwaff, &aff_zero_basic_set, 1);
2891
58
}
2892
2893
/* Return a set containing those elements in the shared domain
2894
 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2895
 *
2896
 * We compute the difference on the shared domain and then construct
2897
 * the set of values where this difference is non-negative.
2898
 * If strict is set, we first subtract 1 from the difference.
2899
 * If equal is set, we only return the elements where pwaff1 and pwaff2
2900
 * are equal.
2901
 */
2902
static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
2903
  __isl_take isl_pw_aff *pwaff2, int strict, int equal)
2904
14.3k
{
2905
14.3k
  isl_set *set1, *set2;
2906
14.3k
2907
14.3k
  set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
2908
14.3k
  set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
2909
14.3k
  set1 = isl_set_intersect(set1, set2);
2910
14.3k
  pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
2911
14.3k
  pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
2912
14.3k
  pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
2913
14.3k
2914
14.3k
  if (
strict14.3k
)
{8.63k
2915
8.63k
    isl_space *dim = isl_set_get_space(set1);
2916
8.63k
    isl_aff *aff;
2917
8.63k
    aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2918
8.63k
    aff = isl_aff_add_constant_si(aff, -1);
2919
8.63k
    pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
2920
8.63k
  } else
2921
5.71k
    isl_set_free(set1);
2922
14.3k
2923
14.3k
  if (equal)
2924
1.06k
    return isl_pw_aff_zero_set(pwaff1);
2925
13.2k
  return isl_pw_aff_nonneg_set(pwaff1);
2926
14.3k
}
2927
2928
/* Return a set containing those elements in the shared domain
2929
 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2930
 */
2931
static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
2932
  __isl_take isl_pw_aff *pwaff2)
2933
1.06k
{
2934
1.06k
  return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
2935
1.06k
}
2936
2937
__isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
2938
  __isl_take isl_pw_aff *pwaff2)
2939
1.06k
{
2940
1.06k
  return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
2941
1.06k
}
2942
2943
/* Return a set containing those elements in the shared domain
2944
 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2945
 */
2946
static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
2947
  __isl_take isl_pw_aff *pwaff2)
2948
4.65k
{
2949
4.65k
  return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
2950
4.65k
}
2951
2952
__isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
2953
  __isl_take isl_pw_aff *pwaff2)
2954
4.65k
{
2955
4.65k
  return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
2956
4.65k
}
2957
2958
/* Return a set containing those elements in the shared domain
2959
 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2960
 */
2961
static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
2962
  __isl_take isl_pw_aff *pwaff2)
2963
8.63k
{
2964
8.63k
  return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
2965
8.63k
}
2966
2967
__isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
2968
  __isl_take isl_pw_aff *pwaff2)
2969
8.63k
{
2970
8.63k
  return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
2971
8.63k
}
2972
2973
__isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
2974
  __isl_take isl_pw_aff *pwaff2)
2975
3.45k
{
2976
3.45k
  return isl_pw_aff_ge_set(pwaff2, pwaff1);
2977
3.45k
}
2978
2979
__isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
2980
  __isl_take isl_pw_aff *pwaff2)
2981
4.89k
{
2982
4.89k
  return isl_pw_aff_gt_set(pwaff2, pwaff1);
2983
4.89k
}
2984
2985
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
2986
 * where the function values are ordered in the same way as "order",
2987
 * which returns a set in the shared domain of its two arguments.
2988
 * The parameters of "pa1" and "pa2" are assumed to have been aligned.
2989
 *
2990
 * Let "pa1" and "pa2" be defined on domains A and B respectively.
2991
 * We first pull back the two functions such that they are defined on
2992
 * the domain [A -> B].  Then we apply "order", resulting in a set
2993
 * in the space [A -> B].  Finally, we unwrap this set to obtain
2994
 * a map in the space A -> B.
2995
 */
2996
static __isl_give isl_map *isl_pw_aff_order_map_aligned(
2997
  __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2,
2998
  __isl_give isl_set *(*order)(__isl_take isl_pw_aff *pa1,
2999
    __isl_take isl_pw_aff *pa2))
3000
0
{
3001
0
  isl_space *space1, *space2;
3002
0
  isl_multi_aff *ma;
3003
0
  isl_set *set;
3004
0
3005
0
  space1 = isl_space_domain(isl_pw_aff_get_space(pa1));
3006
0
  space2 = isl_space_domain(isl_pw_aff_get_space(pa2));
3007
0
  space1 = isl_space_map_from_domain_and_range(space1, space2);
3008
0
  ma = isl_multi_aff_domain_map(isl_space_copy(space1));
3009
0
  pa1 = isl_pw_aff_pullback_multi_aff(pa1, ma);
3010
0
  ma = isl_multi_aff_range_map(space1);
3011
0
  pa2 = isl_pw_aff_pullback_multi_aff(pa2, ma);
3012
0
  set = order(pa1, pa2);
3013
0
3014
0
  return isl_set_unwrap(set);
3015
0
}
3016
3017
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3018
 * where the function values are equal.
3019
 * The parameters of "pa1" and "pa2" are assumed to have been aligned.
3020
 */
3021
static __isl_give isl_map *isl_pw_aff_eq_map_aligned(__isl_take isl_pw_aff *pa1,
3022
  __isl_take isl_pw_aff *pa2)
3023
0
{
3024
0
  return isl_pw_aff_order_map_aligned(pa1, pa2, &isl_pw_aff_eq_set);
3025
0
}
3026
3027
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3028
 * where the function values are equal.
3029
 */
3030
__isl_give isl_map *isl_pw_aff_eq_map(__isl_take isl_pw_aff *pa1,
3031
  __isl_take isl_pw_aff *pa2)
3032
0
{
3033
0
  return align_params_pw_pw_map_and(pa1, pa2, &isl_pw_aff_eq_map_aligned);
3034
0
}
3035
3036
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3037
 * where the function value of "pa1" is less than the function value of "pa2".
3038
 * The parameters of "pa1" and "pa2" are assumed to have been aligned.
3039
 */
3040
static __isl_give isl_map *isl_pw_aff_lt_map_aligned(__isl_take isl_pw_aff *pa1,
3041
  __isl_take isl_pw_aff *pa2)
3042
0
{
3043
0
  return isl_pw_aff_order_map_aligned(pa1, pa2, &isl_pw_aff_lt_set);
3044
0
}
3045
3046
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3047
 * where the function value of "pa1" is less than the function value of "pa2".
3048
 */
3049
__isl_give isl_map *isl_pw_aff_lt_map(__isl_take isl_pw_aff *pa1,
3050
  __isl_take isl_pw_aff *pa2)
3051
0
{
3052
0
  return align_params_pw_pw_map_and(pa1, pa2, &isl_pw_aff_lt_map_aligned);
3053
0
}
3054
3055
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3056
 * where the function value of "pa1" is greater than the function value
3057
 * of "pa2".
3058
 * The parameters of "pa1" and "pa2" are assumed to have been aligned.
3059
 */
3060
static __isl_give isl_map *isl_pw_aff_gt_map_aligned(__isl_take isl_pw_aff *pa1,
3061
  __isl_take isl_pw_aff *pa2)
3062
0
{
3063
0
  return isl_pw_aff_order_map_aligned(pa1, pa2, &isl_pw_aff_gt_set);
3064
0
}
3065
3066
/* Return a map containing pairs of elements in the domains of "pa1" and "pa2"
3067
 * where the function value of "pa1" is greater than the function value
3068
 * of "pa2".
3069
 */
3070
__isl_give isl_map *isl_pw_aff_gt_map(__isl_take isl_pw_aff *pa1,
3071
  __isl_take isl_pw_aff *pa2)
3072
0
{
3073
0
  return align_params_pw_pw_map_and(pa1, pa2, &isl_pw_aff_gt_map_aligned);
3074
0
}
3075
3076
/* Return a set containing those elements in the shared domain
3077
 * of the elements of list1 and list2 where each element in list1
3078
 * has the relation specified by "fn" with each element in list2.
3079
 */
3080
static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
3081
  __isl_take isl_pw_aff_list *list2,
3082
  __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
3083
            __isl_take isl_pw_aff *pwaff2))
3084
4.70k
{
3085
4.70k
  int i, j;
3086
4.70k
  isl_ctx *ctx;
3087
4.70k
  isl_set *set;
3088
4.70k
3089
4.70k
  if (
!list1 || 4.70k
!list24.70k
)
3090
0
    goto error;
3091
4.70k
3092
4.70k
  ctx = isl_pw_aff_list_get_ctx(list1);
3093
4.70k
  if (
list1->n < 1 || 4.70k
list2->n < 14.70k
)
3094
0
    isl_die(ctx, isl_error_invalid,
3095
4.70k
      "list should contain at least one element", goto error);
3096
4.70k
3097
4.70k
  set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
3098
9.50k
  for (i = 0; 
i < list1->n9.50k
;
++i4.80k
)
3099
9.77k
    
for (j = 0; 4.80k
j < list2->n9.77k
;
++j4.96k
)
{4.96k
3100
4.96k
      isl_set *set_ij;
3101
4.96k
3102
4.96k
      set_ij = fn(isl_pw_aff_copy(list1->p[i]),
3103
4.96k
            isl_pw_aff_copy(list2->p[j]));
3104
4.96k
      set = isl_set_intersect(set, set_ij);
3105
4.96k
    }
3106
4.70k
3107
4.70k
  isl_pw_aff_list_free(list1);
3108
4.70k
  isl_pw_aff_list_free(list2);
3109
4.70k
  return set;
3110
0
error:
3111
0
  isl_pw_aff_list_free(list1);
3112
0
  isl_pw_aff_list_free(list2);
3113
0
  return NULL;
3114
4.70k
}
3115
3116
/* Return a set containing those elements in the shared domain
3117
 * of the elements of list1 and list2 where each element in list1
3118
 * is equal to each element in list2.
3119
 */
3120
__isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
3121
  __isl_take isl_pw_aff_list *list2)
3122
493
{
3123
493
  return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
3124
493
}
3125
3126
__isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
3127
  __isl_take isl_pw_aff_list *list2)
3128
12
{
3129
12
  return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
3130
12
}
3131
3132
/* Return a set containing those elements in the shared domain
3133
 * of the elements of list1 and list2 where each element in list1
3134
 * is less than or equal to each element in list2.
3135
 */
3136
__isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
3137
  __isl_take isl_pw_aff_list *list2)
3138
2.73k
{
3139
2.73k
  return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
3140
2.73k
}
3141
3142
__isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
3143
  __isl_take isl_pw_aff_list *list2)
3144
315
{
3145
315
  return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
3146
315
}
3147
3148
__isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
3149
  __isl_take isl_pw_aff_list *list2)
3150
1.10k
{
3151
1.10k
  return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
3152
1.10k
}
3153
3154
__isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
3155
  __isl_take isl_pw_aff_list *list2)
3156
48
{
3157
48
  return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
3158
48
}
3159
3160
3161
/* Return a set containing those elements in the shared domain
3162
 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
3163
 */
3164
static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
3165
  __isl_take isl_pw_aff *pwaff2)
3166
3.57k
{
3167
3.57k
  isl_set *set_lt, *set_gt;
3168
3.57k
3169
3.57k
  set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
3170
3.57k
           isl_pw_aff_copy(pwaff2));
3171
3.57k
  set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
3172
3.57k
  return isl_set_union_disjoint(set_lt, set_gt);
3173
3.57k
}
3174
3175
__isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
3176
  __isl_take isl_pw_aff *pwaff2)
3177
3.57k
{
3178
3.57k
  return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
3179
3.57k
}
3180
3181
__isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
3182
  isl_int v)
3183
3.11k
{
3184
3.11k
  int i;
3185
3.11k
3186
3.11k
  if (isl_int_is_one(v))
3187
0
    return pwaff;
3188
3.11k
  
if (3.11k
!3.11k
isl_int_is_pos3.11k
(v))
3189
0
    isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
3190
3.11k
      "factor needs to be positive",
3191
3.11k
      return isl_pw_aff_free(pwaff));
3192
3.11k
  pwaff = isl_pw_aff_cow(pwaff);
3193
3.11k
  if (!pwaff)
3194
0
    return NULL;
3195
3.11k
  
if (3.11k
pwaff->n == 03.11k
)
3196
0
    return pwaff;
3197
3.11k
3198
6.42k
  
for (i = 0; 3.11k
i < pwaff->n6.42k
;
++i3.31k
)
{3.31k
3199
3.31k
    pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
3200
3.31k
    if (!pwaff->p[i].aff)
3201
0
      return isl_pw_aff_free(pwaff);
3202
3.31k
  }
3203
3.11k
3204
3.11k
  return pwaff;
3205
3.11k
}
3206
3207
__isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
3208
5.77k
{
3209
5.77k
  int i;
3210
5.77k
3211
5.77k
  pwaff = isl_pw_aff_cow(pwaff);
3212
5.77k
  if (!pwaff)
3213
0
    return NULL;
3214
5.77k
  
if (5.77k
pwaff->n == 05.77k
)
3215
0
    return pwaff;
3216
5.77k
3217
11.7k
  
for (i = 0; 5.77k
i < pwaff->n11.7k
;
++i5.99k
)
{5.99k
3218
5.99k
    pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
3219
5.99k
    if (!pwaff->p[i].aff)
3220
0
      return isl_pw_aff_free(pwaff);
3221
5.99k
  }
3222
5.77k
3223
5.77k
  return pwaff;
3224
5.77k
}
3225
3226
__isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
3227
63
{
3228
63
  int i;
3229
63
3230
63
  pwaff = isl_pw_aff_cow(pwaff);
3231
63
  if (!pwaff)
3232
0
    return NULL;
3233
63
  
if (63
pwaff->n == 063
)
3234
0
    return pwaff;
3235
63
3236
128
  
for (i = 0; 63
i < pwaff->n128
;
++i65
)
{65
3237
65
    pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
3238
65
    if (!pwaff->p[i].aff)
3239
0
      return isl_pw_aff_free(pwaff);
3240
65
  }
3241
63
3242
63
  return pwaff;
3243
63
}
3244
3245
/* Assuming that "cond1" and "cond2" are disjoint,
3246
 * return an affine expression that is equal to pwaff1 on cond1
3247
 * and to pwaff2 on cond2.
3248
 */
3249
static __isl_give isl_pw_aff *isl_pw_aff_select(
3250
  __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
3251
  __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
3252
125
{
3253
125
  pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
3254
125
  pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
3255
125
3256
125
  return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
3257
125
}
3258
3259
/* Return an affine expression that is equal to pwaff_true for elements
3260
 * where "cond" is non-zero and to pwaff_false for elements where "cond"
3261
 * is zero.
3262
 * That is, return cond ? pwaff_true : pwaff_false;
3263
 *
3264
 * If "cond" involves and NaN, then we conservatively return a NaN
3265
 * on its entire domain.  In principle, we could consider the pieces
3266
 * where it is NaN separately from those where it is not.
3267
 *
3268
 * If "pwaff_true" and "pwaff_false" are obviously equal to each other,
3269
 * then only use the domain of "cond" to restrict the domain.
3270
 */
3271
__isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
3272
  __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
3273
64
{
3274
64
  isl_set *cond_true, *cond_false;
3275
64
  isl_bool equal;
3276
64
3277
64
  if (!cond)
3278
0
    goto error;
3279
64
  
if (64
isl_pw_aff_involves_nan(cond)64
)
{0
3280
0
    isl_space *space = isl_pw_aff_get_domain_space(cond);
3281
0
    isl_local_space *ls = isl_local_space_from_space(space);
3282
0
    isl_pw_aff_free(cond);
3283
0
    isl_pw_aff_free(pwaff_true);
3284
0
    isl_pw_aff_free(pwaff_false);
3285
0
    return isl_pw_aff_nan_on_domain(ls);
3286
0
  }
3287
64
3288
64
  pwaff_true = isl_pw_aff_align_params(pwaff_true,
3289
64
              isl_pw_aff_get_space(pwaff_false));
3290
64
  pwaff_false = isl_pw_aff_align_params(pwaff_false,
3291
64
              isl_pw_aff_get_space(pwaff_true));
3292
64
  equal = isl_pw_aff_plain_is_equal(pwaff_true, pwaff_false);
3293
64
  if (equal < 0)
3294
0
    goto error;
3295
64
  
if (64
equal64
)
{6
3296
6
    isl_set *dom;
3297
6
3298
6
    dom = isl_set_coalesce(isl_pw_aff_domain(cond));
3299
6
    isl_pw_aff_free(pwaff_false);
3300
6
    return isl_pw_aff_intersect_domain(pwaff_true, dom);
3301
6
  }
3302
64
3303
58
  cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
3304
58
  cond_false = isl_pw_aff_zero_set(cond);
3305
58
  return isl_pw_aff_select(cond_true, pwaff_true,
3306
58
         cond_false, pwaff_false);
3307
0
error:
3308
0
  isl_pw_aff_free(cond);
3309
0
  isl_pw_aff_free(pwaff_true);
3310
0
  isl_pw_aff_free(pwaff_false);
3311
0
  return NULL;
3312
64
}
3313
3314
isl_bool isl_aff_is_cst(__isl_keep isl_aff *aff)
3315
34.1k
{
3316
34.1k
  if (!aff)
3317
0
    return isl_bool_error;
3318
34.1k
3319
34.1k
  return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
3320
34.1k
}
3321
3322
/* Check whether pwaff is a piecewise constant.
3323
 */
3324
isl_bool isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
3325
174
{
3326
174
  int i;
3327
174
3328
174
  if (!pwaff)
3329
0
    return isl_bool_error;
3330
174
3331
348
  
for (i = 0; 174
i < pwaff->n348
;
++i174
)
{174
3332
174
    isl_bool is_cst = isl_aff_is_cst(pwaff->p[i].aff);
3333
174
    if (
is_cst < 0 || 174
!is_cst174
)
3334
0
      return is_cst;
3335
174
  }
3336
174
3337
174
  return isl_bool_true;
3338
174
}
3339
3340
/* Are all elements of "mpa" piecewise constants?
3341
 */
3342
isl_bool isl_multi_pw_aff_is_cst(__isl_keep isl_multi_pw_aff *mpa)
3343
0
{
3344
0
  int i;
3345
0
3346
0
  if (!mpa)
3347
0
    return isl_bool_error;
3348
0
3349
0
  
for (i = 0; 0
i < mpa->n0
;
++i0
)
{0
3350
0
    isl_bool is_cst = isl_pw_aff_is_cst(mpa->p[i]);
3351
0
    if (
is_cst < 0 || 0
!is_cst0
)
3352
0
      return is_cst;
3353
0
  }
3354
0
3355
0
  return isl_bool_true;
3356
0
}
3357
3358
/* Return the product of "aff1" and "aff2".
3359
 *
3360
 * If either of the two is NaN, then the result is NaN.
3361
 *
3362
 * Otherwise, at least one of "aff1" or "aff2" needs to be a constant.
3363
 */
3364
__isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
3365
  __isl_take isl_aff *aff2)
3366
15.0k
{
3367
15.0k
  if (
!aff1 || 15.0k
!aff215.0k
)
3368
0
    goto error;
3369
15.0k
3370
15.0k
  
if (15.0k
isl_aff_is_nan(aff1)15.0k
)
{2
3371
2
    isl_aff_free(aff2);
3372
2
    return aff1;
3373
2
  }
3374
15.0k
  
if (15.0k
isl_aff_is_nan(aff2)15.0k
)
{2
3375
2
    isl_aff_free(aff1);
3376
2
    return aff2;
3377
2
  }
3378
15.0k
3379
15.0k
  
if (15.0k
!isl_aff_is_cst(aff2) && 15.0k
isl_aff_is_cst(aff1)2.54k
)
3380
2.54k
    return isl_aff_mul(aff2, aff1);
3381
15.0k
3382
12.5k
  
if (12.5k
!isl_aff_is_cst(aff2)12.5k
)
3383
0
    isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
3384
12.5k
      "at least one affine expression should be constant",
3385
12.5k
      goto error);
3386
12.5k
3387
12.5k
  aff1 = isl_aff_cow(aff1);
3388
12.5k
  if (
!aff1 || 12.5k
!aff212.5k
)
3389
0
    goto error;
3390
12.5k
3391
12.5k
  aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
3392
12.5k
  aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
3393
12.5k
3394
12.5k
  isl_aff_free(aff2);
3395
12.5k
  return aff1;
3396
0
error:
3397
0
  isl_aff_free(aff1);
3398
0
  isl_aff_free(aff2);
3399
0
  return NULL;
3400
12.5k
}
3401
3402
/* Divide "aff1" by "aff2", assuming "aff2" is a constant.
3403
 *
3404
 * If either of the two is NaN, then the result is NaN.
3405
 */
3406
__isl_give isl_aff *isl_aff_div(__isl_take isl_aff *aff1,
3407
  __isl_take isl_aff *aff2)
3408
99
{
3409
99
  int is_cst;
3410
99
  int neg;
3411
99
3412
99
  if (
!aff1 || 99
!aff299
)
3413
0
    goto error;
3414
99
3415
99
  
if (99
isl_aff_is_nan(aff1)99
)
{2
3416
2
    isl_aff_free(aff2);
3417
2
    return aff1;
3418
2
  }
3419
97
  
if (97
isl_aff_is_nan(aff2)97
)
{2
3420
2
    isl_aff_free(aff1);
3421
2
    return aff2;
3422
2
  }
3423
97
3424
95
  is_cst = isl_aff_is_cst(aff2);
3425
95
  if (is_cst < 0)
3426
0
    goto error;
3427
95
  
if (95
!is_cst95
)
3428
0
    isl_die(isl_aff_get_ctx(aff2), isl_error_invalid,
3429
95
      "second argument should be a constant", goto error);
3430
95
3431
95
  
if (95
!aff295
)
3432
0
    goto error;
3433
95
3434
95
  
neg = 95
isl_int_is_neg95
(aff2->v->el[1]);
3435
95
  if (
neg95
)
{13
3436
13
    isl_int_neg(aff2->v->el[0], aff2->v->el[0]);
3437
13
    isl_int_neg(aff2->v->el[1], aff2->v->el[1]);
3438
13
  }
3439
95
3440
95
  aff1 = isl_aff_scale(aff1, aff2->v->el[0]);
3441
95
  aff1 = isl_aff_scale_down(aff1, aff2->v->el[1]);
3442
95
3443
95
  if (
neg95
)
{13
3444
13
    isl_int_neg(aff2->v->el[0], aff2->v->el[0]);
3445
13
    isl_int_neg(aff2->v->el[1], aff2->v->el[1]);
3446
13
  }
3447
95
3448
95
  isl_aff_free(aff2);
3449
95
  return aff1;
3450
0
error:
3451
0
  isl_aff_free(aff1);
3452
0
  isl_aff_free(aff2);
3453
0
  return NULL;
3454
95
}
3455
3456
static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
3457
  __isl_take isl_pw_aff *pwaff2)
3458
51.7k
{
3459
51.7k
  return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
3460
51.7k
}
3461
3462
__isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
3463
  __isl_take isl_pw_aff *pwaff2)
3464
51.7k
{
3465
51.7k
  return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
3466
51.7k
}
3467
3468
__isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
3469
  __isl_take isl_pw_aff *pwaff2)
3470
2.47k
{
3471
2.47k
  return isl_pw_aff_union_add_(pwaff1, pwaff2);
3472
2.47k
}
3473
3474
static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
3475
  __isl_take isl_pw_aff *pwaff2)
3476
12.1k
{
3477
12.1k
  return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
3478
12.1k
}
3479
3480
__isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
3481
  __isl_take isl_pw_aff *pwaff2)
3482
12.1k
{
3483
12.1k
  return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
3484
12.1k
}
3485
3486
static __isl_give isl_pw_aff *pw_aff_div(__isl_take isl_pw_aff *pa1,
3487
  __isl_take isl_pw_aff *pa2)
3488
74
{
3489
74
  return isl_pw_aff_on_shared_domain(pa1, pa2, &isl_aff_div);
3490
74
}
3491
3492
/* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
3493
 */
3494
__isl_give isl_pw_aff *isl_pw_aff_div(__isl_take isl_pw_aff *pa1,
3495
  __isl_take isl_pw_aff *pa2)
3496
74
{
3497
74
  int is_cst;
3498
74
3499
74
  is_cst = isl_pw_aff_is_cst(pa2);
3500
74
  if (is_cst < 0)
3501
0
    goto error;
3502
74
  
if (74
!is_cst74
)
3503
0
    isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3504
74
      "second argument should be a piecewise constant",
3505
74
      goto error);
3506
74
  return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_div);
3507
0
error:
3508
0
  isl_pw_aff_free(pa1);
3509
0
  isl_pw_aff_free(pa2);
3510
0
  return NULL;
3511
74
}
3512
3513
/* Compute the quotient of the integer division of "pa1" by "pa2"
3514
 * with rounding towards zero.
3515
 * "pa2" is assumed to be a piecewise constant.
3516
 *
3517
 * In particular, return
3518
 *
3519
 *  pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
3520
 *
3521
 */
3522
__isl_give isl_pw_aff *isl_pw_aff_tdiv_q(__isl_take isl_pw_aff *pa1,
3523
  __isl_take isl_pw_aff *pa2)
3524
63
{
3525
63
  int is_cst;
3526
63
  isl_set *cond;
3527
63
  isl_pw_aff *f, *c;
3528
63
3529
63
  is_cst = isl_pw_aff_is_cst(pa2);
3530
63
  if (is_cst < 0)
3531
0
    goto error;
3532
63
  
if (63
!is_cst63
)
3533
0
    isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3534
63
      "second argument should be a piecewise constant",
3535
63
      goto error);
3536
63
3537
63
  pa1 = isl_pw_aff_div(pa1, pa2);
3538
63
3539
63
  cond = isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1));
3540
63
  f = isl_pw_aff_floor(isl_pw_aff_copy(pa1));
3541
63
  c = isl_pw_aff_ceil(pa1);
3542
63
  return isl_pw_aff_cond(isl_set_indicator_function(cond), f, c);
3543
0
error:
3544
0
  isl_pw_aff_free(pa1);
3545
0
  isl_pw_aff_free(pa2);
3546
0
  return NULL;
3547
63
}
3548
3549
/* Compute the remainder of the integer division of "pa1" by "pa2"
3550
 * with rounding towards zero.
3551
 * "pa2" is assumed to be a piecewise constant.
3552
 *
3553
 * In particular, return
3554
 *
3555
 *  pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
3556
 *
3557
 */
3558
__isl_give isl_pw_aff *isl_pw_aff_tdiv_r(__isl_take isl_pw_aff *pa1,
3559
  __isl_take isl_pw_aff *pa2)
3560
36
{
3561
36
  int is_cst;
3562
36
  isl_pw_aff *res;
3563
36
3564
36
  is_cst = isl_pw_aff_is_cst(pa2);
3565
36
  if (is_cst < 0)
3566
0
    goto error;
3567
36
  
if (36
!is_cst36
)
3568
0
    isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3569
36
      "second argument should be a piecewise constant",
3570
36
      goto error);
3571
36
  res = isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1), isl_pw_aff_copy(pa2));
3572
36
  res = isl_pw_aff_mul(pa2, res);
3573
36
  res = isl_pw_aff_sub(pa1, res);
3574
36
  return res;
3575
0
error:
3576
0
  isl_pw_aff_free(pa1);
3577
0
  isl_pw_aff_free(pa2);
3578
0
  return NULL;
3579
36
}
3580
3581
/* Does either of "pa1" or "pa2" involve any NaN2?
3582
 */
3583
static isl_bool either_involves_nan(__isl_keep isl_pw_aff *pa1,
3584
  __isl_keep isl_pw_aff *pa2)
3585
69
{
3586
69
  isl_bool has_nan;
3587
69
3588
69
  has_nan = isl_pw_aff_involves_nan(pa1);
3589
69
  if (
has_nan < 0 || 69
has_nan69
)
3590
1
    return has_nan;
3591
68
  return isl_pw_aff_involves_nan(pa2);
3592
69
}
3593
3594
/* Replace "pa1" and "pa2" (at least one of which involves a NaN)
3595
 * by a NaN on their shared domain.
3596
 *
3597
 * In principle, the result could be refined to only being NaN
3598
 * on the parts of this domain where at least one of "pa1" or "pa2" is NaN.
3599
 */
3600
static __isl_give isl_pw_aff *replace_by_nan(__isl_take isl_pw_aff *pa1,
3601
  __isl_take isl_pw_aff *pa2)
3602
2
{
3603
2
  isl_local_space *ls;
3604
2
  isl_set *dom;
3605
2
  isl_pw_aff *pa;
3606
2
3607
2
  dom = isl_set_intersect(isl_pw_aff_domain(pa1), isl_pw_aff_domain(pa2));
3608
2
  ls = isl_local_space_from_space(isl_set_get_space(dom));
3609
2
  pa = isl_pw_aff_nan_on_domain(ls);
3610
2
  pa = isl_pw_aff_intersect_domain(pa, dom);
3611
2
3612
2
  return pa;
3613
2
}
3614
3615
static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
3616
  __isl_take isl_pw_aff *pwaff2)
3617
7
{
3618
7
  isl_set *le;
3619
7
  isl_set *dom;
3620
7
3621
7
  dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
3622
7
        isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
3623
7
  le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
3624
7
        isl_pw_aff_copy(pwaff2));
3625
7
  dom = isl_set_subtract(dom, isl_set_copy(le));
3626
7
  return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
3627
7
}
3628
3629
static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
3630
  __isl_take isl_pw_aff *pwaff2)
3631
60
{
3632
60
  isl_set *ge;
3633
60
  isl_set *dom;
3634
60
3635
60
  dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
3636
60
        isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
3637
60
  ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
3638
60
        isl_pw_aff_copy(pwaff2));
3639
60
  dom = isl_set_subtract(dom, isl_set_copy(ge));
3640
60
  return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
3641
60
}
3642
3643
/* Return an expression for the minimum (if "max" is not set) or
3644
 * the maximum (if "max" is set) of "pa1" and "pa2".
3645
 * If either expression involves any NaN, then return a NaN
3646
 * on the shared domain as result.
3647
 */
3648
static __isl_give isl_pw_aff *pw_aff_min_max(__isl_take isl_pw_aff *pa1,
3649
  __isl_take isl_pw_aff *pa2, int max)
3650
69
{
3651
69
  isl_bool has_nan;
3652
69
3653
69
  has_nan = either_involves_nan(pa1, pa2);
3654
69
  if (has_nan < 0)
3655
0
    pa1 = isl_pw_aff_free(pa1);
3656
69
  else 
if (69
has_nan69
)
3657
2
    return replace_by_nan(pa1, pa2);
3658
69
3659
67
  
if (67
max67
)
3660
60
    return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_max);
3661
67
  else
3662
7
    return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_min);
3663
67
}
3664
3665
/* Return an expression for the minimum of "pwaff1" and "pwaff2".
3666
 */
3667
__isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
3668
  __isl_take isl_pw_aff *pwaff2)
3669
9
{
3670
9
  return pw_aff_min_max(pwaff1, pwaff2, 0);
3671
9
}
3672
3673
/* Return an expression for the maximum of "pwaff1" and "pwaff2".
3674
 */
3675
__isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
3676
  __isl_take isl_pw_aff *pwaff2)
3677
60
{
3678
60
  return pw_aff_min_max(pwaff1, pwaff2, 1);
3679
60
}
3680
3681
static __isl_give isl_pw_aff *pw_aff_list_reduce(
3682
  __isl_take isl_pw_aff_list *list,
3683
  __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
3684
          __isl_take isl_pw_aff *pwaff2))
3685
6
{
3686
6
  int i;
3687
6
  isl_ctx *ctx;
3688
6
  isl_pw_aff *res;
3689
6
3690
6
  if (!list)
3691
0
    return NULL;
3692
6
3693
6
  ctx = isl_pw_aff_list_get_ctx(list);
3694
6
  if (list->n < 1)
3695
0
    isl_die(ctx, isl_error_invalid,
3696
6
      "list should contain at least one element", goto error);
3697
6
3698
6
  res = isl_pw_aff_copy(list->p[0]);
3699
12
  for (i = 1; 
i < list->n12
;
++i6
)
3700
6
    res = fn(res, isl_pw_aff_copy(list->p[i]));
3701
6
3702
6
  isl_pw_aff_list_free(list);
3703
6
  return res;
3704
0
error:
3705
0
  isl_pw_aff_list_free(list);
3706
0
  return NULL;
3707
6
}
3708
3709
/* Return an isl_pw_aff that maps each element in the intersection of the
3710
 * domains of the elements of list to the minimal corresponding affine
3711
 * expression.
3712
 */
3713
__isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
3714
5
{
3715
5
  return pw_aff_list_reduce(list, &isl_pw_aff_min);
3716
5
}
3717
3718
/* Return an isl_pw_aff that maps each element in the intersection of the
3719
 * domains of the elements of list to the maximal corresponding affine
3720
 * expression.
3721
 */
3722
__isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
3723
1
{
3724
1
  return pw_aff_list_reduce(list, &isl_pw_aff_max);
3725
1
}
3726
3727
/* Mark the domains of "pwaff" as rational.
3728
 */
3729
__isl_give isl_pw_aff *isl_pw_aff_set_rational(__isl_take isl_pw_aff *pwaff)
3730
225
{
3731
225
  int i;
3732
225
3733
225
  pwaff = isl_pw_aff_cow(pwaff);
3734
225
  if (!pwaff)
3735
0
    return NULL;
3736
225
  
if (225
pwaff->n == 0225
)
3737
0
    return pwaff;
3738
225
3739
450
  
for (i = 0; 225
i < pwaff->n450
;
++i225
)
{225
3740
225
    pwaff->p[i].set = isl_set_set_rational(pwaff->p[i].set);
3741
225
    if (!pwaff->p[i].set)
3742
0
      return isl_pw_aff_free(pwaff);
3743
225
  }
3744
225
3745
225
  return pwaff;
3746
225
}
3747
3748
/* Mark the domains of the elements of "list" as rational.
3749
 */
3750
__isl_give isl_pw_aff_list *isl_pw_aff_list_set_rational(
3751
  __isl_take isl_pw_aff_list *list)
3752
48
{
3753
48
  int i, n;
3754
48
3755
48
  if (!list)
3756
0
    return NULL;
3757
48
  
if (48
list->n == 048
)
3758
0
    return list;
3759
48
3760
48
  n = list->n;
3761
98
  for (i = 0; 
i < n98
;
++i50
)
{50
3762
50
    isl_pw_aff *pa;
3763
50
3764
50
    pa = isl_pw_aff_list_get_pw_aff(list, i);
3765
50
    pa = isl_pw_aff_set_rational(pa);
3766
50
    list = isl_pw_aff_list_set_pw_aff(list, i, pa);
3767
50
  }
3768
48
3769
48
  return list;
3770
48
}
3771
3772
/* Do the parameters of "aff" match those of "space"?
3773
 */
3774
isl_bool isl_aff_matching_params(__isl_keep isl_aff *aff,
3775
  __isl_keep isl_space *space)
3776
378k
{
3777
378k
  isl_space *aff_space;
3778
378k
  isl_bool match;
3779
378k
3780
378k
  if (
!aff || 378k
!space378k
)
3781
0
    return isl_bool_error;
3782
378k
3783
378k
  aff_space = isl_aff_get_domain_space(aff);
3784
378k
3785
378k
  match = isl_space_has_equal_params(space, aff_space);
3786
378k
3787
378k
  isl_space_free(aff_space);
3788
378k
  return match;
3789
378k
}
3790
3791
/* Check that the domain space of "aff" matches "space".
3792
 */
3793
isl_stat isl_aff_check_match_domain_space(__isl_keep isl_aff *aff,
3794
  __isl_keep isl_space *space)
3795
378k
{
3796
378k
  isl_space *aff_space;
3797
378k
  isl_bool match;
3798
378k
3799
378k
  if (
!aff || 378k
!space378k
)
3800
0
    return isl_stat_error;
3801
378k
3802
378k
  aff_space = isl_aff_get_domain_space(aff);
3803
378k
3804
378k
  match = isl_space_has_equal_params(space, aff_space);
3805
378k
  if (match < 0)
3806
0
    goto error;
3807
378k
  
if (378k
!match378k
)
3808
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
3809
378k
      "parameters don't match", goto error);
3810
378k
  match = isl_space_tuple_is_equal(space, isl_dim_in,
3811
378k
          aff_space, isl_dim_set);
3812
378k
  if (match < 0)
3813
0
    goto error;
3814
378k
  
if (378k
!match378k
)
3815
0
    isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
3816
378k
      "domains don't match", goto error);
3817
378k
  isl_space_free(aff_space);
3818
378k
  return isl_stat_ok;
3819
0
error:
3820
0
  isl_space_free(aff_space);
3821
0
  return isl_stat_error;
3822
378k
}
3823
3824
#undef BASE
3825
#define BASE aff
3826
#undef DOMBASE
3827
#define DOMBASE set
3828
#define NO_DOMAIN
3829
3830
#include <isl_multi_templ.c>
3831
#include <isl_multi_apply_set.c>
3832
#include <isl_multi_cmp.c>
3833
#include <isl_multi_floor.c>
3834
#include <isl_multi_gist.c>
3835
3836
#undef NO_DOMAIN
3837
3838
/* Remove any internal structure of the domain of "ma".
3839
 * If there is any such internal structure in the input,
3840
 * then the name of the corresponding space is also removed.
3841
 */
3842
__isl_give isl_multi_aff *isl_multi_aff_flatten_domain(
3843
  __isl_take isl_multi_aff *ma)
3844
0
{
3845
0
  isl_space *space;
3846
0
3847
0
  if (!ma)
3848
0
    return NULL;
3849
0
3850
0
  
if (0
!ma->space->nested[0]0
)
3851
0
    return ma;
3852
0
3853
0
  space = isl_multi_aff_get_space(ma);
3854
0
  space = isl_space_flatten_domain(space);
3855
0
  ma = isl_multi_aff_reset_space(ma, space);
3856
0
3857
0
  return ma;
3858
0
}
3859
3860
/* Given a map space, return an isl_multi_aff that maps a wrapped copy
3861
 * of the space to its domain.
3862
 */
3863
__isl_give isl_multi_aff *isl_multi_aff_domain_map(__isl_take isl_space *space)
3864
350
{
3865
350
  int i, n_in;
3866
350
  isl_local_space *ls;
3867
350
  isl_multi_aff *ma;
3868
350
3869
350
  if (!space)
3870
0
    return NULL;
3871
350
  
if (350
!isl_space_is_map(space)350
)
3872
0
    isl_die(isl_space_get_ctx(space), isl_error_invalid,
3873
350
      "not a map space", goto error);
3874
350
3875
350
  n_in = isl_space_dim(space, isl_dim_in);
3876
350
  space = isl_space_domain_map(space);
3877
350
3878
350
  ma = isl_multi_aff_alloc(isl_space_copy(space));
3879
350
  if (
n_in == 0350
)
{2
3880
2
    isl_space_free(space);
3881
2
    return ma;
3882
2
  }
3883
350
3884
348
  space = isl_space_domain(space);
3885
348
  ls = isl_local_space_from_space(space);
3886
847
  for (i = 0; 
i < n_in847
;
++i499
)
{499
3887
499
    isl_aff *aff;
3888
499
3889
499
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3890
499
            isl_dim_set, i);
3891
499
    ma = isl_multi_aff_set_aff(ma, i, aff);
3892
499
  }
3893
348
  isl_local_space_free(ls);
3894
348
  return ma;
3895
0
error:
3896
0
  isl_space_free(space);
3897
0
  return NULL;
3898
350
}
3899
3900
/* Given a map space, return an isl_multi_aff that maps a wrapped copy
3901
 * of the space to its range.
3902
 */
3903
__isl_give isl_multi_aff *isl_multi_aff_range_map(__isl_take isl_space *space)
3904
0
{
3905
0
  int i, n_in, n_out;
3906
0
  isl_local_space *ls;
3907
0
  isl_multi_aff *ma;
3908
0
3909
0
  if (!space)
3910
0
    return NULL;
3911
0
  
if (0
!isl_space_is_map(space)0
)
3912
0
    isl_die(isl_space_get_ctx(space), isl_error_invalid,
3913
0
      "not a map space", goto error);
3914
0
3915
0
  n_in = isl_space_dim(space, isl_dim_in);
3916
0
  n_out = isl_space_dim(space, isl_dim_out);
3917
0
  space = isl_space_range_map(space);
3918
0
3919
0
  ma = isl_multi_aff_alloc(isl_space_copy(space));
3920
0
  if (
n_out == 00
)
{0
3921
0
    isl_space_free(space);
3922
0
    return ma;
3923
0
  }
3924
0
3925
0
  space = isl_space_domain(space);
3926
0
  ls = isl_local_space_from_space(space);
3927
0
  for (i = 0; 
i < n_out0
;
++i0
)
{0
3928
0
    isl_aff *aff;
3929
0
3930
0
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3931
0
            isl_dim_set, n_in + i);
3932
0
    ma = isl_multi_aff_set_aff(ma, i, aff);
3933
0
  }
3934
0
  isl_local_space_free(ls);
3935
0
  return ma;
3936
0
error:
3937
0
  isl_space_free(space);
3938
0
  return NULL;
3939
0
}
3940
3941
/* Given a map space, return an isl_pw_multi_aff that maps a wrapped copy
3942
 * of the space to its range.
3943
 */
3944
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_range_map(
3945
  __isl_take isl_space *space)
3946
0
{
3947
0
  return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_range_map(space));
3948
0
}
3949
3950
/* Given the space of a set and a range of set dimensions,
3951
 * construct an isl_multi_aff that projects out those dimensions.
3952
 */
3953
__isl_give isl_multi_aff *isl_multi_aff_project_out_map(
3954
  __isl_take isl_space *space, enum isl_dim_type type,
3955
  unsigned first, unsigned n)
3956
1.79k
{
3957
1.79k
  int i, dim;
3958
1.79k
  isl_local_space *ls;
3959
1.79k
  isl_multi_aff *ma;
3960
1.79k
3961
1.79k
  if (!space)
3962
0
    return NULL;
3963
1.79k
  
if (1.79k
!isl_space_is_set(space)1.79k
)
3964
0
    isl_die(isl_space_get_ctx(space), isl_error_unsupported,
3965
1.79k
      "expecting set space", goto error);
3966
1.79k
  
if (1.79k
type != isl_dim_set1.79k
)
3967
0
    isl_die(isl_space_get_ctx(space), isl_error_invalid,
3968
1.79k
      "only set dimensions can be projected out", goto error);
3969
1.79k
3970
1.79k
  dim = isl_space_dim(space, isl_dim_set);
3971
1.79k
  if (first + n > dim)
3972
0
    isl_die(isl_space_get_ctx(space), isl_error_invalid,
3973
1.79k
      "range out of bounds", goto error);
3974
1.79k
3975
1.79k
  space = isl_space_from_domain(space);
3976
1.79k
  space = isl_space_add_dims(space, isl_dim_out, dim - n);
3977
1.79k
3978
1.79k
  if (dim == n)
3979
0
    return isl_multi_aff_alloc(space);
3980
1.79k
3981
1.79k
  ma = isl_multi_aff_alloc(isl_space_copy(space));
3982
1.79k
  space = isl_space_domain(space);
3983
1.79k
  ls = isl_local_space_from_space(space);
3984
1.79k
3985
4.09k
  for (i = 0; 
i < first4.09k
;
++i2.30k
)
{2.30k
3986
2.30k
    isl_aff *aff;
3987
2.30k
3988
2.30k
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3989
2.30k
            isl_dim_set, i);
3990
2.30k
    ma = isl_multi_aff_set_aff(ma, i, aff);
3991
2.30k
  }
3992
1.79k
3993
1.82k
  for (i = 0; 
i < dim - (first + n)1.82k
;
++i36
)
{36
3994
36
    isl_aff *aff;
3995
36
3996
36
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3997
36
            isl_dim_set, first + n + i);
3998
36
    ma = isl_multi_aff_set_aff(ma, first + i, aff);
3999
36
  }
4000
1.79k
4001
1.79k
  isl_local_space_free(ls);
4002
1.79k
  return ma;
4003
0
error:
4004
0
  isl_space_free(space);
4005
0
  return NULL;
4006
1.79k
}
4007
4008
/* Given the space of a set and a range of set dimensions,
4009
 * construct an isl_pw_multi_aff that projects out those dimensions.
4010
 */
4011
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_project_out_map(
4012
  __isl_take isl_space *space, enum isl_dim_type type,
4013
  unsigned first, unsigned n)
4014
1.73k
{
4015
1.73k
  isl_multi_aff *ma;
4016
1.73k
4017
1.73k
  ma = isl_multi_aff_project_out_map(space, type, first, n);
4018
1.73k
  return isl_pw_multi_aff_from_multi_aff(ma);
4019
1.73k
}
4020
4021
/* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
4022
 * domain.
4023
 */
4024
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
4025
  __isl_take isl_multi_aff *ma)
4026
3.06k
{
4027
3.06k
  isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
4028
3.06k
  return isl_pw_multi_aff_alloc(dom, ma);
4029
3.06k
}
4030
4031
/* Create a piecewise multi-affine expression in the given space that maps each
4032
 * input dimension to the corresponding output dimension.
4033
 */
4034
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity(
4035
  __isl_take isl_space *space)
4036
11
{
4037
11
  return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space));
4038
11
}
4039
4040
/* Exploit the equalities in "eq" to simplify the affine expressions.
4041
 */
4042
static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
4043
  __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
4044
1.22k
{
4045
1.22k
  int i;
4046
1.22k
4047
1.22k
  maff = isl_multi_aff_cow(maff);
4048
1.22k
  if (
!maff || 1.22k
!eq1.22k
)
4049
0
    goto error;
4050
1.22k
4051
3.71k
  
for (i = 0; 1.22k
i < maff->n3.71k
;
++i2.49k
)
{2.49k
4052
2.49k
    maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
4053
2.49k
                isl_basic_set_copy(eq));
4054
2.49k
    if (!maff->p[i])
4055
0
      goto error;
4056
2.49k
  }
4057
1.22k
4058
1.22k
  isl_basic_set_free(eq);
4059
1.22k
  return maff;
4060
0
error:
4061
0
  isl_basic_set_free(eq);
4062
0
  isl_multi_aff_free(maff);
4063
0
  return NULL;
4064
1.22k
}
4065
4066
__isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
4067
  isl_int f)
4068
0
{
4069
0
  int i;
4070
0
4071
0
  maff = isl_multi_aff_cow(maff);
4072
0
  if (!maff)
4073
0
    return NULL;
4074
0
4075
0
  
for (i = 0; 0
i < maff->n0
;
++i0
)
{0
4076
0
    maff->p[i] = isl_aff_scale(maff->p[i], f);
4077
0
    if (!maff->p[i])
4078
0
      return isl_multi_aff_free(maff);
4079
0
  }
4080
0
4081
0
  return maff;
4082
0
}
4083
4084
__isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
4085
  __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
4086
2
{
4087
2
  maff1 = isl_multi_aff_add(maff1, maff2);
4088
2
  maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
4089
2
  return maff1;
4090
2
}
4091
4092
int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
4093
14.1k
{
4094
14.1k
  if (!maff)
4095
0
    return -1;
4096
14.1k
4097
14.1k
  return 0;
4098
14.1k
}
4099
4100
/* Return the set of domain elements where "ma1" is lexicographically
4101
 * smaller than or equal to "ma2".
4102
 */
4103
__isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1,
4104
  __isl_take isl_multi_aff *ma2)
4105
285
{
4106
285
  return isl_multi_aff_lex_ge_set(ma2, ma1);
4107
285
}
4108
4109
/* Return the set of domain elements where "ma1" is lexicographically
4110
 * smaller than "ma2".
4111
 */
4112
__isl_give isl_set *isl_multi_aff_lex_lt_set(__isl_take isl_multi_aff *ma1,
4113
  __isl_take isl_multi_aff *ma2)
4114
0
{
4115
0
  return isl_multi_aff_lex_gt_set(ma2, ma1);
4116
0
}
4117
4118
/* Return the set of domain elements where "ma1" and "ma2"
4119
 * satisfy "order".
4120
 */
4121
static __isl_give isl_set *isl_multi_aff_order_set(
4122
  __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2,
4123
  __isl_give isl_map *order(__isl_take isl_space *set_space))
4124
563
{
4125
563
  isl_space *space;
4126
563
  isl_map *map1, *map2;
4127
563
  isl_map *map, *ge;
4128
563
4129
563
  map1 = isl_map_from_multi_aff(ma1);
4130
563
  map2 = isl_map_from_multi_aff(ma2);
4131
563
  map = isl_map_range_product(map1, map2);
4132
563
  space = isl_space_range(isl_map_get_space(map));
4133
563
  space = isl_space_domain(isl_space_unwrap(space));
4134
563
  ge = order(space);
4135
563
  map = isl_map_intersect_range(map, isl_map_wrap(ge));
4136
563
4137
563
  return isl_map_domain(map);
4138
563
}
4139
4140
/* Return the set of domain elements where "ma1" is lexicographically
4141
 * greater than or equal to "ma2".
4142
 */
4143
__isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1,
4144
  __isl_take isl_multi_aff *ma2)
4145
563
{
4146
563
  return isl_multi_aff_order_set(ma1, ma2, &isl_map_lex_ge);
4147
563
}
4148
4149
/* Return the set of domain elements where "ma1" is lexicographically
4150
 * greater than "ma2".
4151
 */
4152
__isl_give isl_set *isl_multi_aff_lex_gt_set(__isl_take isl_multi_aff *ma1,
4153
  __isl_take isl_multi_aff *ma2)
4154
0
{
4155
0
  return isl_multi_aff_order_set(ma1, ma2, &isl_map_lex_gt);
4156
0
}
4157
4158
#undef PW
4159
13.4k
#define PW isl_pw_multi_aff
4160
#undef EL
4161
1.47k
#define EL isl_multi_aff
4162
#undef EL_IS_ZERO
4163
#define EL_IS_ZERO is_empty
4164
#undef ZERO
4165
#define ZERO empty
4166
#undef IS_ZERO
4167
#define IS_ZERO is_empty
4168
#undef FIELD
4169
54.3k
#define FIELD maff
4170
#undef DEFAULT_IS_ZERO
4171
0
#define DEFAULT_IS_ZERO 0
4172
4173
#define NO_SUB
4174
#define NO_EVAL
4175
#define NO_OPT
4176
#define NO_INVOLVES_DIMS
4177
#define NO_INSERT_DIMS
4178
#define NO_LIFT
4179
#define NO_MORPH
4180
4181
#include <isl_pw_templ.c>
4182
#include <isl_pw_union_opt.c>
4183
4184
#undef NO_SUB
4185
4186
#undef UNION
4187
6.26k
#define UNION isl_union_pw_multi_aff
4188
#undef PART
4189
18.4k
#define PART isl_pw_multi_aff
4190
#undef PARTS
4191
#define PARTS pw_multi_aff
4192
4193
#include <isl_union_multi.c>
4194
#include <isl_union_neg.c>
4195
4196
static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax(
4197
  __isl_take isl_pw_multi_aff *pma1,
4198
  __isl_take isl_pw_multi_aff *pma2)
4199
350
{
4200
350
  return isl_pw_multi_aff_union_opt_cmp(pma1, pma2,
4201
350
              &isl_multi_aff_lex_ge_set);
4202
350
}
4203
4204
/* Given two piecewise multi affine expressions, return a piecewise
4205
 * multi-affine expression defined on the union of the definition domains
4206
 * of the inputs that is equal to the lexicographic maximum of the two
4207
 * inputs on each cell.  If only one of the two inputs is defined on
4208
 * a given cell, then it is considered to be the maximum.
4209
 */
4210
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmax(
4211
  __isl_take isl_pw_multi_aff *pma1,
4212
  __isl_take isl_pw_multi_aff *pma2)
4213
350
{
4214
350
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4215
350
                &pw_multi_aff_union_lexmax);
4216
350
}
4217
4218
static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin(
4219
  __isl_take isl_pw_multi_aff *pma1,
4220
  __isl_take isl_pw_multi_aff *pma2)
4221
271
{
4222
271
  return isl_pw_multi_aff_union_opt_cmp(pma1, pma2,
4223
271
              &isl_multi_aff_lex_le_set);
4224
271
}
4225
4226
/* Given two piecewise multi affine expressions, return a piecewise
4227
 * multi-affine expression defined on the union of the definition domains
4228
 * of the inputs that is equal to the lexicographic minimum of the two
4229
 * inputs on each cell.  If only one of the two inputs is defined on
4230
 * a given cell, then it is considered to be the minimum.
4231
 */
4232
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmin(
4233
  __isl_take isl_pw_multi_aff *pma1,
4234
  __isl_take isl_pw_multi_aff *pma2)
4235
271
{
4236
271
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4237
271
                &pw_multi_aff_union_lexmin);
4238
271
}
4239
4240
static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
4241
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4242
1
{
4243
1
  return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
4244
1
            &isl_multi_aff_add);
4245
1
}
4246
4247
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
4248
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4249
1
{
4250
1
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4251
1
            &pw_multi_aff_add);
4252
1
}
4253
4254
static __isl_give isl_pw_multi_aff *pw_multi_aff_sub(
4255
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4256
0
{
4257
0
  return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
4258
0
            &isl_multi_aff_sub);
4259
0
}
4260
4261
/* Subtract "pma2" from "pma1" and return the result.
4262
 */
4263
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_sub(
4264
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4265
0
{
4266
0
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4267
0
            &pw_multi_aff_sub);
4268
0
}
4269
4270
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
4271
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4272
335
{
4273
335
  return isl_pw_multi_aff_union_add_(pma1, pma2);
4274
335
}
4275
4276
/* Compute the sum of "upa1" and "upa2" on the union of their domains,
4277
 * with the actual sum on the shared domain and
4278
 * the defined expression on the symmetric difference of the domains.
4279
 */
4280
__isl_give isl_union_pw_aff *isl_union_pw_aff_union_add(
4281
  __isl_take isl_union_pw_aff *upa1, __isl_take isl_union_pw_aff *upa2)
4282
139
{
4283
139
  return isl_union_pw_aff_union_add_(upa1, upa2);
4284
139
}
4285
4286
/* Compute the sum of "upma1" and "upma2" on the union of their domains,
4287
 * with the actual sum on the shared domain and
4288
 * the defined expression on the symmetric difference of the domains.
4289
 */
4290
__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_union_add(
4291
  __isl_take isl_union_pw_multi_aff *upma1,
4292
  __isl_take isl_union_pw_multi_aff *upma2)
4293
107
{
4294
107
  return isl_union_pw_multi_aff_union_add_(upma1, upma2);
4295
107
}
4296
4297
/* Given two piecewise multi-affine expressions A -> B and C -> D,
4298
 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
4299
 */
4300
static __isl_give isl_pw_multi_aff *pw_multi_aff_product(
4301
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4302
1
{
4303
1
  int i, j, n;
4304
1
  isl_space *space;
4305
1
  isl_pw_multi_aff *res;
4306
1
4307
1
  if (
!pma1 || 1
!pma21
)
4308
0
    goto error;
4309
1
4310
1
  n = pma1->n * pma2->n;
4311
1
  space = isl_space_product(isl_space_copy(pma1->dim),
4312
1
          isl_space_copy(pma2->dim));
4313
1
  res = isl_pw_multi_aff_alloc_size(space, n);
4314
1
4315
3
  for (i = 0; 
i < pma1->n3
;
++i2
)
{2
4316
4
    for (j = 0; 
j < pma2->n4
;
++j2
)
{2
4317
2
      isl_set *domain;
4318
2
      isl_multi_aff *ma;
4319
2
4320
2
      domain = isl_set_product(isl_set_copy(pma1->p[i].set),
4321
2
             isl_set_copy(pma2->p[j].set));
4322
2
      ma = isl_multi_aff_product(
4323
2
          isl_multi_aff_copy(pma1->p[i].maff),
4324
2
          isl_multi_aff_copy(pma2->p[j].maff));
4325
2
      res = isl_pw_multi_aff_add_piece(res, domain, ma);
4326
2
    }
4327
2
  }
4328
1
4329
1
  isl_pw_multi_aff_free(pma1);
4330
1
  isl_pw_multi_aff_free(pma2);
4331
1
  return res;
4332
0
error:
4333
0
  isl_pw_multi_aff_free(pma1);
4334
0
  isl_pw_multi_aff_free(pma2);
4335
0
  return NULL;
4336
1
}
4337
4338
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_product(
4339
  __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4340
1
{
4341
1
  return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4342
1
            &pw_multi_aff_product);
4343
1
}
4344
4345
/* Construct a map mapping the domain of the piecewise multi-affine expression
4346
 * to its range, with each dimension in the range equated to the
4347
 * corresponding affine expression on its cell.
4348
 *
4349
 * If the domain of "pma" is rational, then so is the constructed "map".
4350
 */
4351
__isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
4352
4.51k
{
4353
4.51k
  int i;
4354
4.51k
  isl_map *map;
4355
4.51k
4356
4.51k
  if (!pma)
4357
0
    return NULL;
4358
4.51k
4359
4.51k
  map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
4360
4.51k
4361
9.11k
  for (i = 0; 
i < pma->n9.11k
;
++i4.59k
)
{4.59k
4362
4.59k
    isl_bool rational;
4363
4.59k
    isl_multi_aff *maff;
4364
4.59k
    isl_basic_map *bmap;
4365
4.59k
    isl_map *map_i;
4366
4.59k
4367
4.59k
    rational = isl_set_is_rational(pma->p[i].set);
4368
4.59k
    if (rational < 0)
4369
0
      map = isl_map_free(map);
4370
4.59k
    maff = isl_multi_aff_copy(pma->p[i].maff);
4371
4.59k
    bmap = isl_basic_map_from_multi_aff2(maff, rational);
4372
4.59k
    map_i = isl_map_from_basic_map(bmap);
4373
4.59k
    map_i = isl_map_intersect_domain(map_i,
4374
4.59k
            isl_set_copy(pma->p[i].set));
4375
4.59k
    map = isl_map_union_disjoint(map, map_i);
4376
4.59k
  }
4377
4.51k
4378
4.51k
  isl_pw_multi_aff_free(pma);
4379
4.51k
  return map;
4380
4.51k
}
4381
4382
__isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
4383
7
{
4384
7
  if (!pma)
4385
0
    return NULL;
4386
7
4387
7
  
if (7
!isl_space_is_set(pma->dim)7
)
4388
0
    isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4389
7
      "isl_pw_multi_aff cannot be converted into an isl_set",
4390
7
      goto error);
4391
7
4392
7
  return isl_map_from_pw_multi_aff(pma);
4393
0
error:
4394
0
  isl_pw_multi_aff_free(pma);
4395
0
  return NULL;
4396
7
}
4397
4398
/* Subtract the initial "n" elements in "ma" with coefficients in "c" and
4399
 * denominator "denom".
4400
 * "denom" is allowed to be negative, in which case the actual denominator
4401
 * is -denom and the expressions are added instead.
4402
 */
4403
static __isl_give isl_aff *subtract_initial(__isl_take isl_aff *aff,
4404
  __isl_keep isl_multi_aff *ma, int n, isl_int *c, isl_int denom)
4405
4.28k
{
4406
4.28k
  int i, first;
4407
4.28k
  int sign;
4408
4.28k
  isl_int d;
4409
4.28k
4410
4.28k
  first = isl_seq_first_non_zero(c, n);
4411
4.28k
  if (first == -1)
4412
4.27k
    return aff;
4413
4.28k
4414
3
  
sign = 3
isl_int_sgn3
(denom);
4415
3
  isl_int_init(d);
4416
3
  isl_int_abs(d, denom);
4417
6
  for (i = first; 
i < n6
;
++i3
)
{3
4418
3
    isl_aff *aff_i;
4419
3
4420
3
    if (isl_int_is_zero(c[i]))
4421
0
      continue;
4422
3
    aff_i = isl_multi_aff_get_aff(ma, i);
4423
3
    aff_i = isl_aff_scale(aff_i, c[i]);
4424
3
    aff_i = isl_aff_scale_down(aff_i, d);
4425
3
    if (sign >= 0)
4426
2
      aff = isl_aff_sub(aff, aff_i);
4427
3
    else
4428
1
      aff = isl_aff_add(aff, aff_i);
4429
3
  }
4430
3
  isl_int_clear(d);
4431
3
4432
3
  return aff;
4433
4.28k
}
4434
4435
/* Extract an affine expression that expresses the output dimension "pos"
4436
 * of "bmap" in terms of the parameters and input dimensions from
4437
 * equality "eq".
4438
 * Note that this expression may involve integer divisions defined
4439
 * in terms of parameters and input dimensions.
4440
 * The equality may also involve references to earlier (but not later)
4441
 * output dimensions.  These are replaced by the corresponding elements
4442
 * in "ma".
4443
 *
4444
 * If the equality is of the form
4445
 *
4446
 *  f(i) + h(j) + a x + g(i) = 0,
4447
 *
4448
 * with f(i) a linear combinations of the parameters and input dimensions,
4449
 * g(i) a linear combination of integer divisions defined in terms of the same
4450
 * and h(j) a linear combinations of earlier output dimensions,
4451
 * then the affine expression is
4452
 *
4453
 *  (-f(i) - g(i))/a - h(j)/a
4454
 *
4455
 * If the equality is of the form
4456
 *
4457
 *  f(i) + h(j) - a x + g(i) = 0,
4458
 *
4459
 * then the affine expression is
4460
 *
4461
 *  (f(i) + g(i))/a - h(j)/(-a)
4462
 *
4463
 *
4464
 * If "div" refers to an integer division (i.e., it is smaller than
4465
 * the number of integer divisions), then the equality constraint
4466
 * does involve an integer division (the one at position "div") that
4467
 * is defined in terms of output dimensions.  However, this integer
4468
 * division can be eliminated by exploiting a pair of constraints
4469
 * x >= l and x <= l + n, with n smaller than the coefficient of "div"
4470
 * in the equality constraint.  "ineq" refers to inequality x >= l, i.e.,
4471
 * -l + x >= 0.
4472
 * In particular, let
4473
 *
4474
 *  x = e(i) + m floor(...)
4475
 *
4476
 * with e(i) the expression derived above and floor(...) the integer
4477
 * division involving output dimensions.
4478
 * From
4479
 *
4480
 *  l <= x <= l + n,
4481
 *
4482
 * we have
4483
 *
4484
 *  0 <= x - l <= n
4485
 *
4486
 * This means
4487
 *
4488
 *  e(i) + m floor(...) - l = (e(i) + m floor(...) - l) mod m
4489
 *                          = (e(i) - l) mod m
4490
 *
4491
 * Therefore,
4492
 *
4493
 *  x - l = (e(i) - l) mod m
4494
 *
4495
 * or
4496
 *
4497
 *  x = ((e(i) - l) mod m) + l
4498
 *
4499
 * The variable "shift" below contains the expression -l, which may
4500
 * also involve a linear combination of earlier output dimensions.
4501
 */
4502
static __isl_give isl_aff *extract_aff_from_equality(
4503
  __isl_keep isl_basic_map *bmap, int pos, int eq, int div, int ineq,
4504
  __isl_keep isl_multi_aff *ma)
4505
4.25k
{
4506
4.25k
  unsigned o_out;
4507
4.25k
  unsigned n_div, n_out;
4508
4.25k
  isl_ctx *ctx;
4509
4.25k
  isl_local_space *ls;
4510
4.25k
  isl_aff *aff, *shift;
4511
4.25k
  isl_val *mod;
4512
4.25k
4513
4.25k
  ctx = isl_basic_map_get_ctx(bmap);
4514
4.25k
  ls = isl_basic_map_get_local_space(bmap);
4515
4.25k
  ls = isl_local_space_domain(ls);
4516
4.25k
  aff = isl_aff_alloc(isl_local_space_copy(ls));
4517
4.25k
  if (!aff)
4518
0
    goto error;
4519
4.25k
  o_out = isl_basic_map_offset(bmap, isl_dim_out);
4520
4.25k
  n_out = isl_basic_map_dim(bmap, isl_dim_out);
4521
4.25k
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
4522
4.25k
  if (
isl_int_is_neg4.25k
(bmap->eq[eq][o_out + pos]))
{217
4523
217
    isl_seq_cpy(aff->v->el + 1, bmap->eq[eq], o_out);
4524
217
    isl_seq_cpy(aff->v->el + 1 + o_out,
4525
217
          bmap->eq[eq] + o_out + n_out, n_div);
4526
4.04k
  } else {
4527
4.04k
    isl_seq_neg(aff->v->el + 1, bmap->eq[eq], o_out);
4528
4.04k
    isl_seq_neg(aff->v->el + 1 + o_out,
4529
4.04k
          bmap->eq[eq] + o_out + n_out, n_div);
4530
4.04k
  }
4531
4.25k
  if (div < n_div)
4532
25
    isl_int_set_si(aff->v->el[1 + o_out + div], 0);
4533
4.25k
  isl_int_abs(aff->v->el[0], bmap->eq[eq][o_out + pos]);
4534
4.25k
  aff = subtract_initial(aff, ma, pos, bmap->eq[eq] + o_out,
4535
4.25k
          bmap->eq[eq][o_out + pos]);
4536
4.25k
  if (
div < n_div4.25k
)
{25
4537
25
    shift = isl_aff_alloc(isl_local_space_copy(ls));
4538
25
    if (!shift)
4539
0
      goto error;
4540
25
    isl_seq_cpy(shift->v->el + 1, bmap->ineq[ineq], o_out);
4541
25
    isl_seq_cpy(shift->v->el + 1 + o_out,
4542
25
          bmap->ineq[ineq] + o_out + n_out, n_div);
4543
25
    isl_int_set_si(shift->v->el[0], 1);
4544
25
    shift = subtract_initial(shift, ma, pos,
4545
25
          bmap->ineq[ineq] + o_out, ctx->negone);
4546
25
    aff = isl_aff_add(aff, isl_aff_copy(shift));
4547
25
    mod = isl_val_int_from_isl_int(ctx,
4548
25
              bmap->eq[eq][o_out + n_out + div]);
4549
25
    mod = isl_val_abs(mod);
4550
25
    aff = isl_aff_mod_val(aff, mod);
4551
25
    aff = isl_aff_sub(aff, shift);
4552
25
  }
4553
4.25k
4554
4.25k
  isl_local_space_free(ls);
4555
4.25k
  return aff;
4556
0
error:
4557
0
  isl_local_space_free(ls);
4558
0
  isl_aff_free(aff);
4559
0
  return NULL;
4560
4.25k
}
4561
4562
/* Given a basic map with output dimensions defined
4563
 * in terms of the parameters input dimensions and earlier
4564
 * output dimensions using an equality (and possibly a pair on inequalities),
4565
 * extract an isl_aff that expresses output dimension "pos" in terms
4566
 * of the parameters and input dimensions.
4567
 * Note that this expression may involve integer divisions defined
4568
 * in terms of parameters and input dimensions.
4569
 * "ma" contains the expressions corresponding to earlier output dimensions.
4570
 *
4571
 * This function shares some similarities with
4572
 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
4573
 */
4574
static __isl_give isl_aff *extract_isl_aff_from_basic_map(
4575
  __isl_keep isl_basic_map *bmap, int pos, __isl_keep isl_multi_aff *ma)
4576
4.25k
{
4577
4.25k
  int eq, div, ineq;
4578
4.25k
  isl_aff *aff;
4579
4.25k
4580
4.25k
  if (!bmap)
4581
0
    return NULL;
4582
4.25k
  eq = isl_basic_map_output_defining_equality(bmap, pos, &div, &ineq);
4583
4.25k
  if (eq >= bmap->n_eq)
4584
0
    isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
4585
4.25k
      "unable to find suitable equality", return NULL);
4586
4.25k
  aff = extract_aff_from_equality(bmap, pos, eq, div, ineq, ma);
4587
4.25k
4588
4.25k
  aff = isl_aff_remove_unused_divs(aff);
4589
4.25k
  return aff;
4590
4.25k
}
4591
4592
/* Given a basic map where each output dimension is defined
4593
 * in terms of the parameters and input dimensions using an equality,
4594
 * extract an isl_multi_aff that expresses the output dimensions in terms
4595
 * of the parameters and input dimensions.
4596
 */
4597
static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
4598
  __isl_take isl_basic_map *bmap)
4599
2.93k
{
4600
2.93k
  int i;
4601
2.93k
  unsigned n_out;
4602
2.93k
  isl_multi_aff *ma;
4603
2.93k
4604
2.93k
  if (!bmap)
4605
0
    return NULL;
4606
2.93k
4607
2.93k
  ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
4608
2.93k
  n_out = isl_basic_map_dim(bmap, isl_dim_out);
4609
2.93k
4610
7.19k
  for (i = 0; 
i < n_out7.19k
;
++i4.25k
)
{4.25k
4611
4.25k
    isl_aff *aff;
4612
4.25k
4613
4.25k
    aff = extract_isl_aff_from_basic_map(bmap, i, ma);
4614
4.25k
    ma = isl_multi_aff_set_aff(ma, i, aff);
4615
4.25k
  }
4616
2.93k
4617
2.93k
  isl_basic_map_free(bmap);
4618
2.93k
4619
2.93k
  return ma;
4620
2.93k
}
4621
4622
/* Given a basic set where each set dimension is defined
4623
 * in terms of the parameters using an equality,
4624
 * extract an isl_multi_aff that expresses the set dimensions in terms
4625
 * of the parameters.
4626
 */
4627
__isl_give isl_multi_aff *isl_multi_aff_from_basic_set_equalities(
4628
  __isl_take isl_basic_set *bset)
4629
9
{
4630
9
  return extract_isl_multi_aff_from_basic_map(bset);
4631
9
}
4632
4633
/* Create an isl_pw_multi_aff that is equivalent to
4634
 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
4635
 * The given basic map is such that each output dimension is defined
4636
 * in terms of the parameters and input dimensions using an equality.
4637
 *
4638
 * Since some applications expect the result of isl_pw_multi_aff_from_map
4639
 * to only contain integer affine expressions, we compute the floor
4640
 * of the expression before returning.
4641
 *
4642
 * Remove all constraints involving local variables without
4643
 * an explicit representation (resulting in the removal of those
4644
 * local variables) prior to the actual extraction to ensure
4645
 * that the local spaces in which the resulting affine expressions
4646
 * are created do not contain any unknown local variables.
4647
 * Removing such constraints is safe because constraints involving
4648
 * unknown local variables are not used to determine whether
4649
 * a basic map is obviously single-valued.
4650
 */
4651
static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
4652
  __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
4653
2.92k
{
4654
2.92k
  isl_multi_aff *ma;
4655
2.92k
4656
2.92k
  bmap = isl_basic_map_drop_constraint_involving_unknown_divs(bmap);
4657
2.92k
  ma = extract_isl_multi_aff_from_basic_map(bmap);
4658
2.92k
  ma = isl_multi_aff_floor(ma);
4659
2.92k
  return isl_pw_multi_aff_alloc(domain, ma);
4660
2.92k
}
4661
4662
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4663
 * This obviously only works if the input "map" is single-valued.
4664
 * If so, we compute the lexicographic minimum of the image in the form
4665
 * of an isl_pw_multi_aff.  Since the image is unique, it is equal
4666
 * to its lexicographic minimum.
4667
 * If the input is not single-valued, we produce an error.
4668
 */
4669
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_base(
4670
  __isl_take isl_map *map)
4671
8
{
4672
8
  int i;
4673
8
  int sv;
4674
8
  isl_pw_multi_aff *pma;
4675
8
4676
8
  sv = isl_map_is_single_valued(map);
4677
8
  if (sv < 0)
4678
0
    goto error;
4679
8
  
if (8
!sv8
)
4680
0
    isl_die(isl_map_get_ctx(map), isl_error_invalid,
4681
8
      "map is not single-valued", goto error);
4682
8
  map = isl_map_make_disjoint(map);
4683
8
  if (!map)
4684
0
    return NULL;
4685
8
4686
8
  pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
4687
8
4688
25
  for (i = 0; 
i < map->n25
;
++i17
)
{17
4689
17
    isl_pw_multi_aff *pma_i;
4690
17
    isl_basic_map *bmap;
4691
17
    bmap = isl_basic_map_copy(map->p[i]);
4692
17
    pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
4693
17
    pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
4694
17
  }
4695
8
4696
8
  isl_map_free(map);
4697
8
  return pma;
4698
0
error:
4699
0
  isl_map_free(map);
4700
0
  return NULL;
4701
8
}
4702
4703
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4704
 * taking into account that the output dimension at position "d"
4705
 * can be represented as
4706
 *
4707
 *  x = floor((e(...) + c1) / m)
4708
 *
4709
 * given that constraint "i" is of the form
4710
 *
4711
 *  e(...) + c1 - m x >= 0
4712
 *
4713
 *
4714
 * Let "map" be of the form
4715
 *
4716
 *  A -> B
4717
 *
4718
 * We construct a mapping
4719
 *
4720
 *  A -> [A -> x = floor(...)]
4721
 *
4722
 * apply that to the map, obtaining
4723
 *
4724
 *  [A -> x = floor(...)] -> B
4725
 *
4726
 * and equate dimension "d" to x.
4727
 * We then compute a isl_pw_multi_aff representation of the resulting map
4728
 * and plug in the mapping above.
4729
 */
4730
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_div(
4731
  __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i)
4732
11
{
4733
11
  isl_ctx *ctx;
4734
11
  isl_space *space;
4735
11
  isl_local_space *ls;
4736
11
  isl_multi_aff *ma;
4737
11
  isl_aff *aff;
4738
11
  isl_vec *v;
4739
11
  isl_map *insert;
4740
11
  int offset;
4741
11
  int n;
4742
11
  int n_in;
4743
11
  isl_pw_multi_aff *pma;
4744
11
  isl_bool is_set;
4745
11
4746
11
  is_set = isl_map_is_set(map);
4747
11
  if (is_set < 0)
4748
0
    goto error;
4749
11
4750
11
  offset = isl_basic_map_offset(hull, isl_dim_out);
4751
11
  ctx = isl_map_get_ctx(map);
4752
11
  space = isl_space_domain(isl_map_get_space(map));
4753
11
  n_in = isl_space_dim(space, isl_dim_set);
4754
11
  n = isl_space_dim(space, isl_dim_all);
4755
11
4756
11
  v = isl_vec_alloc(ctx, 1 + 1 + n);
4757
11
  if (
v11
)
{11
4758
11
    isl_int_neg(v->el[0], hull->ineq[i][offset + d]);
4759
11
    isl_seq_cpy(v->el + 1, hull->ineq[i], 1 + n);
4760
11
  }
4761
11
  isl_basic_map_free(hull);
4762
11
4763
11
  ls = isl_local_space_from_space(isl_space_copy(space));
4764
11
  aff = isl_aff_alloc_vec(ls, v);
4765
11
  aff = isl_aff_floor(aff);
4766
11
  if (
is_set11
)
{1
4767
1
    isl_space_free(space);
4768
1
    ma = isl_multi_aff_from_aff(aff);
4769
10
  } else {
4770
10
    ma = isl_multi_aff_identity(isl_space_map_from_set(space));
4771
10
    ma = isl_multi_aff_range_product(ma,
4772
10
            isl_multi_aff_from_aff(aff));
4773
10
  }
4774
11
4775
11
  insert = isl_map_from_multi_aff(isl_multi_aff_copy(ma));
4776
11
  map = isl_map_apply_domain(map, insert);
4777
11
  map = isl_map_equate(map, isl_dim_in, n_in, isl_dim_out, d);
4778
11
  pma = isl_pw_multi_aff_from_map(map);
4779
11
  pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma);
4780
11
4781
11
  return pma;
4782
0
error:
4783
0
  isl_map_free(map);
4784
0
  isl_basic_map_free(hull);
4785
0
  return NULL;
4786
11
}
4787
4788
/* Is constraint "c" of the form
4789
 *
4790
 *  e(...) + c1 - m x >= 0
4791
 *
4792
 * or
4793
 *
4794
 *  -e(...) + c2 + m x >= 0
4795
 *
4796
 * where m > 1 and e only depends on parameters and input dimemnsions?
4797
 *
4798
 * "offset" is the offset of the output dimensions
4799
 * "pos" is the position of output dimension x.
4800
 */
4801
static int is_potential_div_constraint(isl_int *c, int offset, int d, int total)
4802
106
{
4803
106
  if (isl_int_is_zero(c[offset + d]))
4804
82
    return 0;
4805
24
  
if (24
isl_int_is_one24
(c[offset + d]))
4806
6
    return 0;
4807
18
  
if (18
isl_int_is_negone18
(c[offset + d]))
4808
7
    return 0;
4809
11
  
if (11
isl_seq_first_non_zero(c + offset, d) != -111
)
4810
0
    return 0;
4811
11
  
if (11
isl_seq_first_non_zero(c + offset + d + 1,11
4812
11
            total - (offset + d + 1)) != -1)
4813
0
    return 0;
4814
11
  return 1;
4815
11
}
4816
4817
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4818
 *
4819
 * As a special case, we first check if there is any pair of constraints,
4820
 * shared by all the basic maps in "map" that force a given dimension
4821
 * to be equal to the floor of some affine combination of the input dimensions.
4822
 *
4823
 * In particular, if we can find two constraints
4824
 *
4825
 *  e(...) + c1 - m x >= 0    i.e.,   m x <= e(...) + c1
4826
 *
4827
 * and
4828
 *
4829
 *  -e(...) + c2 + m x >= 0   i.e.,   m x >= e(...) - c2
4830
 *
4831
 * where m > 1 and e only depends on parameters and input dimemnsions,
4832
 * and such that
4833
 *
4834
 *  c1 + c2 < m     i.e.,   -c2 >= c1 - (m - 1)
4835
 *
4836
 * then we know that we can take
4837
 *
4838
 *  x = floor((e(...) + c1) / m)
4839
 *
4840
 * without having to perform any computation.
4841
 *
4842
 * Note that we know that
4843
 *
4844
 *  c1 + c2 >= 1
4845
 *
4846
 * If c1 + c2 were 0, then we would have detected an equality during
4847
 * simplification.  If c1 + c2 were negative, then we would have detected
4848
 * a contradiction.
4849
 */
4850
static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_div(
4851
  __isl_take isl_map *map)
4852
19
{
4853
19
  int d, dim;
4854
19
  int i, j, n;
4855
19
  int offset, total;
4856
19
  isl_int sum;
4857
19
  isl_basic_map *hull;
4858
19
4859
19
  hull = isl_map_unshifted_simple_hull(isl_map_copy(map));
4860
19
  if (!hull)
4861
0
    goto error;
4862
19
4863
19
  
isl_int_init19
(sum);19
4864
19
  dim = isl_map_dim(map, isl_dim_out);
4865
19
  offset = isl_basic_map_offset(hull, isl_dim_out);
4866
19
  total = 1 + isl_basic_map_total_dim(hull);
4867
19
  n = hull->n_ineq;
4868
48
  for (d = 0; 
d < dim48
;
++d29
)
{40
4869
135
    for (i = 0; 
i < n135
;
++i95
)
{106
4870
106
      if (!is_potential_div_constraint(hull->ineq[i],
4871
106
              offset, d, total))
4872
95
        continue;
4873
11
      
for (j = i + 1; 11
j < n11
;
++j0
)
{11
4874
11
        if (!isl_seq_is_neg(hull->ineq[i] + 1,
4875
11
            hull->ineq[j] + 1, total - 1))
4876
0
          continue;
4877
11
        
isl_int_add11
(sum, hull->ineq[i][0],11
4878
11
            hull->ineq[j][0]);
4879
11
        if (isl_int_abs_lt(sum,
4880
11
                hull->ineq[i][offset + d]))
4881
11
          break;
4882
11
4883
11
      }
4884
11
      if (j >= n)
4885
0
        continue;
4886
11
      
isl_int_clear11
(sum);11
4887
11
      if (isl_int_is_pos(hull->ineq[j][offset + d]))
4888
0
        j = i;
4889
11
      return pw_multi_aff_from_map_div(map, hull, d, j);
4890
11
    }
4891
40
  }
4892
8
  
isl_int_clear8
(sum);8
4893
8
  isl_basic_map_free(hull);
4894
8
  return pw_multi_aff_from_map_base(map);
4895
0
error:
4896
0
  isl_map_free(map);
4897
0
  isl_basic_map_free(hull);
4898
0
  return NULL;
4899
19
}
4900
4901
/* Given an affine expression
4902
 *
4903
 *  [A -> B] -> f(A,B)
4904
 *
4905
 * construct an isl_multi_aff
4906
 *
4907
 *  [A -> B] -> B'
4908
 *
4909
 * such that dimension "d" in B' is set to "aff" and the remaining
4910
 * dimensions are set equal to the corresponding dimensions in B.
4911
 * "n_in" is the dimension of the space A.
4912
 * "n_out" is the dimension of the space B.
4913
 *
4914
 * If "is_set" is set, then the affine expression is of the form
4915
 *
4916
 *  [B] -> f(B)
4917
 *
4918
 * and we construct an isl_multi_aff
4919
 *
4920
 *  B -> B'
4921
 */
4922
static __isl_give isl_multi_aff *range_map(__isl_take isl_aff *aff, int d,
4923
  unsigned n_in, unsigned n_out, int is_set)
4924
4
{
4925
4
  int i;
4926
4
  isl_multi_aff *ma;
4927
4
  isl_space *space, *space2;
4928
4
  isl_local_space *ls;
4929
4
4930
4
  space = isl_aff_get_domain_space(aff);
4931
4
  ls = isl_local_space_from_space(isl_space_copy(space));
4932
4
  space2 = isl_space_copy(space);
4933
4
  if (!is_set)
4934
4
    space2 = isl_space_range(isl_space_unwrap(space2));
4935
4
  space = isl_space_map_from_domain_and_range(space, space2);
4936
4
  ma = isl_multi_aff_alloc(space);
4937
4
  ma = isl_multi_aff_set_aff(ma, d, aff);
4938
4
4939
21
  for (i = 0; 
i < n_out21
;
++i17
)
{17
4940
17
    if (i == d)
4941
4
      continue;
4942
13
    aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
4943
13
            isl_dim_set, n_in + i);
4944
13
    ma = isl_multi_aff_set_aff(ma, i, aff);
4945
13
  }
4946
4
4947
4
  isl_local_space_free(ls);
4948
4
4949
4
  return ma;
4950
4
}
4951
4952
/* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4953
 * taking into account that the dimension at position "d" can be written as
4954
 *
4955
 *  x = m a + f(..)           (1)
4956
 *
4957
 * where m is equal to "gcd".
4958
 * "i" is the index of the equality in "hull" that defines f(..).
4959
 * In particular, the equality is of the form
4960
 *
4961
 *  f(..) - x + m g(existentials) = 0
4962
 *
4963
 * or
4964
 *
4965
 *  -f(..) + x + m g(existentials) = 0
4966
 *
4967
 * We basically plug (1) into "map", resulting in a map with "a"
4968
 * in the range instead of "x".  The corresponding isl_pw_multi_aff
4969
 * defining "a" is then plugged back into (1) to obtain a definition for "x".
4970
 *
4971
 * Specifically, given the input map
4972
 *
4973
 *  A -> B
4974
 *
4975
 * We first wrap it into a set
4976
 *
4977
 *  [A -> B]
4978
 *
4979
 * and define (1) on top of the corresponding space, resulting in "aff".
4980