?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
generalize isl_multi_aff_flat_range_product
[isl.git] / isl_multi_templ.c
blob8bd40a68b74e75a96aa1e852ae7ed4a2d8b0a0df
1 /*
2 * Copyright 2011 Sven Verdoolaege
3 * Copyright 2012 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 */
10
11 #define xCAT(A,B) A ## B
12 #define CAT(A,B) xCAT(A,B)
13 #undef EL
14 #define EL CAT(isl_,BASE)
15 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
16 #define FN(TYPE,NAME) xFN(TYPE,NAME)
17 #define xMULTI(BASE) isl_multi_ ## BASE
18 #define MULTI(BASE) xMULTI(BASE)
19 #define MULTI_NAME(BASE) "isl_multi_" #BASE
20 #define xLIST(EL) EL ## _list
21 #define LIST(EL) xLIST(EL)
22
23 isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
24 {
25 return multi ? isl_space_get_ctx(multi->space) : NULL;
26 }
27
28 __isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)
29 {
30 return multi ? isl_space_copy(multi->space) : NULL;
31 }
32
33 __isl_give isl_space *FN(MULTI(BASE),get_domain_space)(
34 __isl_keep MULTI(BASE) *multi)
35 {
36 return multi ? isl_space_domain(isl_space_copy(multi->space)) : NULL;
37 }
38
39 __isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space)
40 {
41 isl_ctx *ctx;
42 int n;
43 MULTI(BASE) *multi;
44
45 if (!space)
46 return NULL;
47
48 ctx = isl_space_get_ctx(space);
49 n = isl_space_dim(space, isl_dim_out);
50 multi = isl_calloc(ctx, MULTI(BASE),
51 sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *));
52 if (!multi)
53 goto error;
54
55 multi->space = space;
56 multi->n = n;
57 multi->ref = 1;
58 return multi;
59 error:
60 isl_space_free(space);
61 return NULL;
62 }
63
64 __isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi)
65 {
66 int i;
67 MULTI(BASE) *dup;
68
69 if (!multi)
70 return NULL;
71
72 dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space));
73 if (!dup)
74 return NULL;
75
76 for (i = 0; i < multi->n; ++i)
77 dup = FN(FN(MULTI(BASE),set),BASE)(dup, i,
78 FN(EL,copy)(multi->p[i]));
79
80 return dup;
81 }
82
83 __isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi)
84 {
85 if (!multi)
86 return NULL;
87
88 if (multi->ref == 1)
89 return multi;
90
91 multi->ref--;
92 return FN(MULTI(BASE),dup)(multi);
93 }
94
95 __isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi)
96 {
97 if (!multi)
98 return NULL;
99
100 multi->ref++;
101 return multi;
102 }
103
104 void *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi)
105 {
106 int i;
107
108 if (!multi)
109 return NULL;
110
111 if (--multi->ref > 0)
112 return NULL;
113
114 isl_space_free(multi->space);
115 for (i = 0; i < multi->n; ++i)
116 FN(EL,free)(multi->p[i]);
117 free(multi);
118
119 return NULL;
120 }
121
122 unsigned FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
123 enum isl_dim_type type)
124 {
125 return multi ? isl_space_dim(multi->space, type) : 0;
126 }
127
128 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_name)(
129 __isl_take MULTI(BASE) *multi,
130 enum isl_dim_type type, unsigned pos, const char *s)
131 {
132 int i;
133
134 multi = FN(MULTI(BASE),cow)(multi);
135 if (!multi)
136 return NULL;
137
138 multi->space = isl_space_set_dim_name(multi->space, type, pos, s);
139 if (!multi->space)
140 return FN(MULTI(BASE),free)(multi);
141
142 if (type == isl_dim_out)
143 return multi;
144 for (i = 0; i < multi->n; ++i) {
145 multi->p[i] = FN(EL,set_dim_name)(multi->p[i], type, pos, s);
146 if (!multi->p[i])
147 return FN(MULTI(BASE),free)(multi);
148 }
149
150 return multi;
151 }
152
153 const char *FN(MULTI(BASE),get_tuple_name)(__isl_keep MULTI(BASE) *multi,
154 enum isl_dim_type type)
155 {
156 return multi ? isl_space_get_tuple_name(multi->space, type) : NULL;
157 }
158
159 __isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
160 int pos)
161 {
162 isl_ctx *ctx;
163
164 if (!multi)
165 return NULL;
166 ctx = FN(MULTI(BASE),get_ctx)(multi);
167 if (pos < 0 || pos >= multi->n)
168 isl_die(ctx, isl_error_invalid,
169 "index out of bounds", return NULL);
170 return FN(EL,copy)(multi->p[pos]);
171 }
172
173 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
174 __isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
175 {
176 isl_space *multi_space = NULL;
177 isl_space *el_space = NULL;
178
179 multi = FN(MULTI(BASE),cow)(multi);
180 if (!multi || !el)
181 goto error;
182
183 multi_space = FN(MULTI(BASE),get_space)(multi);
184 el_space = FN(EL,get_space)(el);
185
186 if (!isl_space_match(multi_space, isl_dim_param,
187 el_space, isl_dim_param))
188 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
189 "parameters don't match", goto error);
190 if (!isl_space_tuple_match(multi_space, isl_dim_in,
191 el_space, isl_dim_in))
192 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
193 "domains don't match", goto error);
194
195 if (pos < 0 || pos >= multi->n)
196 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
197 "index out of bounds", goto error);
198
199 FN(EL,free)(multi->p[pos]);
200 multi->p[pos] = el;
201
202 isl_space_free(multi_space);
203 isl_space_free(el_space);
204
205 return multi;
206 error:
207 FN(MULTI(BASE),free)(multi);
208 FN(EL,free)(el);
209 isl_space_free(multi_space);
210 isl_space_free(el_space);
211 return NULL;
212 }
213
214 /* Reset the space of "multi". This function is called from isl_pw_templ.c
215 * and doesn't know if the space of an element object is represented
216 * directly or through its domain. It therefore passes along both,
217 * which we pass along to the element function since we don't how
218 * that is represented either.
219 */
220 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
221 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
222 __isl_take isl_space *domain)
223 {
224 int i;
225
226 multi = FN(MULTI(BASE),cow)(multi);
227 if (!multi || !space || !domain)
228 goto error;
229
230 for (i = 0; i < multi->n; ++i) {
231 multi->p[i] = FN(EL,reset_space_and_domain)(multi->p[i],
232 isl_space_copy(space), isl_space_copy(domain));
233 if (!multi->p[i])
234 goto error;
235 }
236 isl_space_free(domain);
237 isl_space_free(multi->space);
238 multi->space = space;
239
240 return multi;
241 error:
242 isl_space_free(domain);
243 isl_space_free(space);
244 FN(MULTI(BASE),free)(multi);
245 return NULL;
246 }
247
248 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
249 __isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
250 {
251 isl_space *space;
252
253 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
254 isl_space_copy(multi->space));
255 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
256 }
257
258 __isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
259 __isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
260 {
261 isl_space *domain;
262
263 domain = isl_space_domain(isl_space_copy(space));
264 return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
265 }
266
267 __isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
268 __isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
269 __isl_take isl_id *id)
270 {
271 isl_space *space;
272
273 multi = FN(MULTI(BASE),cow)(multi);
274 if (!multi)
275 return isl_id_free(id);
276
277 space = FN(MULTI(BASE),get_space)(multi);
278 space = isl_space_set_tuple_id(space, type, id);
279
280 return FN(MULTI(BASE),reset_space)(multi, space);
281 }
282
283 __isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
284 __isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
285 {
286 int i;
287
288 multi = FN(MULTI(BASE),cow)(multi);
289 if (!multi || !exp)
290 return NULL;
291
292 for (i = 0; i < multi->n; ++i) {
293 multi->p[i] = FN(EL,realign_domain)(multi->p[i],
294 isl_reordering_copy(exp));
295 if (!multi->p[i])
296 goto error;
297 }
298
299 multi = FN(MULTI(BASE),reset_domain_space)(multi,
300 isl_space_copy(exp->dim));
301
302 isl_reordering_free(exp);
303 return multi;
304 error:
305 isl_reordering_free(exp);
306 FN(MULTI(BASE),free)(multi);
307 return NULL;
308 }
309
310 /* Align the parameters of "multi" to those of "model".
311 */
312 __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
313 __isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
314 {
315 isl_ctx *ctx;
316
317 if (!multi || !model)
318 goto error;
319
320 ctx = isl_space_get_ctx(model);
321 if (!isl_space_has_named_params(model))
322 isl_die(ctx, isl_error_invalid,
323 "model has unnamed parameters", goto error);
324 if (!isl_space_has_named_params(multi->space))
325 isl_die(ctx, isl_error_invalid,
326 "input has unnamed parameters", goto error);
327 if (!isl_space_match(multi->space, isl_dim_param,
328 model, isl_dim_param)) {
329 isl_reordering *exp;
330
331 model = isl_space_params(model);
332 exp = isl_parameter_alignment_reordering(multi->space, model);
333 exp = isl_reordering_extend_space(exp,
334 FN(MULTI(BASE),get_domain_space)(multi));
335 multi = FN(MULTI(BASE),realign_domain)(multi, exp);
336 }
337
338 isl_space_free(model);
339 return multi;
340 error:
341 isl_space_free(model);
342 FN(MULTI(BASE),free)(multi);
343 return NULL;
344 }
345
346 static __isl_give MULTI(BASE) *align_params_multi_set_and(
347 __isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
348 __isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
349 __isl_take isl_set *set))
350 {
351 isl_ctx *ctx;
352
353 if (!multi || !set)
354 goto error;
355 if (isl_space_match(multi->space, isl_dim_param,
356 set->dim, isl_dim_param))
357 return fn(multi, set);
358 ctx = FN(MULTI(BASE),get_ctx)(multi);
359 if (!isl_space_has_named_params(multi->space) ||
360 !isl_space_has_named_params(set->dim))
361 isl_die(ctx, isl_error_invalid,
362 "unaligned unnamed parameters", goto error);
363 multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
364 set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
365 return fn(multi, set);
366 error:
367 FN(MULTI(BASE),free)(multi);
368 isl_set_free(set);
369 return NULL;
370 }
371
372 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
373 __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
374 {
375 int i;
376
377 if (!multi || !context)
378 goto error;
379
380 for (i = 0; i < multi->n; ++i) {
381 multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
382 if (!multi->p[i])
383 goto error;
384 }
385
386 isl_set_free(context);
387 return multi;
388 error:
389 isl_set_free(context);
390 FN(MULTI(BASE),free)(multi);
391 return NULL;
392 }
393
394 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
395 __isl_take isl_set *context)
396 {
397 return align_params_multi_set_and(multi, context,
398 &FN(MULTI(BASE),gist_aligned));
399 }
400
401 __isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
402 __isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
403 {
404 isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
405 isl_set *dom_context = isl_set_universe(space);
406 dom_context = isl_set_intersect_params(dom_context, context);
407 return FN(MULTI(BASE),gist)(multi, dom_context);
408 }
409
410 __isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
411 __isl_take isl_space *space, __isl_take LIST(EL) *list)
412 {
413 int i;
414 int n;
415 isl_ctx *ctx;
416 MULTI(BASE) *multi;
417
418 if (!space || !list)
419 goto error;
420
421 ctx = isl_space_get_ctx(space);
422 n = FN(FN(LIST(EL),n),BASE)(list);
423 if (n != isl_space_dim(space, isl_dim_out))
424 isl_die(ctx, isl_error_invalid,
425 "invalid number of elements in list", goto error);
426
427 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
428 for (i = 0; i < n; ++i) {
429 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
430 FN(FN(LIST(EL),get),BASE)(list, i));
431 }
432
433 isl_space_free(space);
434 FN(LIST(EL),free)(list);
435 return multi;
436 error:
437 isl_space_free(space);
438 FN(LIST(EL),free)(list);
439 return NULL;
440 }
441
442 /* Create a multi expression in the given space that maps each
443 * input dimension to the corresponding output dimension.
444 */
445 __isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
446 {
447 int i, n;
448 isl_local_space *ls;
449 MULTI(BASE) *multi;
450
451 if (!space)
452 return NULL;
453
454 if (isl_space_is_set(space))
455 isl_die(isl_space_get_ctx(space), isl_error_invalid,
456 "expecting map space", goto error);
457
458 n = isl_space_dim(space, isl_dim_out);
459 if (n != isl_space_dim(space, isl_dim_in))
460 isl_die(isl_space_get_ctx(space), isl_error_invalid,
461 "number of input and output dimensions needs to be "
462 "the same", goto error);
463
464 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
465
466 if (!n) {
467 isl_space_free(space);
468 return multi;
469 }
470
471 space = isl_space_domain(space);
472 ls = isl_local_space_from_space(space);
473
474 for (i = 0; i < n; ++i) {
475 EL *el;
476 el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
477 isl_dim_set, i);
478 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
479 }
480
481 isl_local_space_free(ls);
482
483 return multi;
484 error:
485 isl_space_free(space);
486 return NULL;
487 }
488
489 /* Construct a multi expression in the given space with value zero in
490 * each of the output dimensions.
491 */
492 __isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
493 {
494 int n;
495 MULTI(BASE) *multi;
496
497 if (!space)
498 return NULL;
499
500 n = isl_space_dim(space , isl_dim_out);
501 multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
502
503 if (!n)
504 isl_space_free(space);
505 else {
506 int i;
507 isl_local_space *ls;
508 EL *el;
509
510 space = isl_space_domain(space);
511 ls = isl_local_space_from_space(space);
512 el = FN(EL,zero_on_domain)(ls);
513
514 for (i = 0; i < n; ++i)
515 multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
516 FN(EL,copy)(el));
517
518 FN(EL,free)(el);
519 }
520
521 return multi;
522 }
523
524 __isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
525 __isl_take MULTI(BASE) *multi,
526 enum isl_dim_type type, unsigned first, unsigned n)
527 {
528 int i;
529 unsigned dim;
530
531 multi = FN(MULTI(BASE),cow)(multi);
532 if (!multi)
533 return NULL;
534
535 dim = FN(MULTI(BASE),dim)(multi, type);
536 if (first + n > dim || first + n < first)
537 isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
538 "index out of bounds",
539 return FN(MULTI(BASE),cow)(multi));
540
541 multi->space = isl_space_drop_dims(multi->space, type, first, n);
542 if (!multi->space)
543 return FN(MULTI(BASE),cow)(multi);
544
545 if (type == isl_dim_out) {
546 for (i = 0; i < n; ++i)
547 FN(EL,free)(multi->p[first + i]);
548 for (i = first; i + n < multi->n; ++i)
549 multi->p[i] = multi->p[i + n];
550 multi->n -= n;
551
552 return multi;
553 }
554
555 for (i = 0; i < multi->n; ++i) {
556 multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
557 if (!multi->p[i])
558 return FN(MULTI(BASE),cow)(multi);
559 }
560
561 return multi;
562 }
563
564 /* Given two MULTI(BASE)s A -> B and C -> D,
565 * construct a MULTI(BASE) (A * C) -> (B, D).
566 */
567 __isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
568 __isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
569 {
570 int i, n1, n2;
571 EL *el;
572 isl_space *space;
573 MULTI(BASE) *res;
574
575 if (!multi1 || !multi2)
576 goto error;
577
578 space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
579 FN(MULTI(BASE),get_space)(multi2));
580 space = isl_space_flatten_range(space);
581 res = FN(MULTI(BASE),alloc)(space);
582
583 n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
584 n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
585
586 for (i = 0; i < n1; ++i) {
587 el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
588 res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
589 }
590
591 for (i = 0; i < n2; ++i) {
592 el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
593 res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
594 }
595
596 FN(MULTI(BASE),free)(multi1);
597 FN(MULTI(BASE),free)(multi2);
598 return res;
599 error:
600 FN(MULTI(BASE),free)(multi1);
601 FN(MULTI(BASE),free)(multi2);
602 return NULL;
603 }
Integer set library