Coverage Report

Created: 2017-06-28 17:40

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