Coverage Report

Created: 2018-12-13 20:48

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