Merge branch 'maint'
[platform/upstream/isl.git] / isl_dim_map.c
1 /*
2  * Copyright 2008-2009 Katholieke Universiteit Leuven
3  * Copyright 2010-2011 INRIA Saclay
4  *
5  * Use of this software is governed by the GNU LGPLv2.1 license
6  *
7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
10  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
11  */
12
13 #include <isl_map_private.h>
14 #include <isl_space_private.h>
15 #include <isl_dim_map.h>
16 #include <isl_reordering.h>
17
18 struct isl_dim_map_entry {
19         int pos;
20         int sgn;
21 };
22
23 /* Maps dst positions to src positions */
24 struct isl_dim_map {
25         unsigned len;
26         struct isl_dim_map_entry m[1];
27 };
28
29 __isl_give isl_dim_map *isl_dim_map_alloc(isl_ctx *ctx, unsigned len)
30 {
31         int i;
32         struct isl_dim_map *dim_map;
33         dim_map = isl_alloc(ctx, struct isl_dim_map,
34             sizeof(struct isl_dim_map) + len * sizeof(struct isl_dim_map_entry));
35         if (!dim_map)
36                 return NULL;
37         dim_map->len = 1 + len;
38         dim_map->m[0].pos = 0;
39         dim_map->m[0].sgn = 1;
40         for (i = 0; i < len; ++i)
41                 dim_map->m[1 + i].sgn = 0;
42         return dim_map;
43 }
44
45 void isl_dim_map_range(__isl_keep isl_dim_map *dim_map,
46         unsigned dst_pos, unsigned dst_stride,
47         unsigned src_pos, unsigned src_stride,
48         unsigned n, int sign)
49 {
50         int i;
51
52         if (!dim_map)
53                 return;
54
55         for (i = 0; i < n; ++i) {
56                 unsigned d = 1 + dst_pos + dst_stride * i;
57                 unsigned s = 1 + src_pos + src_stride * i;
58                 dim_map->m[d].pos = s;
59                 dim_map->m[d].sgn = sign;
60         }
61 }
62
63 void isl_dim_map_dim_range(__isl_keep isl_dim_map *dim_map,
64         __isl_keep isl_space *dim, enum isl_dim_type type,
65         unsigned first, unsigned n, unsigned dst_pos)
66 {
67         int i;
68         unsigned src_pos;
69
70         if (!dim_map || !dim)
71                 return;
72         
73         src_pos = 1 + isl_space_offset(dim, type);
74         for (i = 0; i < n; ++i) {
75                 dim_map->m[1 + dst_pos + i].pos = src_pos + first + i;
76                 dim_map->m[1 + dst_pos + i].sgn = 1;
77         }
78 }
79
80 void isl_dim_map_dim(__isl_keep isl_dim_map *dim_map, __isl_keep isl_space *dim,
81         enum isl_dim_type type, unsigned dst_pos)
82 {
83         isl_dim_map_dim_range(dim_map, dim, type,
84                               0, isl_space_dim(dim, type), dst_pos);
85 }
86
87 void isl_dim_map_div(__isl_keep isl_dim_map *dim_map,
88         __isl_keep isl_basic_map *bmap, unsigned dst_pos)
89 {
90         int i;
91         unsigned src_pos;
92
93         if (!dim_map || !bmap)
94                 return;
95         
96         src_pos = 1 + isl_space_dim(bmap->dim, isl_dim_all);
97         for (i = 0; i < bmap->n_div; ++i) {
98                 dim_map->m[1 + dst_pos + i].pos = src_pos + i;
99                 dim_map->m[1 + dst_pos + i].sgn = 1;
100         }
101 }
102
103 void isl_dim_map_dump(struct isl_dim_map *dim_map)
104 {
105         int i;
106
107         for (i = 0; i < dim_map->len; ++i)
108                 fprintf(stderr, "%d -> %d * %d; ", i,
109                         dim_map->m[i].sgn, dim_map->m[i].pos);
110         fprintf(stderr, "\n");
111 }
112
113 static void copy_constraint_dim_map(isl_int *dst, isl_int *src,
114                                         struct isl_dim_map *dim_map)
115 {
116         int i;
117
118         for (i = 0; i < dim_map->len; ++i) {
119                 if (dim_map->m[i].sgn == 0)
120                         isl_int_set_si(dst[i], 0);
121                 else if (dim_map->m[i].sgn > 0)
122                         isl_int_set(dst[i], src[dim_map->m[i].pos]);
123                 else
124                         isl_int_neg(dst[i], src[dim_map->m[i].pos]);
125         }
126 }
127
128 static void copy_div_dim_map(isl_int *dst, isl_int *src,
129                                         struct isl_dim_map *dim_map)
130 {
131         isl_int_set(dst[0], src[0]);
132         copy_constraint_dim_map(dst+1, src+1, dim_map);
133 }
134
135 __isl_give isl_basic_map *isl_basic_map_add_constraints_dim_map(
136         __isl_take isl_basic_map *dst, __isl_take isl_basic_map *src,
137         __isl_take isl_dim_map *dim_map)
138 {
139         int i;
140
141         if (!src || !dst || !dim_map)
142                 goto error;
143
144         for (i = 0; i < src->n_eq; ++i) {
145                 int i1 = isl_basic_map_alloc_equality(dst);
146                 if (i1 < 0)
147                         goto error;
148                 copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map);
149         }
150
151         for (i = 0; i < src->n_ineq; ++i) {
152                 int i1 = isl_basic_map_alloc_inequality(dst);
153                 if (i1 < 0)
154                         goto error;
155                 copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map);
156         }
157
158         for (i = 0; i < src->n_div; ++i) {
159                 int i1 = isl_basic_map_alloc_div(dst);
160                 if (i1 < 0)
161                         goto error;
162                 copy_div_dim_map(dst->div[i1], src->div[i], dim_map);
163         }
164
165         free(dim_map);
166         isl_basic_map_free(src);
167
168         return dst;
169 error:
170         free(dim_map);
171         isl_basic_map_free(src);
172         isl_basic_map_free(dst);
173         return NULL;
174 }
175
176 __isl_give isl_basic_set *isl_basic_set_add_constraints_dim_map(
177         __isl_take isl_basic_set *dst, __isl_take isl_basic_set *src,
178         __isl_take isl_dim_map *dim_map)
179 {
180         return isl_basic_map_add_constraints_dim_map(dst, src, dim_map);
181 }
182
183 /* Extend the given dim_map with mappings for the divs in bmap.
184  */
185 __isl_give isl_dim_map *isl_dim_map_extend(__isl_keep isl_dim_map *dim_map,
186         __isl_keep isl_basic_map *bmap)
187 {
188         int i;
189         struct isl_dim_map *res;
190         int offset;
191
192         offset = isl_basic_map_offset(bmap, isl_dim_div);
193
194         res = isl_dim_map_alloc(bmap->ctx, dim_map->len - 1 + bmap->n_div);
195         if (!res)
196                 return NULL;
197
198         for (i = 0; i < dim_map->len; ++i)
199                 res->m[i] = dim_map->m[i];
200         for (i = 0; i < bmap->n_div; ++i) {
201                 res->m[dim_map->len + i].pos = offset + i;
202                 res->m[dim_map->len + i].sgn = 1;
203         }
204
205         return res;
206 }
207
208 /* Extract a dim_map from a reordering.
209  * We essentially need to reverse the mapping, and add an offset
210  * of 1 for the constant term.
211  */
212 __isl_give isl_dim_map *isl_dim_map_from_reordering(
213         __isl_keep isl_reordering *exp)
214 {
215         int i;
216         isl_ctx *ctx;
217         struct isl_dim_map *dim_map;
218
219         if (!exp)
220                 return NULL;
221
222         ctx = isl_space_get_ctx(exp->dim);
223         dim_map = isl_dim_map_alloc(ctx, isl_space_dim(exp->dim, isl_dim_all));
224         if (!dim_map)
225                 return NULL;
226
227         for (i = 0; i < exp->len; ++i) {
228                 dim_map->m[1 + exp->pos[i]].pos = 1 + i;
229                 dim_map->m[1 + exp->pos[i]].sgn = 1;
230         }
231
232         return dim_map;
233 }