Coverage Report

Created: 2017-08-18 19:41

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