1/*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2010-2011 INRIA Saclay
4 *
5 * Use of this software is governed by the MIT 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
18struct isl_dim_map_entry {
19	int pos;
20	int sgn;
21};
22
23/* Maps dst positions to src positions */
24struct 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
45void 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
63void 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
80void 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
87void 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
103void 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
113static 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
128static 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;
169error:
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}
234