Coverage Report

Created: 2018-04-24 22:41

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