add isl_aff_ge_basic_set
[platform/upstream/isl.git] / isl_aff.c
1 /*
2  * Copyright 2011      INRIA Saclay
3  *
4  * Use of this software is governed by the GNU LGPLv2.1 license
5  *
6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8  * 91893 Orsay, France
9  */
10
11 #include <isl_map_private.h>
12 #include <isl_aff_private.h>
13 #include <isl_local_space_private.h>
14 #include <isl_mat_private.h>
15 #include <isl/constraint.h>
16 #include <isl/seq.h>
17 #include <isl/set.h>
18
19 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
20         __isl_take isl_vec *v)
21 {
22         isl_aff *aff;
23
24         if (!ls || !v)
25                 goto error;
26
27         aff = isl_calloc_type(v->ctx, struct isl_aff);
28         if (!aff)
29                 goto error;
30
31         aff->ref = 1;
32         aff->ls = ls;
33         aff->v = v;
34
35         return aff;
36 error:
37         isl_local_space_free(ls);
38         isl_vec_free(v);
39         return NULL;
40 }
41
42 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
43 {
44         isl_ctx *ctx;
45         isl_vec *v;
46         unsigned total;
47
48         if (!ls)
49                 return NULL;
50
51         ctx = isl_local_space_get_ctx(ls);
52         if (!isl_local_space_divs_known(ls))
53                 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
54                         goto error);
55
56         total = isl_local_space_dim(ls, isl_dim_all);
57         v = isl_vec_alloc(ctx, 1 + 1 + total);
58         return isl_aff_alloc_vec(ls, v);
59 error:
60         isl_local_space_free(ls);
61         return NULL;
62 }
63
64 __isl_give isl_aff *isl_aff_zero(__isl_take isl_local_space *ls)
65 {
66         isl_aff *aff;
67
68         aff = isl_aff_alloc(ls);
69         if (!aff)
70                 return NULL;
71
72         isl_int_set_si(aff->v->el[0], 1);
73         isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
74
75         return aff;
76 }
77
78 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
79 {
80         if (!aff)
81                 return NULL;
82
83         aff->ref++;
84         return aff;
85 }
86
87 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
88 {
89         if (!aff)
90                 return NULL;
91
92         return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
93                                  isl_vec_copy(aff->v));
94 }
95
96 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
97 {
98         if (!aff)
99                 return NULL;
100
101         if (aff->ref == 1)
102                 return aff;
103         aff->ref--;
104         return isl_aff_dup(aff);
105 }
106
107 void *isl_aff_free(__isl_take isl_aff *aff)
108 {
109         if (!aff)
110                 return NULL;
111
112         if (--aff->ref > 0)
113                 return NULL;
114
115         isl_local_space_free(aff->ls);
116         isl_vec_free(aff->v);
117
118         free(aff);
119
120         return NULL;
121 }
122
123 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
124 {
125         return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
126 }
127
128 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
129 {
130         return aff ? isl_local_space_dim(aff->ls, type) : 0;
131 }
132
133 __isl_give isl_dim *isl_aff_get_dim(__isl_keep isl_aff *aff)
134 {
135         return aff ? isl_local_space_get_dim(aff->ls) : NULL;
136 }
137
138 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
139 {
140         return aff ? isl_local_space_copy(aff->ls) : NULL;
141 }
142
143 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
144         enum isl_dim_type type, unsigned pos)
145 {
146         return aff ? isl_local_space_get_dim_name(aff->ls, type, pos) : 0;
147 }
148
149 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
150 {
151         if (!aff)
152                 return -1;
153
154         return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
155 }
156
157 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
158 {
159         int equal;
160
161         if (!aff1 || !aff2)
162                 return -1;
163
164         equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
165         if (equal < 0 || !equal)
166                 return equal;
167
168         return isl_vec_is_equal(aff1->v, aff2->v);
169 }
170
171 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
172 {
173         if (!aff)
174                 return -1;
175         isl_int_set(*v, aff->v->el[0]);
176         return 0;
177 }
178
179 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
180 {
181         if (!aff)
182                 return -1;
183         isl_int_set(*v, aff->v->el[1]);
184         return 0;
185 }
186
187 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
188         enum isl_dim_type type, int pos, isl_int *v)
189 {
190         if (!aff)
191                 return -1;
192
193         if (pos >= isl_local_space_dim(aff->ls, type))
194                 isl_die(aff->v->ctx, isl_error_invalid,
195                         "position out of bounds", return -1);
196
197         pos += isl_local_space_offset(aff->ls, type);
198         isl_int_set(*v, aff->v->el[1 + pos]);
199
200         return 0;
201 }
202
203 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
204 {
205         aff = isl_aff_cow(aff);
206         if (!aff)
207                 return NULL;
208
209         aff->v = isl_vec_cow(aff->v);
210         if (!aff->v)
211                 return isl_aff_free(aff);
212
213         isl_int_set(aff->v->el[0], v);
214
215         return aff;
216 }
217
218 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
219 {
220         aff = isl_aff_cow(aff);
221         if (!aff)
222                 return NULL;
223
224         aff->v = isl_vec_cow(aff->v);
225         if (!aff->v)
226                 return isl_aff_free(aff);
227
228         isl_int_set(aff->v->el[1], v);
229
230         return aff;
231 }
232
233 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
234 {
235         if (isl_int_is_zero(v))
236                 return aff;
237
238         aff = isl_aff_cow(aff);
239         if (!aff)
240                 return NULL;
241
242         aff->v = isl_vec_cow(aff->v);
243         if (!aff->v)
244                 return isl_aff_free(aff);
245
246         isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
247
248         return aff;
249 }
250
251 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
252 {
253         isl_int t;
254
255         isl_int_init(t);
256         isl_int_set_si(t, v);
257         aff = isl_aff_add_constant(aff, t);
258         isl_int_clear(t);
259
260         return aff;
261 }
262
263 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
264 {
265         aff = isl_aff_cow(aff);
266         if (!aff)
267                 return NULL;
268
269         aff->v = isl_vec_cow(aff->v);
270         if (!aff->v)
271                 return isl_aff_free(aff);
272
273         isl_int_set_si(aff->v->el[1], v);
274
275         return aff;
276 }
277
278 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
279         enum isl_dim_type type, int pos, isl_int v)
280 {
281         if (!aff)
282                 return NULL;
283
284         if (pos >= isl_local_space_dim(aff->ls, type))
285                 isl_die(aff->v->ctx, isl_error_invalid,
286                         "position out of bounds", return isl_aff_free(aff));
287
288         aff = isl_aff_cow(aff);
289         if (!aff)
290                 return NULL;
291
292         aff->v = isl_vec_cow(aff->v);
293         if (!aff->v)
294                 return isl_aff_free(aff);
295
296         pos += isl_local_space_offset(aff->ls, type);
297         isl_int_set(aff->v->el[1 + pos], v);
298
299         return aff;
300 }
301
302 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
303         enum isl_dim_type type, int pos, int v)
304 {
305         if (!aff)
306                 return NULL;
307
308         if (pos >= isl_local_space_dim(aff->ls, type))
309                 isl_die(aff->v->ctx, isl_error_invalid,
310                         "position out of bounds", return isl_aff_free(aff));
311
312         aff = isl_aff_cow(aff);
313         if (!aff)
314                 return NULL;
315
316         aff->v = isl_vec_cow(aff->v);
317         if (!aff->v)
318                 return isl_aff_free(aff);
319
320         pos += isl_local_space_offset(aff->ls, type);
321         isl_int_set_si(aff->v->el[1 + pos], v);
322
323         return aff;
324 }
325
326 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
327         enum isl_dim_type type, int pos, isl_int v)
328 {
329         if (!aff)
330                 return NULL;
331
332         if (pos >= isl_local_space_dim(aff->ls, type))
333                 isl_die(aff->v->ctx, isl_error_invalid,
334                         "position out of bounds", return isl_aff_free(aff));
335
336         aff = isl_aff_cow(aff);
337         if (!aff)
338                 return NULL;
339
340         aff->v = isl_vec_cow(aff->v);
341         if (!aff->v)
342                 return isl_aff_free(aff);
343
344         pos += isl_local_space_offset(aff->ls, type);
345         isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
346
347         return aff;
348 }
349
350 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
351         enum isl_dim_type type, int pos, int v)
352 {
353         isl_int t;
354
355         isl_int_init(t);
356         isl_int_set_si(t, v);
357         aff = isl_aff_add_coefficient(aff, type, pos, t);
358         isl_int_clear(t);
359
360         return aff;
361 }
362
363 __isl_give isl_div *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
364 {
365         if (!aff)
366                 return NULL;
367
368         return isl_local_space_get_div(aff->ls, pos);
369 }
370
371 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
372 {
373         aff = isl_aff_cow(aff);
374         if (!aff)
375                 return NULL;
376         aff->v = isl_vec_cow(aff->v);
377         if (!aff->v)
378                 return isl_aff_free(aff);
379
380         isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
381
382         return aff;
383 }
384
385 /* Given f, return floor(f).
386  * If f is an integer expression, then just return f.
387  * Otherwise, create a new div d = [f] and return the expression d.
388  */
389 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
390 {
391         int size;
392         isl_ctx *ctx;
393
394         if (!aff)
395                 return NULL;
396
397         if (isl_int_is_one(aff->v->el[0]))
398                 return aff;
399
400         aff = isl_aff_cow(aff);
401         if (!aff)
402                 return NULL;
403
404         aff->ls = isl_local_space_add_div(aff->ls, isl_vec_copy(aff->v));
405         if (!aff->ls)
406                 return isl_aff_free(aff);
407
408         ctx = isl_aff_get_ctx(aff);
409         size = aff->v->size;
410         isl_vec_free(aff->v);
411         aff->v = isl_vec_alloc(ctx, size + 1);
412         aff->v = isl_vec_clr(aff->v);
413         if (!aff->v)
414                 return isl_aff_free(aff);
415         isl_int_set_si(aff->v->el[0], 1);
416         isl_int_set_si(aff->v->el[size], 1);
417
418         return aff;
419 }
420
421 /* Given f, return ceil(f).
422  * If f is an integer expression, then just return f.
423  * Otherwise, create a new div d = [-f] and return the expression -d.
424  */
425 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
426 {
427         if (!aff)
428                 return NULL;
429
430         if (isl_int_is_one(aff->v->el[0]))
431                 return aff;
432
433         aff = isl_aff_neg(aff);
434         aff = isl_aff_floor(aff);
435         aff = isl_aff_neg(aff);
436
437         return aff;
438 }
439
440 /* Apply the expansion computed by isl_merge_divs.
441  * The expansion itself is given by "exp" while the resulting
442  * list of divs is given by "div".
443  */
444 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
445         __isl_take isl_mat *div, int *exp)
446 {
447         int i, j;
448         int old_n_div;
449         int new_n_div;
450         int offset;
451
452         aff = isl_aff_cow(aff);
453         if (!aff || !div)
454                 goto error;
455
456         old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
457         new_n_div = isl_mat_rows(div);
458         if (new_n_div < old_n_div)
459                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
460                         "not an expansion", goto error);
461
462         aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
463         if (!aff->v)
464                 goto error;
465
466         offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
467         j = old_n_div - 1;
468         for (i = new_n_div - 1; i >= 0; --i) {
469                 if (j >= 0 && exp[j] == i) {
470                         if (i != j)
471                                 isl_int_swap(aff->v->el[offset + i],
472                                              aff->v->el[offset + j]);
473                         j--;
474                 } else
475                         isl_int_set_si(aff->v->el[offset + i], 0);
476         }
477
478         aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
479         if (!aff->ls)
480                 goto error;
481         isl_mat_free(div);
482         return aff;
483 error:
484         isl_aff_free(aff);
485         isl_mat_free(div);
486         return NULL;
487 }
488
489 /* Add two affine expressions that live in the same local space.
490  */
491 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
492         __isl_take isl_aff *aff2)
493 {
494         isl_int gcd, f;
495
496         aff1 = isl_aff_cow(aff1);
497         if (!aff1 || !aff2)
498                 goto error;
499
500         aff1->v = isl_vec_cow(aff1->v);
501         if (!aff1->v)
502                 goto error;
503
504         isl_int_init(gcd);
505         isl_int_init(f);
506         isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
507         isl_int_divexact(f, aff2->v->el[0], gcd);
508         isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
509         isl_int_divexact(f, aff1->v->el[0], gcd);
510         isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
511         isl_int_divexact(f, aff2->v->el[0], gcd);
512         isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
513         isl_int_clear(f);
514         isl_int_clear(gcd);
515
516         isl_aff_free(aff2);
517         return aff1;
518 error:
519         isl_aff_free(aff1);
520         isl_aff_free(aff2);
521         return NULL;
522 }
523
524 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
525         __isl_take isl_aff *aff2)
526 {
527         isl_ctx *ctx;
528         int *exp1 = NULL;
529         int *exp2 = NULL;
530         isl_mat *div;
531
532         if (!aff1 || !aff2)
533                 goto error;
534
535         ctx = isl_aff_get_ctx(aff1);
536         if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
537                 isl_die(ctx, isl_error_invalid,
538                         "spaces don't match", goto error);
539
540         if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
541                 return add_expanded(aff1, aff2);
542
543         exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
544         exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
545         if (!exp1 || !exp2)
546                 goto error;
547
548         div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
549         aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
550         aff2 = isl_aff_expand_divs(aff2, div, exp2);
551         free(exp1);
552         free(exp2);
553
554         return add_expanded(aff1, aff2);
555 error:
556         free(exp1);
557         free(exp2);
558         isl_aff_free(aff1);
559         isl_aff_free(aff2);
560         return NULL;
561 }
562
563 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
564         __isl_take isl_aff *aff2)
565 {
566         return isl_aff_add(aff1, isl_aff_neg(aff2));
567 }
568
569 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
570 {
571         isl_int gcd;
572
573         if (isl_int_is_one(f))
574                 return aff;
575
576         aff = isl_aff_cow(aff);
577         if (!aff)
578                 return NULL;
579         aff->v = isl_vec_cow(aff->v);
580         if (!aff->v)
581                 return isl_aff_free(aff);
582
583         isl_int_init(gcd);
584         isl_int_gcd(gcd, aff->v->el[0], f);
585         isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
586         isl_int_divexact(gcd, f, gcd);
587         isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
588         isl_int_clear(gcd);
589
590         return aff;
591 }
592
593 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
594 {
595         isl_int gcd;
596
597         if (isl_int_is_one(f))
598                 return aff;
599
600         aff = isl_aff_cow(aff);
601         if (!aff)
602                 return NULL;
603         aff->v = isl_vec_cow(aff->v);
604         if (!aff->v)
605                 return isl_aff_free(aff);
606
607         isl_int_init(gcd);
608         isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
609         isl_int_gcd(gcd, gcd, f);
610         isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
611         isl_int_divexact(gcd, f, gcd);
612         isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
613         isl_int_clear(gcd);
614
615         return aff;
616 }
617
618 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
619 {
620         isl_int v;
621
622         if (f == 1)
623                 return aff;
624
625         isl_int_init(v);
626         isl_int_set_ui(v, f);
627         aff = isl_aff_scale_down(aff, v);
628         isl_int_clear(v);
629
630         return aff;
631 }
632
633 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
634         enum isl_dim_type type, unsigned pos, const char *s)
635 {
636         aff = isl_aff_cow(aff);
637         if (!aff)
638                 return NULL;
639         aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
640         if (!aff->ls)
641                 return isl_aff_free(aff);
642
643         return aff;
644 }
645
646 /* Exploit the equalities in "eq" to simplify the affine expression
647  * and the expressions of the integer divisions in the local space.
648  * The integer divisions in this local space are assumed to appear
649  * as regular dimensions in "eq".
650  */
651 static __isl_give isl_aff *isl_aff_substitute_equalities(
652         __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
653 {
654         int i, j;
655         unsigned total;
656         unsigned n_div;
657
658         if (!eq)
659                 goto error;
660         if (eq->n_eq == 0) {
661                 isl_basic_set_free(eq);
662                 return aff;
663         }
664
665         aff = isl_aff_cow(aff);
666         if (!aff)
667                 goto error;
668
669         aff->ls = isl_local_space_substitute_equalities(aff->ls,
670                                                         isl_basic_set_copy(eq));
671         if (!aff->ls)
672                 goto error;
673
674         total = 1 + isl_dim_total(eq->dim);
675         n_div = eq->n_div;
676         for (i = 0; i < eq->n_eq; ++i) {
677                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
678                 if (j < 0 || j == 0 || j >= total)
679                         continue;
680
681                 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
682                                 &aff->v->el[0]);
683         }
684
685         isl_basic_set_free(eq);
686         return aff;
687 error:
688         isl_basic_set_free(eq);
689         isl_aff_free(aff);
690         return NULL;
691 }
692
693 /* Look for equalities among the variables shared by context and aff
694  * and the integer divisions of aff, if any.
695  * The equalities are then used to eliminate coefficients and/or integer
696  * divisions from aff.
697  */
698 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
699         __isl_take isl_set *context)
700 {
701         isl_basic_set *hull;
702         int n_div;
703
704         if (!aff)
705                 goto error;
706         n_div = isl_local_space_dim(aff->ls, isl_dim_div);
707         if (n_div > 0) {
708                 isl_basic_set *bset;
709                 context = isl_set_add_dims(context, isl_dim_set, n_div);
710                 bset = isl_basic_set_from_local_space(
711                                             isl_aff_get_local_space(aff));
712                 bset = isl_basic_set_lift(bset);
713                 bset = isl_basic_set_flatten(bset);
714                 context = isl_set_intersect(context,
715                                             isl_set_from_basic_set(bset));
716         }
717
718         hull = isl_set_affine_hull(context);
719         return isl_aff_substitute_equalities(aff, hull);
720 error:
721         isl_aff_free(aff);
722         isl_set_free(context);
723         return NULL;
724 }
725
726 /* Return a basic set containing those elements in the shared space
727  * of aff1 and aff2 where aff1 is greater than or equal to aff2.
728  */
729 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
730         __isl_take isl_aff *aff2)
731 {
732         isl_constraint *ineq;
733
734         aff1 = isl_aff_sub(aff1, aff2);
735         ineq = isl_inequality_from_aff(aff1);
736
737         return isl_basic_set_from_constraint(ineq);
738 }