File: isl_box.c

package info (click to toggle)
isl 0.20-2
  • links: PTS
  • area: main
  • in suites: buster, sid
  • size: 12,708 kB
  • sloc: ansic: 125,702; python: 5,770; sh: 4,291; cpp: 1,057; makefile: 497; lisp: 54; perl: 9
file content (368 lines) | stat: -rw-r--r-- 10,199 bytes parent folder | download | duplicates (10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
/*
 * Copyright 2010-2011 INRIA Saclay
 * Copyright 2012-2013 Ecole Normale Superieure
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
 * 91893 Orsay, France
 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
 */

#include <isl/val.h>
#include <isl/space.h>
#include <isl_map_private.h>
#include <isl_aff_private.h>
#include <isl/constraint.h>
#include <isl/ilp.h>
#include <isl/fixed_box.h>

/* Representation of a box of fixed size containing the elements
 * [offset, offset + size).
 * "size" lives in the target space of "offset".
 *
 * If any of the "offsets" is NaN, then the object represents
 * the failure of finding a fixed-size box.
 */
struct isl_fixed_box {
	isl_multi_aff *offset;
	isl_multi_val *size;
};

/* Free "box" and return NULL.
 */
__isl_null isl_fixed_box *isl_fixed_box_free(__isl_take isl_fixed_box *box)
{
	if (!box)
		return NULL;
	isl_multi_aff_free(box->offset);
	isl_multi_val_free(box->size);
	free(box);
	return NULL;
}

/* Construct an isl_fixed_box with the given offset and size.
 */
static __isl_give isl_fixed_box *isl_fixed_box_alloc(
	__isl_take isl_multi_aff *offset, __isl_take isl_multi_val *size)
{
	isl_ctx *ctx;
	isl_fixed_box *box;

	if (!offset || !size)
		goto error;
	ctx = isl_multi_aff_get_ctx(offset);
	box = isl_alloc_type(ctx, struct isl_fixed_box);
	if (!box)
		goto error;
	box->offset = offset;
	box->size = size;

	return box;
error:
	isl_multi_aff_free(offset);
	isl_multi_val_free(size);
	return NULL;
}

/* Construct an initial isl_fixed_box with zero offsets
 * in the given space and zero corresponding sizes.
 */
static __isl_give isl_fixed_box *isl_fixed_box_init(
	__isl_take isl_space *space)
{
	isl_multi_aff *offset;
	isl_multi_val *size;

	offset = isl_multi_aff_zero(isl_space_copy(space));
	size = isl_multi_val_zero(isl_space_range(space));
	return isl_fixed_box_alloc(offset, size);
}

/* Return a copy of "box".
 */
__isl_give isl_fixed_box *isl_fixed_box_copy(__isl_keep isl_fixed_box *box)
{
	isl_multi_aff *offset;
	isl_multi_val *size;

	offset = isl_fixed_box_get_offset(box);
	size = isl_fixed_box_get_size(box);
	return isl_fixed_box_alloc(offset, size);
}

/* Replace the offset and size in direction "pos" by "offset" and "size"
 * (without checking whether "box" is a valid box).
 */
static __isl_give isl_fixed_box *isl_fixed_box_set_extent(
	__isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset,
	__isl_keep isl_val *size)
{
	if (!box)
		return NULL;
	box->offset = isl_multi_aff_set_aff(box->offset, pos,
							isl_aff_copy(offset));
	box->size = isl_multi_val_set_val(box->size, pos, isl_val_copy(size));
	if (!box->offset || !box->size)
		return isl_fixed_box_free(box);
	return box;
}

/* Replace the offset and size in direction "pos" by "offset" and "size",
 * if "box" is a valid box.
 */
static __isl_give isl_fixed_box *isl_fixed_box_set_valid_extent(
	__isl_take isl_fixed_box *box, int pos, __isl_keep isl_aff *offset,
	__isl_keep isl_val *size)
{
	isl_bool valid;

	valid = isl_fixed_box_is_valid(box);
	if (valid < 0 || !valid)
		return box;
	return isl_fixed_box_set_extent(box, pos, offset, size);
}

/* Replace "box" by an invalid box, by setting all offsets to NaN
 * (and all sizes to infinity).
 */
static __isl_give isl_fixed_box *isl_fixed_box_invalidate(
	__isl_take isl_fixed_box *box)
{
	int i, n;
	isl_space *space;
	isl_val *infty;
	isl_aff *nan;

	if (!box)
		return NULL;
	n = isl_multi_val_dim(box->size, isl_dim_set);

	infty = isl_val_infty(isl_fixed_box_get_ctx(box));
	space = isl_space_domain(isl_fixed_box_get_space(box));
	nan = isl_aff_nan_on_domain(isl_local_space_from_space(space));
	for (i = 0; i < n; ++i)
		box = isl_fixed_box_set_extent(box, i, nan, infty);
	isl_aff_free(nan);
	isl_val_free(infty);

	if (!box->offset || !box->size)
		return isl_fixed_box_free(box);
	return box;
}

/* Return the isl_ctx to which "box" belongs.
 */
isl_ctx *isl_fixed_box_get_ctx(__isl_keep isl_fixed_box *box)
{
	if (!box)
		return NULL;
	return isl_multi_aff_get_ctx(box->offset);
}

/* Return the space in which "box" lives.
 */
__isl_give isl_space *isl_fixed_box_get_space(__isl_keep isl_fixed_box *box)
{
	if (!box)
		return NULL;
	return isl_multi_aff_get_space(box->offset);
}

/* Does "box" contain valid information?
 */
isl_bool isl_fixed_box_is_valid(__isl_keep isl_fixed_box *box)
{
	if (!box)
		return isl_bool_error;
	return isl_bool_not(isl_multi_aff_involves_nan(box->offset));
}

/* Return the offsets of the box "box".
 */
__isl_give isl_multi_aff *isl_fixed_box_get_offset(
	__isl_keep isl_fixed_box *box)
{
	if (!box)
		return NULL;
	return isl_multi_aff_copy(box->offset);
}

/* Return the sizes of the box "box".
 */
__isl_give isl_multi_val *isl_fixed_box_get_size(__isl_keep isl_fixed_box *box)
{
	if (!box)
		return NULL;
	return isl_multi_val_copy(box->size);
}

/* Data used in set_dim_extent and compute_size_in_direction.
 *
 * "bset" is a wrapped copy of the basic map that has the selected
 * output dimension as range.
 * "pos" is the position of the variable representing the output dimension,
 * i.e., the variable for which the size should be computed.  This variable
 * is also the last variable in "bset".
 * "size" is the best size found so far
 * (infinity if no offset was found so far).
 * "offset" is the offset corresponding to the best size
 * (NULL if no offset was found so far).
 */
struct isl_size_info {
	isl_basic_set *bset;
	int pos;
	isl_val *size;
	isl_aff *offset;
};

/* Is "c" a suitable bound on dimension "pos" for use as a lower bound
 * of a fixed-size range.
 * In particular, it needs to be a lower bound on "pos".
 * In order for the final offset not to be too complicated,
 * the constraint itself should also not involve any integer divisions.
 */
static isl_bool is_suitable_bound(__isl_keep isl_constraint *c, unsigned pos)
{
	unsigned n_div;
	isl_bool is_bound, any_divs;

	is_bound = isl_constraint_is_lower_bound(c, isl_dim_set, pos);
	if (is_bound < 0 || !is_bound)
		return is_bound;

	n_div = isl_constraint_dim(c, isl_dim_div);
	any_divs = isl_constraint_involves_dims(c, isl_dim_div, 0, n_div);
	return isl_bool_not(any_divs);
}

/* Given a constraint from the basic set describing the bounds on
 * an array index, check if it is a lower bound, say m i >= b(x), and,
 * if so, check whether the expression "i - ceil(b(x)/m) + 1" has a constant
 * upper bound.  If so, and if this bound is smaller than any bound
 * derived from earlier constraints, set the size to this bound on
 * the expression and the lower bound to ceil(b(x)/m).
 */
static isl_stat compute_size_in_direction(__isl_take isl_constraint *c,
	void *user)
{
	struct isl_size_info *info = user;
	isl_val *v;
	isl_aff *aff;
	isl_aff *lb;
	isl_bool is_bound, better;

	is_bound = is_suitable_bound(c, info->pos);
	if (is_bound < 0 || !is_bound) {
		isl_constraint_free(c);
		return is_bound < 0 ? isl_stat_error : isl_stat_ok;
	}

	aff = isl_constraint_get_bound(c, isl_dim_set, info->pos);
	aff = isl_aff_ceil(aff);

	lb = isl_aff_copy(aff);

	aff = isl_aff_neg(aff);
	aff = isl_aff_add_coefficient_si(aff, isl_dim_in, info->pos, 1);

	v = isl_basic_set_max_val(info->bset, aff);
	isl_aff_free(aff);

	v = isl_val_add_ui(v, 1);
	better = isl_val_lt(v, info->size);
	if (better >= 0 && better) {
		isl_val_free(info->size);
		info->size = isl_val_copy(v);
		lb = isl_aff_domain_factor_domain(lb);
		isl_aff_free(info->offset);
		info->offset = isl_aff_copy(lb);
	}
	isl_val_free(v);
	isl_aff_free(lb);

	isl_constraint_free(c);

	return better < 0 ? isl_stat_error : isl_stat_ok;
}

/* Look for a fixed-size range of values for the output dimension "pos"
 * of "map", by looking for a lower-bound expression in the parameters
 * and input dimensions such that the range of the output dimension
 * is a constant shifted by this expression.
 *
 * In particular, look through the explicit lower bounds on the output dimension
 * for candidate expressions and pick the one that results in the smallest size.
 * Initialize the size with infinity and if no better size is found
 * then invalidate the box.  Otherwise, set the offset and size
 * in the given direction by those that correspond to the smallest size.
 */
static __isl_give isl_fixed_box *set_dim_extent(__isl_take isl_fixed_box *box,
	__isl_keep isl_map *map, int pos)
{
	struct isl_size_info info;
	isl_bool valid;
	isl_ctx *ctx;

	if (!box || !map)
		return isl_fixed_box_free(box);

	ctx = isl_map_get_ctx(map);
	map = isl_map_copy(map);
	map = isl_map_project_onto(map, isl_dim_out, pos, 1);
	map = isl_map_compute_divs(map);
	info.size = isl_val_infty(ctx);
	info.offset = NULL;
	info.pos = isl_map_dim(map, isl_dim_in);
	info.bset = isl_basic_map_wrap(isl_map_simple_hull(map));
	if (isl_basic_set_foreach_constraint(info.bset,
					&compute_size_in_direction, &info) < 0)
		box = isl_fixed_box_free(box);
	valid = isl_val_is_int(info.size);
	if (valid < 0)
		box = isl_fixed_box_free(box);
	else if (valid)
		box = isl_fixed_box_set_valid_extent(box, pos,
						     info.offset, info.size);
	else
		box = isl_fixed_box_invalidate(box);
	isl_val_free(info.size);
	isl_aff_free(info.offset);
	isl_basic_set_free(info.bset);

	return box;
}

/* Try and construct a fixed-size rectangular box with an offset
 * in terms of the domain of "map" that contains the range of "map".
 * If no such box can be constructed, then return an invalidated box,
 * i.e., one where isl_fixed_box_is_valid returns false.
 *
 * Iterate over the dimensions in the range
 * setting the corresponding offset and extent.
 */
__isl_give isl_fixed_box *isl_map_get_range_simple_fixed_box_hull(
	__isl_keep isl_map *map)
{
	int i, n;
	isl_space *space;
	isl_fixed_box *box;

	n = isl_map_dim(map, isl_dim_out);
	space = isl_map_get_space(map);
	box = isl_fixed_box_init(space);

	map = isl_map_detect_equalities(isl_map_copy(map));
	for (i = 0; i < n; ++i) {
		isl_bool valid;

		box = set_dim_extent(box, map, i);
		valid = isl_fixed_box_is_valid(box);
		if (valid < 0 || !valid)
			break;
	}
	isl_map_free(map);

	return box;
}