1	/*
2	* Copyright 2012-2014 Ecole Normale Superieure
3	* Copyright 2014 INRIA Rocquencourt
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	* and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10	* B.P. 105 - 78153 Le Chesnay, France
11	*/
12
13	#include <isl/id.h>
14	#include <isl/space.h>
15	#include <isl/constraint.h>
16	#include <isl/ilp.h>
17	#include <isl/val.h>
18	#include <isl_ast_build_expr.h>
19	#include <isl_ast_private.h>
20	#include <isl_ast_build_private.h>
21	#include <isl_sort.h>
22
23	/* Compute the "opposite" of the (numerator of the) argument of a div
24	* with denominator "d".
25	*
26	* In particular, compute
27	*
28	* -aff + (d - 1)
29	*/
30	static __isl_give isl_aff *oppose_div_arg(__isl_take isl_aff *aff,
31	__isl_take isl_val *d)
32	{
33	aff = isl_aff_neg(aff);
34	aff = isl_aff_add_constant_val(aff, v: d);
35	aff = isl_aff_add_constant_si(aff, v: -1);
36
37	return aff;
38	}
39
40	/* Internal data structure used inside isl_ast_expr_add_term.
41	* The domain of "build" is used to simplify the expressions.
42	* "build" needs to be set by the caller of isl_ast_expr_add_term.
43	* "ls" is the domain local space of the affine expression
44	* of which a term is being added.
45	* "cst" is the constant term of the expression in which the added term
46	* appears. It may be modified by isl_ast_expr_add_term.
47	*
48	* "v" is the coefficient of the term that is being constructed and
49	* is set internally by isl_ast_expr_add_term.
50	*/
51	struct isl_ast_add_term_data {
52	isl_ast_build *build;
53	isl_local_space *ls;
54	isl_val *cst;
55	isl_val *v;
56	};
57
58	/* Given the numerator "aff" of the argument of an integer division
59	* with denominator "d", check if it can be made non-negative over
60	* data->build->domain by stealing part of the constant term of
61	* the expression in which the integer division appears.
62	*
63	* In particular, the outer expression is of the form
64	*
65	* v * floor(aff/d) + cst
66	*
67	* We already know that "aff" itself may attain negative values.
68	* Here we check if aff + d*floor(cst/v) is non-negative, such
69	* that we could rewrite the expression to
70	*
71	* v * floor((aff + d*floor(cst/v))/d) + cst - v*floor(cst/v)
72	*
73	* Note that aff + d*floor(cst/v) can only possibly be non-negative
74	* if data->cst and data->v have the same sign.
75	* Similarly, if floor(cst/v) is zero, then there is no point in
76	* checking again.
77	*/
78	static isl_bool is_non_neg_after_stealing(__isl_keep isl_aff *aff,
79	__isl_keep isl_val *d, struct isl_ast_add_term_data *data)
80	{
81	isl_aff *shifted;
82	isl_val *shift;
83	isl_bool is_zero;
84	isl_bool non_neg;
85
86	if (isl_val_sgn(v: data->cst) != isl_val_sgn(v: data->v))
87	return isl_bool_false;
88
89	shift = isl_val_div(v1: isl_val_copy(v: data->cst), v2: isl_val_copy(v: data->v));
90	shift = isl_val_floor(v: shift);
91	is_zero = isl_val_is_zero(v: shift);
92	if (is_zero < 0 || is_zero) {
93	isl_val_free(v: shift);
94	return isl_bool_not(b: is_zero);
95	}
96	shift = isl_val_mul(v1: shift, v2: isl_val_copy(v: d));
97	shifted = isl_aff_copy(aff);
98	shifted = isl_aff_add_constant_val(aff: shifted, v: shift);
99	non_neg = isl_ast_build_aff_is_nonneg(build: data->build, aff: shifted);
100	isl_aff_free(aff: shifted);
101
102	return non_neg;
103	}
104
105	/* Given the numerator "aff" of the argument of an integer division
106	* with denominator "d", steal part of the constant term of
107	* the expression in which the integer division appears to make it
108	* non-negative over data->build->domain.
109	*
110	* In particular, the outer expression is of the form
111	*
112	* v * floor(aff/d) + cst
113	*
114	* We know that "aff" itself may attain negative values,
115	* but that aff + d*floor(cst/v) is non-negative.
116	* Find the minimal positive value that we need to add to "aff"
117	* to make it positive and adjust data->cst accordingly.
118	* That is, compute the minimal value "m" of "aff" over
119	* data->build->domain and take
120	*
121	* s = ceil(-m/d)
122	*
123	* such that
124	*
125	* aff + d * s >= 0
126	*
127	* and rewrite the expression to
128	*
129	* v * floor((aff + s*d)/d) + (cst - v*s)
130	*/
131	static __isl_give isl_aff *steal_from_cst(__isl_take isl_aff *aff,
132	__isl_keep isl_val *d, struct isl_ast_add_term_data *data)
133	{
134	isl_set *domain;
135	isl_val *shift, *t;
136
137	domain = isl_ast_build_get_domain(build: data->build);
138	shift = isl_set_min_val(set: domain, obj: aff);
139	isl_set_free(set: domain);
140
141	shift = isl_val_neg(v: shift);
142	shift = isl_val_div(v1: shift, v2: isl_val_copy(v: d));
143	shift = isl_val_ceil(v: shift);
144
145	t = isl_val_copy(v: shift);
146	t = isl_val_mul(v1: t, v2: isl_val_copy(v: data->v));
147	data->cst = isl_val_sub(v1: data->cst, v2: t);
148
149	shift = isl_val_mul(v1: shift, v2: isl_val_copy(v: d));
150	return isl_aff_add_constant_val(aff, v: shift);
151	}
152
153	/* Construct an expression representing the binary operation "type"
154	* (some division or modulo) applied to the expressions
155	* constructed from "aff" and "v".
156	*/
157	static __isl_give isl_ast_expr *div_mod(enum isl_ast_expr_op_type type,
158	__isl_take isl_aff *aff, __isl_take isl_val *v,
159	__isl_keep isl_ast_build *build)
160	{
161	isl_ast_expr *expr1, *expr2;
162
163	expr1 = isl_ast_expr_from_aff(aff, build);
164	expr2 = isl_ast_expr_from_val(v);
165	return isl_ast_expr_alloc_binary(type, expr1, expr2);
166	}
167
168	/* Create an isl_ast_expr evaluating the div at position "pos" in data->ls.
169	* The result is simplified in terms of data->build->domain.
170	* This function may change (the sign of) data->v.
171	*
172	* data->ls is known to be non-NULL.
173	*
174	* Let the div be of the form floor(e/d).
175	* If the ast_build_prefer_pdiv option is set then we check if "e"
176	* is non-negative, so that we can generate
177	*
178	* (pdiv_q, expr(e), expr(d))
179	*
180	* instead of
181	*
182	* (fdiv_q, expr(e), expr(d))
183	*
184	* If the ast_build_prefer_pdiv option is set and
185	* if "e" is not non-negative, then we check if "-e + d - 1" is non-negative.
186	* If so, we can rewrite
187	*
188	* floor(e/d) = -ceil(-e/d) = -floor((-e + d - 1)/d)
189	*
190	* and still use pdiv_q, while changing the sign of data->v.
191	*
192	* Otherwise, we check if
193	*
194	* e + d*floor(cst/v)
195	*
196	* is non-negative and if so, replace floor(e/d) by
197	*
198	* floor((e + s*d)/d) - s
199	*
200	* with s the minimal shift that makes the argument non-negative.
201	*/
202	static __isl_give isl_ast_expr *var_div(struct isl_ast_add_term_data *data,
203	int pos)
204	{
205	isl_ctx *ctx = isl_local_space_get_ctx(ls: data->ls);
206	isl_aff *aff;
207	isl_val *d;
208	enum isl_ast_expr_op_type type;
209
210	aff = isl_local_space_get_div(ls: data->ls, pos);
211	d = isl_aff_get_denominator_val(aff);
212	aff = isl_aff_scale_val(aff, v: isl_val_copy(v: d));
213
214	type = isl_ast_expr_op_fdiv_q;
215	if (isl_options_get_ast_build_prefer_pdiv(ctx)) {
216	isl_bool non_neg;
217	non_neg = isl_ast_build_aff_is_nonneg(build: data->build, aff);
218	if (non_neg >= 0 && !non_neg) {
219	isl_aff *opp = oppose_div_arg(aff: isl_aff_copy(aff),
220	d: isl_val_copy(v: d));
221	non_neg = isl_ast_build_aff_is_nonneg(build: data->build, aff: opp);
222	if (non_neg >= 0 && non_neg) {
223	data->v = isl_val_neg(v: data->v);
224	isl_aff_free(aff);
225	aff = opp;
226	} else
227	isl_aff_free(aff: opp);
228	}
229	if (non_neg >= 0 && !non_neg) {
230	non_neg = is_non_neg_after_stealing(aff, d, data);
231	if (non_neg >= 0 && non_neg)
232	aff = steal_from_cst(aff, d, data);
233	}
234	if (non_neg < 0)
235	aff = isl_aff_free(aff);
236	else if (non_neg)
237	type = isl_ast_expr_op_pdiv_q;
238	}
239
240	return div_mod(type, aff, v: d, build: data->build);
241	}
242
243	/* Create an isl_ast_expr evaluating the specified dimension of data->ls.
244	* The result is simplified in terms of data->build->domain.
245	* This function may change (the sign of) data->v.
246	*
247	* The isl_ast_expr is constructed based on the type of the dimension.
248	* - divs are constructed by var_div
249	* - set variables are constructed from the iterator isl_ids in data->build
250	* - parameters are constructed from the isl_ids in data->ls
251	*/
252	static __isl_give isl_ast_expr *var(struct isl_ast_add_term_data *data,
253	enum isl_dim_type type, int pos)
254	{
255	isl_ctx *ctx = isl_local_space_get_ctx(ls: data->ls);
256	isl_id *id;
257
258	if (type == isl_dim_div)
259	return var_div(data, pos);
260
261	if (type == isl_dim_set) {
262	id = isl_ast_build_get_iterator_id(build: data->build, pos);
263	return isl_ast_expr_from_id(id);
264	}
265
266	if (!isl_local_space_has_dim_id(ls: data->ls, type, pos))
267	isl_die(ctx, isl_error_internal, "unnamed dimension",
268	return NULL);
269	id = isl_local_space_get_dim_id(ls: data->ls, type, pos);
270	return isl_ast_expr_from_id(id);
271	}
272
273	/* Does "expr" represent the zero integer?
274	*/
275	static isl_bool ast_expr_is_zero(__isl_keep isl_ast_expr *expr)
276	{
277	if (!expr)
278	return isl_bool_error;
279	if (expr->type != isl_ast_expr_int)
280	return isl_bool_false;
281	return isl_val_is_zero(v: expr->u.v);
282	}
283
284	/* Create an expression representing the sum of "expr1" and "expr2",
285	* provided neither of the two expressions is identically zero.
286	*/
287	static __isl_give isl_ast_expr *ast_expr_add(__isl_take isl_ast_expr *expr1,
288	__isl_take isl_ast_expr *expr2)
289	{
290	if (!expr1 || !expr2)
291	goto error;
292
293	if (ast_expr_is_zero(expr: expr1)) {
294	isl_ast_expr_free(expr: expr1);
295	return expr2;
296	}
297
298	if (ast_expr_is_zero(expr: expr2)) {
299	isl_ast_expr_free(expr: expr2);
300	return expr1;
301	}
302
303	return isl_ast_expr_add(expr1, expr2);
304	error:
305	isl_ast_expr_free(expr: expr1);
306	isl_ast_expr_free(expr: expr2);
307	return NULL;
308	}
309
310	/* Subtract expr2 from expr1.
311	*
312	* If expr2 is zero, we simply return expr1.
313	* If expr1 is zero, we return
314	*
315	* (isl_ast_expr_op_minus, expr2)
316	*
317	* Otherwise, we return
318	*
319	* (isl_ast_expr_op_sub, expr1, expr2)
320	*/
321	static __isl_give isl_ast_expr *ast_expr_sub(__isl_take isl_ast_expr *expr1,
322	__isl_take isl_ast_expr *expr2)
323	{
324	if (!expr1 || !expr2)
325	goto error;
326
327	if (ast_expr_is_zero(expr: expr2)) {
328	isl_ast_expr_free(expr: expr2);
329	return expr1;
330	}
331
332	if (ast_expr_is_zero(expr: expr1)) {
333	isl_ast_expr_free(expr: expr1);
334	return isl_ast_expr_neg(expr: expr2);
335	}
336
337	return isl_ast_expr_sub(expr1, expr2);
338	error:
339	isl_ast_expr_free(expr: expr1);
340	isl_ast_expr_free(expr: expr2);
341	return NULL;
342	}
343
344	/* Return an isl_ast_expr that represents
345	*
346	* v * (aff mod d)
347	*
348	* v is assumed to be non-negative.
349	* The result is simplified in terms of build->domain.
350	*/
351	static __isl_give isl_ast_expr *isl_ast_expr_mod(__isl_keep isl_val *v,
352	__isl_keep isl_aff *aff, __isl_keep isl_val *d,
353	__isl_keep isl_ast_build *build)
354	{
355	isl_ast_expr *expr;
356	isl_ast_expr *c;
357
358	if (!aff)
359	return NULL;
360
361	expr = div_mod(type: isl_ast_expr_op_pdiv_r,
362	aff: isl_aff_copy(aff), v: isl_val_copy(v: d), build);
363
364	if (!isl_val_is_one(v)) {
365	c = isl_ast_expr_from_val(v: isl_val_copy(v));
366	expr = isl_ast_expr_mul(expr1: c, expr2: expr);
367	}
368
369	return expr;
370	}
371
372	/* Create an isl_ast_expr that scales "expr" by "v".
373	*
374	* If v is 1, we simply return expr.
375	* If v is -1, we return
376	*
377	* (isl_ast_expr_op_minus, expr)
378	*
379	* Otherwise, we return
380	*
381	* (isl_ast_expr_op_mul, expr(v), expr)
382	*/
383	static __isl_give isl_ast_expr *scale(__isl_take isl_ast_expr *expr,
384	__isl_take isl_val *v)
385	{
386	isl_ast_expr *c;
387
388	if (!expr || !v)
389	goto error;
390	if (isl_val_is_one(v)) {
391	isl_val_free(v);
392	return expr;
393	}
394
395	if (isl_val_is_negone(v)) {
396	isl_val_free(v);
397	expr = isl_ast_expr_neg(expr);
398	} else {
399	c = isl_ast_expr_from_val(v);
400	expr = isl_ast_expr_mul(expr1: c, expr2: expr);
401	}
402
403	return expr;
404	error:
405	isl_val_free(v);
406	isl_ast_expr_free(expr);
407	return NULL;
408	}
409
410	/* Add an expression for "*v" times the specified dimension of data->ls
411	* to expr.
412	* If the dimension is an integer division, then this function
413	* may modify data->cst in order to make the numerator non-negative.
414	* The result is simplified in terms of data->build->domain.
415	*
416	* Let e be the expression for the specified dimension,
417	* multiplied by the absolute value of "*v".
418	* If "*v" is negative, we create
419	*
420	* (isl_ast_expr_op_sub, expr, e)
421	*
422	* except when expr is trivially zero, in which case we create
423	*
424	* (isl_ast_expr_op_minus, e)
425	*
426	* instead.
427	*
428	* If "*v" is positive, we simply create
429	*
430	* (isl_ast_expr_op_add, expr, e)
431	*
432	*/
433	static __isl_give isl_ast_expr *isl_ast_expr_add_term(
434	__isl_take isl_ast_expr *expr, enum isl_dim_type type, int pos,
435	__isl_take isl_val *v, struct isl_ast_add_term_data *data)
436	{
437	isl_ast_expr *term;
438
439	if (!expr)
440	return NULL;
441
442	data->v = v;
443	term = var(data, type, pos);
444	v = data->v;
445
446	if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
447	v = isl_val_neg(v);
448	term = scale(expr: term, v);
449	return ast_expr_sub(expr1: expr, expr2: term);
450	} else {
451	term = scale(expr: term, v);
452	return ast_expr_add(expr1: expr, expr2: term);
453	}
454	}
455
456	/* Add an expression for "v" to expr.
457	*/
458	static __isl_give isl_ast_expr *isl_ast_expr_add_int(
459	__isl_take isl_ast_expr *expr, __isl_take isl_val *v)
460	{
461	isl_ast_expr *expr_int;
462
463	if (!expr || !v)
464	goto error;
465
466	if (isl_val_is_zero(v)) {
467	isl_val_free(v);
468	return expr;
469	}
470
471	if (isl_val_is_neg(v) && !ast_expr_is_zero(expr)) {
472	v = isl_val_neg(v);
473	expr_int = isl_ast_expr_from_val(v);
474	return ast_expr_sub(expr1: expr, expr2: expr_int);
475	} else {
476	expr_int = isl_ast_expr_from_val(v);
477	return ast_expr_add(expr1: expr, expr2: expr_int);
478	}
479	error:
480	isl_ast_expr_free(expr);
481	isl_val_free(v);
482	return NULL;
483	}
484
485	/* Internal data structure used inside extract_modulos.
486	*
487	* If any modulo expressions are detected in "aff", then the
488	* expression is removed from "aff" and added to either "pos" or "neg"
489	* depending on the sign of the coefficient of the modulo expression
490	* inside "aff".
491	*
492	* "add" is an expression that needs to be added to "aff" at the end of
493	* the computation. It is NULL as long as no modulos have been extracted.
494	*
495	* "i" is the position in "aff" of the div under investigation
496	* "v" is the coefficient in "aff" of the div
497	* "div" is the argument of the div, with the denominator removed
498	* "d" is the original denominator of the argument of the div
499	*
500	* "nonneg" is an affine expression that is non-negative over "build"
501	* and that can be used to extract a modulo expression from "div".
502	* In particular, if "sign" is 1, then the coefficients of "nonneg"
503	* are equal to those of "div" modulo "d". If "sign" is -1, then
504	* the coefficients of "nonneg" are opposite to those of "div" modulo "d".
505	* If "sign" is 0, then no such affine expression has been found (yet).
506	*/
507	struct isl_extract_mod_data {
508	isl_ast_build *build;
509	isl_aff *aff;
510
511	isl_ast_expr *pos;
512	isl_ast_expr *neg;
513
514	isl_aff *add;
515
516	int i;
517	isl_val *v;
518	isl_val *d;
519	isl_aff *div;
520
521	isl_aff *nonneg;
522	int sign;
523	};
524
525	/* Does
526	*
527	* arg mod data->d
528	*
529	* represent (a special case of) a test for some linear expression
530	* being even?
531	*
532	* In particular, is it of the form
533	*
534	* (lin - 1) mod 2
535	*
536	* ?
537	*/
538	static isl_bool is_even_test(struct isl_extract_mod_data *data,
539	__isl_keep isl_aff *arg)
540	{
541	isl_bool res;
542	isl_val *cst;
543
544	res = isl_val_eq_si(v: data->d, i: 2);
545	if (res < 0 || !res)
546	return res;
547
548	cst = isl_aff_get_constant_val(aff: arg);
549	res = isl_val_eq_si(v: cst, i: -1);
550	isl_val_free(v: cst);
551
552	return res;
553	}
554
555	/* Given that data->v * div_i in data->aff is equal to
556	*
557	* f * (term - (arg mod d))
558	*
559	* with data->d * f = data->v and "arg" non-negative on data->build, add
560	*
561	* f * term
562	*
563	* to data->add and
564	*
565	* abs(f) * (arg mod d)
566	*
567	* to data->neg or data->pos depending on the sign of -f.
568	*
569	* In the special case that "arg mod d" is of the form "(lin - 1) mod 2",
570	* with "lin" some linear expression, first replace
571	*
572	* f * (term - ((lin - 1) mod 2))
573	*
574	* by
575	*
576	* -f * (1 - term - (lin mod 2))
577	*
578	* These two are equal because
579	*
580	* ((lin - 1) mod 2) + (lin mod 2) = 1
581	*
582	* Also, if "lin - 1" is non-negative, then "lin" is non-negative too.
583	*/
584	static isl_stat extract_term_and_mod(struct isl_extract_mod_data *data,
585	__isl_take isl_aff *term, __isl_take isl_aff *arg)
586	{
587	isl_bool even;
588	isl_ast_expr *expr;
589	int s;
590
591	even = is_even_test(data, arg);
592	if (even < 0) {
593	arg = isl_aff_free(aff: arg);
594	} else if (even) {
595	term = oppose_div_arg(aff: term, d: isl_val_copy(v: data->d));
596	data->v = isl_val_neg(v: data->v);
597	arg = isl_aff_set_constant_si(aff: arg, v: 0);
598	}
599
600	data->v = isl_val_div(v1: data->v, v2: isl_val_copy(v: data->d));
601	s = isl_val_sgn(v: data->v);
602	data->v = isl_val_abs(v: data->v);
603	expr = isl_ast_expr_mod(v: data->v, aff: arg, d: data->d, build: data->build);
604	isl_aff_free(aff: arg);
605	if (s > 0)
606	data->neg = ast_expr_add(expr1: data->neg, expr2: expr);
607	else
608	data->pos = ast_expr_add(expr1: data->pos, expr2: expr);
609	data->aff = isl_aff_set_coefficient_si(aff: data->aff,
610	type: isl_dim_div, pos: data->i, v: 0);
611	if (s < 0)
612	data->v = isl_val_neg(v: data->v);
613	term = isl_aff_scale_val(aff: term, v: isl_val_copy(v: data->v));
614
615	if (!data->add)
616	data->add = term;
617	else
618	data->add = isl_aff_add(aff1: data->add, aff2: term);
619	if (!data->add)
620	return isl_stat_error;
621
622	return isl_stat_ok;
623	}
624
625	/* Given that data->v * div_i in data->aff is of the form
626	*
627	* f * d * floor(div/d)
628	*
629	* with div nonnegative on data->build, rewrite it as
630	*
631	* f * (div - (div mod d)) = f * div - f * (div mod d)
632	*
633	* and add
634	*
635	* f * div
636	*
637	* to data->add and
638	*
639	* abs(f) * (div mod d)
640	*
641	* to data->neg or data->pos depending on the sign of -f.
642	*/
643	static isl_stat extract_mod(struct isl_extract_mod_data *data)
644	{
645	return extract_term_and_mod(data, term: isl_aff_copy(aff: data->div),
646	arg: isl_aff_copy(aff: data->div));
647	}
648
649	/* Given that data->v * div_i in data->aff is of the form
650	*
651	* f * d * floor(div/d) (1)
652	*
653	* check if div is non-negative on data->build and, if so,
654	* extract the corresponding modulo from data->aff.
655	* If not, then check if
656	*
657	* -div + d - 1
658	*
659	* is non-negative on data->build. If so, replace (1) by
660	*
661	* -f * d * floor((-div + d - 1)/d)
662	*
663	* and extract the corresponding modulo from data->aff.
664	*
665	* This function may modify data->div.
666	*/
667	static isl_stat extract_nonneg_mod(struct isl_extract_mod_data *data)
668	{
669	isl_bool mod;
670
671	mod = isl_ast_build_aff_is_nonneg(build: data->build, aff: data->div);
672	if (mod < 0)
673	goto error;
674	if (mod)
675	return extract_mod(data);
676
677	data->div = oppose_div_arg(aff: data->div, d: isl_val_copy(v: data->d));
678	mod = isl_ast_build_aff_is_nonneg(build: data->build, aff: data->div);
679	if (mod < 0)
680	goto error;
681	if (mod) {
682	data->v = isl_val_neg(v: data->v);
683	return extract_mod(data);
684	}
685
686	return isl_stat_ok;
687	error:
688	data->aff = isl_aff_free(aff: data->aff);
689	return isl_stat_error;
690	}
691
692	/* Is the affine expression of constraint "c" "simpler" than data->nonneg
693	* for use in extracting a modulo expression?
694	*
695	* We currently only consider the constant term of the affine expression.
696	* In particular, we prefer the affine expression with the smallest constant
697	* term.
698	* This means that if there are two constraints, say x >= 0 and -x + 10 >= 0,
699	* then we would pick x >= 0
700	*
701	* More detailed heuristics could be used if it turns out that there is a need.
702	*/
703	static int mod_constraint_is_simpler(struct isl_extract_mod_data *data,
704	__isl_keep isl_constraint *c)
705	{
706	isl_val *v1, *v2;
707	int simpler;
708
709	if (!data->nonneg)
710	return 1;
711
712	v1 = isl_val_abs(v: isl_constraint_get_constant_val(constraint: c));
713	v2 = isl_val_abs(v: isl_aff_get_constant_val(aff: data->nonneg));
714	simpler = isl_val_lt(v1, v2);
715	isl_val_free(v: v1);
716	isl_val_free(v: v2);
717
718	return simpler;
719	}
720
721	/* Check if the coefficients of "c" are either equal or opposite to those
722	* of data->div modulo data->d. If so, and if "c" is "simpler" than
723	* data->nonneg, then replace data->nonneg by the affine expression of "c"
724	* and set data->sign accordingly.
725	*
726	* Both "c" and data->div are assumed not to involve any integer divisions.
727	*
728	* Before we start the actual comparison, we first quickly check if
729	* "c" and data->div have the same non-zero coefficients.
730	* If not, then we assume that "c" is not of the desired form.
731	* Note that while the coefficients of data->div can be reasonably expected
732	* not to involve any coefficients that are multiples of d, "c" may
733	* very well involve such coefficients. This means that we may actually
734	* miss some cases.
735	*
736	* If the constant term is "too large", then the constraint is rejected,
737	* where "too large" is fairly arbitrarily set to 1 << 15.
738	* We do this to avoid picking up constraints that bound a variable
739	* by a very large number, say the largest or smallest possible
740	* variable in the representation of some integer type.
741	*/
742	static isl_stat check_parallel_or_opposite(__isl_take isl_constraint *c,
743	void *user)
744	{
745	struct isl_extract_mod_data *data = user;
746	enum isl_dim_type c_type[2] = { isl_dim_param, isl_dim_set };
747	enum isl_dim_type a_type[2] = { isl_dim_param, isl_dim_in };
748	int i, t;
749	isl_size n[2];
750	isl_bool parallel = isl_bool_true, opposite = isl_bool_true;
751
752	for (t = 0; t < 2; ++t) {
753	n[t] = isl_constraint_dim(constraint: c, type: c_type[t]);
754	if (n[t] < 0)
755	goto error;
756	for (i = 0; i < n[t]; ++i) {
757	isl_bool a, b;
758
759	a = isl_constraint_involves_dims(constraint: c, type: c_type[t], first: i, n: 1);
760	b = isl_aff_involves_dims(aff: data->div, type: a_type[t], first: i, n: 1);
761	if (a < 0 || b < 0)
762	goto error;
763	if (a != b)
764	parallel = opposite = isl_bool_false;
765	}
766	}
767
768	if (parallel || opposite) {
769	isl_val *v;
770
771	v = isl_val_abs(v: isl_constraint_get_constant_val(constraint: c));
772	if (isl_val_cmp_si(v, i: 1 << 15) > 0)
773	parallel = opposite = isl_bool_false;
774	isl_val_free(v);
775	}
776
777	for (t = 0; t < 2; ++t) {
778	for (i = 0; i < n[t]; ++i) {
779	isl_val *v1, *v2;
780
781	if (!parallel && !opposite)
782	break;
783	v1 = isl_constraint_get_coefficient_val(constraint: c,
784	type: c_type[t], pos: i);
785	v2 = isl_aff_get_coefficient_val(aff: data->div,
786	type: a_type[t], pos: i);
787	if (parallel) {
788	v1 = isl_val_sub(v1, v2: isl_val_copy(v: v2));
789	parallel = isl_val_is_divisible_by(v1, v2: data->d);
790	v1 = isl_val_add(v1, v2: isl_val_copy(v: v2));
791	}
792	if (opposite) {
793	v1 = isl_val_add(v1, v2: isl_val_copy(v: v2));
794	opposite = isl_val_is_divisible_by(v1, v2: data->d);
795	}
796	isl_val_free(v: v1);
797	isl_val_free(v: v2);
798	if (parallel < 0 || opposite < 0)
799	goto error;
800	}
801	}
802
803	if ((parallel || opposite) && mod_constraint_is_simpler(data, c)) {
804	isl_aff_free(aff: data->nonneg);
805	data->nonneg = isl_constraint_get_aff(constraint: c);
806	data->sign = parallel ? 1 : -1;
807	}
808
809	isl_constraint_free(c);
810
811	if (data->sign != 0 && data->nonneg == NULL)
812	return isl_stat_error;
813
814	return isl_stat_ok;
815	error:
816	isl_constraint_free(c);
817	return isl_stat_error;
818	}
819
820	/* Given that data->v * div_i in data->aff is of the form
821	*
822	* f * d * floor(div/d) (1)
823	*
824	* see if we can find an expression div' that is non-negative over data->build
825	* and that is related to div through
826	*
827	* div' = div + d * e
828	*
829	* or
830	*
831	* div' = -div + d - 1 + d * e
832	*
833	* with e some affine expression.
834	* If so, we write (1) as
835	*
836	* f * div + f * (div' mod d)
837	*
838	* or
839	*
840	* -f * (-div + d - 1) - f * (div' mod d)
841	*
842	* exploiting (in the second case) the fact that
843	*
844	* f * d * floor(div/d) = -f * d * floor((-div + d - 1)/d)
845	*
846	*
847	* We first try to find an appropriate expression for div'
848	* from the constraints of data->build->domain (which is therefore
849	* guaranteed to be non-negative on data->build), where we remove
850	* any integer divisions from the constraints and skip this step
851	* if "div" itself involves any integer divisions.
852	* If we cannot find an appropriate expression this way, then
853	* we pass control to extract_nonneg_mod where check
854	* if div or "-div + d -1" themselves happen to be
855	* non-negative on data->build.
856	*
857	* While looking for an appropriate constraint in data->build->domain,
858	* we ignore the constant term, so after finding such a constraint,
859	* we still need to fix up the constant term.
860	* In particular, if a is the constant term of "div"
861	* (or d - 1 - the constant term of "div" if data->sign < 0)
862	* and b is the constant term of the constraint, then we need to find
863	* a non-negative constant c such that
864	*
865	* b + c \equiv a mod d
866	*
867	* We therefore take
868	*
869	* c = (a - b) mod d
870	*
871	* and add it to b to obtain the constant term of div'.
872	* If this constant term is "too negative", then we add an appropriate
873	* multiple of d to make it positive.
874	*
875	*
876	* Note that the above is only a very simple heuristic for finding an
877	* appropriate expression. We could try a bit harder by also considering
878	* sums of constraints that involve disjoint sets of variables or
879	* we could consider arbitrary linear combinations of constraints,
880	* although that could potentially be much more expensive as it involves
881	* the solution of an LP problem.
882	*
883	* In particular, if v_i is a column vector representing constraint i,
884	* w represents div and e_i is the i-th unit vector, then we are looking
885	* for a solution of the constraints
886	*
887	* \sum_i lambda_i v_i = w + \sum_i alpha_i d e_i
888	*
889	* with \lambda_i >= 0 and alpha_i of unrestricted sign.
890	* If we are not just interested in a non-negative expression, but
891	* also in one with a minimal range, then we don't just want
892	* c = \sum_i lambda_i v_i to be non-negative over the domain,
893	* but also beta - c = \sum_i mu_i v_i, where beta is a scalar
894	* that we want to minimize and we now also have to take into account
895	* the constant terms of the constraints.
896	* Alternatively, we could first compute the dual of the domain
897	* and plug in the constraints on the coefficients.
898	*/
899	static isl_stat try_extract_mod(struct isl_extract_mod_data *data)
900	{
901	isl_basic_set *hull;
902	isl_val *v1, *v2;
903	isl_stat r;
904	isl_size n;
905
906	if (!data->build)
907	goto error;
908
909	n = isl_aff_dim(aff: data->div, type: isl_dim_div);
910	if (n < 0)
911	goto error;
912
913	if (isl_aff_involves_dims(aff: data->div, type: isl_dim_div, first: 0, n))
914	return extract_nonneg_mod(data);
915
916	hull = isl_set_simple_hull(set: isl_set_copy(set: data->build->domain));
917	hull = isl_basic_set_remove_divs(bset: hull);
918	data->sign = 0;
919	data->nonneg = NULL;
920	r = isl_basic_set_foreach_constraint(bset: hull, fn: &check_parallel_or_opposite,
921	user: data);
922	isl_basic_set_free(bset: hull);
923
924	if (!data->sign || r < 0) {
925	isl_aff_free(aff: data->nonneg);
926	if (r < 0)
927	goto error;
928	return extract_nonneg_mod(data);
929	}
930
931	v1 = isl_aff_get_constant_val(aff: data->div);
932	v2 = isl_aff_get_constant_val(aff: data->nonneg);
933	if (data->sign < 0) {
934	v1 = isl_val_neg(v: v1);
935	v1 = isl_val_add(v1, v2: isl_val_copy(v: data->d));
936	v1 = isl_val_sub_ui(v1, v2: 1);
937	}
938	v1 = isl_val_sub(v1, v2: isl_val_copy(v: v2));
939	v1 = isl_val_mod(v1, v2: isl_val_copy(v: data->d));
940	v1 = isl_val_add(v1, v2);
941	v2 = isl_val_div(v1: isl_val_copy(v: v1), v2: isl_val_copy(v: data->d));
942	v2 = isl_val_ceil(v: v2);
943	if (isl_val_is_neg(v: v2)) {
944	v2 = isl_val_mul(v1: v2, v2: isl_val_copy(v: data->d));
945	v1 = isl_val_sub(v1, v2: isl_val_copy(v: v2));
946	}
947	data->nonneg = isl_aff_set_constant_val(aff: data->nonneg, v: v1);
948	isl_val_free(v: v2);
949
950	if (data->sign < 0) {
951	data->div = oppose_div_arg(aff: data->div, d: isl_val_copy(v: data->d));
952	data->v = isl_val_neg(v: data->v);
953	}
954
955	return extract_term_and_mod(data,
956	term: isl_aff_copy(aff: data->div), arg: data->nonneg);
957	error:
958	data->aff = isl_aff_free(aff: data->aff);
959	return isl_stat_error;
960	}
961
962	/* Check if "data->aff" involves any (implicit) modulo computations based
963	* on div "data->i".
964	* If so, remove them from aff and add expressions corresponding
965	* to those modulo computations to data->pos and/or data->neg.
966	*
967	* "aff" is assumed to be an integer affine expression.
968	*
969	* In particular, check if (v * div_j) is of the form
970	*
971	* f * m * floor(a / m)
972	*
973	* and, if so, rewrite it as
974	*
975	* f * (a - (a mod m)) = f * a - f * (a mod m)
976	*
977	* and extract out -f * (a mod m).
978	* In particular, if f > 0, we add (f * (a mod m)) to *neg.
979	* If f < 0, we add ((-f) * (a mod m)) to *pos.
980	*
981	* Note that in order to represent "a mod m" as
982	*
983	* (isl_ast_expr_op_pdiv_r, a, m)
984	*
985	* we need to make sure that a is non-negative.
986	* If not, we check if "-a + m - 1" is non-negative.
987	* If so, we can rewrite
988	*
989	* floor(a/m) = -ceil(-a/m) = -floor((-a + m - 1)/m)
990	*
991	* and still extract a modulo.
992	*/
993	static int extract_modulo(struct isl_extract_mod_data *data)
994	{
995	data->div = isl_aff_get_div(aff: data->aff, pos: data->i);
996	data->d = isl_aff_get_denominator_val(aff: data->div);
997	if (isl_val_is_divisible_by(v1: data->v, v2: data->d)) {
998	data->div = isl_aff_scale_val(aff: data->div, v: isl_val_copy(v: data->d));
999	if (try_extract_mod(data) < 0)
1000	data->aff = isl_aff_free(aff: data->aff);
1001	}
1002	isl_aff_free(aff: data->div);
1003	isl_val_free(v: data->d);
1004	return 0;
1005	}
1006
1007	/* Check if "aff" involves any (implicit) modulo computations.
1008	* If so, remove them from aff and add expressions corresponding
1009	* to those modulo computations to *pos and/or *neg.
1010	* We only do this if the option ast_build_prefer_pdiv is set.
1011	*
1012	* "aff" is assumed to be an integer affine expression.
1013	*
1014	* A modulo expression is of the form
1015	*
1016	* a mod m = a - m * floor(a / m)
1017	*
1018	* To detect them in aff, we look for terms of the form
1019	*
1020	* f * m * floor(a / m)
1021	*
1022	* rewrite them as
1023	*
1024	* f * (a - (a mod m)) = f * a - f * (a mod m)
1025	*
1026	* and extract out -f * (a mod m).
1027	* In particular, if f > 0, we add (f * (a mod m)) to *neg.
1028	* If f < 0, we add ((-f) * (a mod m)) to *pos.
1029	*/
1030	static __isl_give isl_aff *extract_modulos(__isl_take isl_aff *aff,
1031	__isl_keep isl_ast_expr **pos, __isl_keep isl_ast_expr **neg,
1032	__isl_keep isl_ast_build *build)
1033	{
1034	struct isl_extract_mod_data data = { build, aff, *pos, *neg };
1035	isl_ctx *ctx;
1036	isl_size n;
1037
1038	if (!aff)
1039	return NULL;
1040
1041	ctx = isl_aff_get_ctx(aff);
1042	if (!isl_options_get_ast_build_prefer_pdiv(ctx))
1043	return aff;
1044
1045	n = isl_aff_dim(aff: data.aff, type: isl_dim_div);
1046	if (n < 0)
1047	return isl_aff_free(aff);
1048	for (data.i = 0; data.i < n; ++data.i) {
1049	data.v = isl_aff_get_coefficient_val(aff: data.aff,
1050	type: isl_dim_div, pos: data.i);
1051	if (!data.v)
1052	return isl_aff_free(aff);
1053	if (isl_val_is_zero(v: data.v) ||
1054	isl_val_is_one(v: data.v) || isl_val_is_negone(v: data.v)) {
1055	isl_val_free(v: data.v);
1056	continue;
1057	}
1058	if (extract_modulo(data: &data) < 0)
1059	data.aff = isl_aff_free(aff: data.aff);
1060	isl_val_free(v: data.v);
1061	if (!data.aff)
1062	break;
1063	}
1064
1065	if (data.add)
1066	data.aff = isl_aff_add(aff1: data.aff, aff2: data.add);
1067
1068	*pos = data.pos;
1069	*neg = data.neg;
1070	return data.aff;
1071	}
1072
1073	/* Call "fn" on every non-zero coefficient of "aff",
1074	* passing it in the type of dimension (in terms of the domain),
1075	* the position and the value, as long as "fn" returns isl_bool_true.
1076	* If "reverse" is set, then the coefficients are considered in reverse order
1077	* within each type.
1078	*/
1079	static isl_bool every_non_zero_coefficient(__isl_keep isl_aff *aff,
1080	int reverse,
1081	isl_bool (*fn)(enum isl_dim_type type, int pos, __isl_take isl_val *v,
1082	void *user),
1083	void *user)
1084	{
1085	int i, j;
1086	enum isl_dim_type t[] = { isl_dim_param, isl_dim_in, isl_dim_div };
1087	enum isl_dim_type l[] = { isl_dim_param, isl_dim_set, isl_dim_div };
1088	isl_val *v;
1089
1090	for (i = 0; i < 3; ++i) {
1091	isl_size n;
1092
1093	n = isl_aff_dim(aff, type: t[i]);
1094	if (n < 0)
1095	return isl_bool_error;
1096	for (j = 0; j < n; ++j) {
1097	isl_bool ok;
1098	int pos;
1099
1100	pos = reverse ? n - 1 - j : j;
1101	v = isl_aff_get_coefficient_val(aff, type: t[i], pos);
1102	ok = isl_val_is_zero(v);
1103	if (ok >= 0 && !ok)
1104	ok = fn(l[i], pos, v, user);
1105	else
1106	isl_val_free(v);
1107	if (ok < 0 || !ok)
1108	return ok;
1109	}
1110	}
1111
1112	return isl_bool_true;
1113	}
1114
1115	/* Internal data structure for extract_rational.
1116	*
1117	* "d" is the denominator of the original affine expression.
1118	* "ls" is its domain local space.
1119	* "rat" collects the rational part.
1120	*/
1121	struct isl_ast_extract_rational_data {
1122	isl_val *d;
1123	isl_local_space *ls;
1124
1125	isl_aff *rat;
1126	};
1127
1128	/* Given a non-zero term in an affine expression equal to "v" times
1129	* the variable of type "type" at position "pos",
1130	* add it to data->rat if "v" is not a multiple of data->d.
1131	*/
1132	static isl_bool add_rational(enum isl_dim_type type, int pos,
1133	__isl_take isl_val *v, void *user)
1134	{
1135	struct isl_ast_extract_rational_data *data = user;
1136	isl_aff *rat;
1137
1138	if (isl_val_is_divisible_by(v1: v, v2: data->d)) {
1139	isl_val_free(v);
1140	return isl_bool_true;
1141	}
1142	rat = isl_aff_var_on_domain(ls: isl_local_space_copy(ls: data->ls), type, pos);
1143	rat = isl_aff_scale_val(aff: rat, v);
1144	data->rat = isl_aff_add(aff1: data->rat, aff2: rat);
1145	return isl_bool_true;
1146	}
1147
1148	/* Check if aff involves any non-integer coefficients.
1149	* If so, split aff into
1150	*
1151	* aff = aff1 + (aff2 / d)
1152	*
1153	* with both aff1 and aff2 having only integer coefficients.
1154	* Return aff1 and add (aff2 / d) to *expr.
1155	*/
1156	static __isl_give isl_aff *extract_rational(__isl_take isl_aff *aff,
1157	__isl_keep isl_ast_expr **expr, __isl_keep isl_ast_build *build)
1158	{
1159	struct isl_ast_extract_rational_data data = { NULL };
1160	isl_ast_expr *rat_expr;
1161	isl_val *v;
1162
1163	if (!aff)
1164	return NULL;
1165	data.d = isl_aff_get_denominator_val(aff);
1166	if (!data.d)
1167	goto error;
1168	if (isl_val_is_one(v: data.d)) {
1169	isl_val_free(v: data.d);
1170	return aff;
1171	}
1172
1173	aff = isl_aff_scale_val(aff, v: isl_val_copy(v: data.d));
1174
1175	data.ls = isl_aff_get_domain_local_space(aff);
1176	data.rat = isl_aff_zero_on_domain(ls: isl_local_space_copy(ls: data.ls));
1177
1178	if (every_non_zero_coefficient(aff, reverse: 0, fn: &add_rational, user: &data) < 0)
1179	goto error;
1180
1181	v = isl_aff_get_constant_val(aff);
1182	if (isl_val_is_divisible_by(v1: v, v2: data.d)) {
1183	isl_val_free(v);
1184	} else {
1185	isl_aff *rat_0;
1186
1187	rat_0 = isl_aff_val_on_domain(ls: isl_local_space_copy(ls: data.ls), val: v);
1188	data.rat = isl_aff_add(aff1: data.rat, aff2: rat_0);
1189	}
1190
1191	isl_local_space_free(ls: data.ls);
1192
1193	aff = isl_aff_sub(aff1: aff, aff2: isl_aff_copy(aff: data.rat));
1194	aff = isl_aff_scale_down_val(aff, v: isl_val_copy(v: data.d));
1195
1196	rat_expr = div_mod(type: isl_ast_expr_op_div, aff: data.rat, v: data.d, build);
1197	*expr = ast_expr_add(expr1: *expr, expr2: rat_expr);
1198
1199	return aff;
1200	error:
1201	isl_aff_free(aff: data.rat);
1202	isl_local_space_free(ls: data.ls);
1203	isl_aff_free(aff);
1204	isl_val_free(v: data.d);
1205	return NULL;
1206	}
1207
1208	/* Internal data structure for isl_ast_expr_from_aff.
1209	*
1210	* "term" contains the information for adding a term.
1211	* "expr" collects the results.
1212	*/
1213	struct isl_ast_add_terms_data {
1214	struct isl_ast_add_term_data *term;
1215	isl_ast_expr *expr;
1216	};
1217
1218	/* Given a non-zero term in an affine expression equal to "v" times
1219	* the variable of type "type" at position "pos",
1220	* add the corresponding AST expression to data->expr.
1221	*/
1222	static isl_bool add_term(enum isl_dim_type type, int pos,
1223	__isl_take isl_val *v, void *user)
1224	{
1225	struct isl_ast_add_terms_data *data = user;
1226
1227	data->expr =
1228	isl_ast_expr_add_term(expr: data->expr, type, pos, v, data: data->term);
1229
1230	return isl_bool_true;
1231	}
1232
1233	/* Add terms to "expr" for each variable in "aff".
1234	* The result is simplified in terms of data->build->domain.
1235	*/
1236	static __isl_give isl_ast_expr *add_terms(__isl_take isl_ast_expr *expr,
1237	__isl_keep isl_aff *aff, struct isl_ast_add_term_data *data)
1238	{
1239	struct isl_ast_add_terms_data terms_data = { data, expr };
1240
1241	if (every_non_zero_coefficient(aff, reverse: 0, fn: &add_term, user: &terms_data) < 0)
1242	return isl_ast_expr_free(expr: terms_data.expr);
1243
1244	return terms_data.expr;
1245	}
1246
1247	/* Construct an isl_ast_expr that evaluates the affine expression "aff".
1248	* The result is simplified in terms of build->domain.
1249	*
1250	* We first extract hidden modulo computations from the affine expression
1251	* and then add terms for each variable with a non-zero coefficient.
1252	* Finally, if the affine expression has a non-trivial denominator,
1253	* we divide the resulting isl_ast_expr by this denominator.
1254	*/
1255	__isl_give isl_ast_expr *isl_ast_expr_from_aff(__isl_take isl_aff *aff,
1256	__isl_keep isl_ast_build *build)
1257	{
1258	isl_ctx *ctx = isl_aff_get_ctx(aff);
1259	isl_ast_expr *expr, *expr_neg;
1260	struct isl_ast_add_term_data term_data;
1261
1262	if (!aff)
1263	return NULL;
1264
1265	expr = isl_ast_expr_alloc_int_si(ctx, i: 0);
1266	expr_neg = isl_ast_expr_alloc_int_si(ctx, i: 0);
1267
1268	aff = extract_rational(aff, expr: &expr, build);
1269
1270	aff = extract_modulos(aff, pos: &expr, neg: &expr_neg, build);
1271	expr = ast_expr_sub(expr1: expr, expr2: expr_neg);
1272
1273	term_data.build = build;
1274	term_data.ls = isl_aff_get_domain_local_space(aff);
1275	term_data.cst = isl_aff_get_constant_val(aff);
1276	expr = add_terms(expr, aff, data: &term_data);
1277
1278	expr = isl_ast_expr_add_int(expr, v: term_data.cst);
1279	isl_local_space_free(ls: term_data.ls);
1280
1281	isl_aff_free(aff);
1282	return expr;
1283	}
1284
1285	/* Internal data structure for coefficients_of_sign.
1286	*
1287	* "sign" is the sign of the coefficients that should be retained.
1288	* "aff" is the affine expression of which some coefficients are zeroed out.
1289	*/
1290	struct isl_ast_coefficients_of_sign_data {
1291	int sign;
1292	isl_aff *aff;
1293	};
1294
1295	/* Clear the specified coefficient of data->aff if the value "v"
1296	* does not have the required sign.
1297	*/
1298	static isl_bool clear_opposite_sign(enum isl_dim_type type, int pos,
1299	__isl_take isl_val *v, void *user)
1300	{
1301	struct isl_ast_coefficients_of_sign_data *data = user;
1302
1303	if (type == isl_dim_set)
1304	type = isl_dim_in;
1305	if (data->sign * isl_val_sgn(v) < 0)
1306	data->aff = isl_aff_set_coefficient_si(aff: data->aff, type, pos, v: 0);
1307	isl_val_free(v);
1308
1309	return isl_bool_true;
1310	}
1311
1312	/* Extract the coefficients of "aff" (excluding the constant term)
1313	* that have the given sign.
1314	*
1315	* Take a copy of "aff" and clear the coefficients that do not have
1316	* the required sign.
1317	* Consider the coefficients in reverse order since clearing
1318	* the coefficient of an integer division in data.aff
1319	* could result in the removal of that integer division from data.aff,
1320	* changing the positions of all subsequent integer divisions of data.aff,
1321	* while those of "aff" remain the same.
1322	*/
1323	static __isl_give isl_aff *coefficients_of_sign(__isl_take isl_aff *aff,
1324	int sign)
1325	{
1326	struct isl_ast_coefficients_of_sign_data data;
1327
1328	data.sign = sign;
1329	data.aff = isl_aff_copy(aff);
1330	if (every_non_zero_coefficient(aff, reverse: 1, fn: &clear_opposite_sign, user: &data) < 0)
1331	data.aff = isl_aff_free(aff: data.aff);
1332	isl_aff_free(aff);
1333
1334	data.aff = isl_aff_set_constant_si(aff: data.aff, v: 0);
1335
1336	return data.aff;
1337	}
1338
1339	/* Should the constant term "v" be considered positive?
1340	*
1341	* A positive constant will be added to "pos" by the caller,
1342	* while a negative constant will be added to "neg".
1343	* If either "pos" or "neg" is exactly zero, then we prefer
1344	* to add the constant "v" to that side, irrespective of the sign of "v".
1345	* This results in slightly shorter expressions and may reduce the risk
1346	* of overflows.
1347	*/
1348	static isl_bool constant_is_considered_positive(__isl_keep isl_val *v,
1349	__isl_keep isl_ast_expr *pos, __isl_keep isl_ast_expr *neg)
1350	{
1351	isl_bool zero;
1352
1353	zero = ast_expr_is_zero(expr: pos);
1354	if (zero < 0 || zero)
1355	return zero;
1356	zero = ast_expr_is_zero(expr: neg);
1357	if (zero < 0 || zero)
1358	return isl_bool_not(b: zero);
1359	return isl_val_is_pos(v);
1360	}
1361
1362	/* Check if the equality
1363	*
1364	* aff = 0
1365	*
1366	* represents a stride constraint on the integer division "pos".
1367	*
1368	* In particular, if the integer division "pos" is equal to
1369	*
1370	* floor(e/d)
1371	*
1372	* then check if aff is equal to
1373	*
1374	* e - d floor(e/d)
1375	*
1376	* or its opposite.
1377	*
1378	* If so, the equality is exactly
1379	*
1380	* e mod d = 0
1381	*
1382	* Note that in principle we could also accept
1383	*
1384	* e - d floor(e'/d)
1385	*
1386	* where e and e' differ by a constant.
1387	*/
1388	static isl_bool is_stride_constraint(__isl_keep isl_aff *aff, int pos)
1389	{
1390	isl_aff *div;
1391	isl_val *c, *d;
1392	isl_bool eq;
1393
1394	div = isl_aff_get_div(aff, pos);
1395	c = isl_aff_get_coefficient_val(aff, type: isl_dim_div, pos);
1396	d = isl_aff_get_denominator_val(aff: div);
1397	eq = isl_val_abs_eq(v1: c, v2: d);
1398	if (eq >= 0 && eq) {
1399	aff = isl_aff_copy(aff);
1400	aff = isl_aff_set_coefficient_si(aff, type: isl_dim_div, pos, v: 0);
1401	div = isl_aff_scale_val(aff: div, v: d);
1402	if (isl_val_is_pos(v: c))
1403	div = isl_aff_neg(aff: div);
1404	eq = isl_aff_plain_is_equal(aff1: div, aff2: aff);
1405	isl_aff_free(aff);
1406	} else
1407	isl_val_free(v: d);
1408	isl_val_free(v: c);
1409	isl_aff_free(aff: div);
1410
1411	return eq;
1412	}
1413
1414	/* Are all coefficients of "aff" (zero or) negative?
1415	*/
1416	static isl_bool all_negative_coefficients(__isl_keep isl_aff *aff)
1417	{
1418	int i;
1419	isl_size n;
1420
1421	n = isl_aff_dim(aff, type: isl_dim_param);
1422	if (n < 0)
1423	return isl_bool_error;
1424	for (i = 0; i < n; ++i)
1425	if (isl_aff_coefficient_sgn(aff, type: isl_dim_param, pos: i) > 0)
1426	return isl_bool_false;
1427
1428	n = isl_aff_dim(aff, type: isl_dim_in);
1429	if (n < 0)
1430	return isl_bool_error;
1431	for (i = 0; i < n; ++i)
1432	if (isl_aff_coefficient_sgn(aff, type: isl_dim_in, pos: i) > 0)
1433	return isl_bool_false;
1434
1435	return isl_bool_true;
1436	}
1437
1438	/* Give an equality of the form
1439	*
1440	* aff = e - d floor(e/d) = 0
1441	*
1442	* or
1443	*
1444	* aff = -e + d floor(e/d) = 0
1445	*
1446	* with the integer division "pos" equal to floor(e/d),
1447	* construct the AST expression
1448	*
1449	* (isl_ast_expr_op_eq,
1450	* (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1451	*
1452	* If e only has negative coefficients, then construct
1453	*
1454	* (isl_ast_expr_op_eq,
1455	* (isl_ast_expr_op_zdiv_r, expr(-e), expr(d)), expr(0))
1456	*
1457	* instead.
1458	*/
1459	static __isl_give isl_ast_expr *extract_stride_constraint(
1460	__isl_take isl_aff *aff, int pos, __isl_keep isl_ast_build *build)
1461	{
1462	isl_bool all_neg;
1463	isl_ctx *ctx;
1464	isl_val *c;
1465	isl_ast_expr *expr, *cst;
1466
1467	if (!aff)
1468	return NULL;
1469
1470	ctx = isl_aff_get_ctx(aff);
1471
1472	c = isl_aff_get_coefficient_val(aff, type: isl_dim_div, pos);
1473	aff = isl_aff_set_coefficient_si(aff, type: isl_dim_div, pos, v: 0);
1474
1475	all_neg = all_negative_coefficients(aff);
1476	if (all_neg < 0)
1477	aff = isl_aff_free(aff);
1478	else if (all_neg)
1479	aff = isl_aff_neg(aff);
1480
1481	cst = isl_ast_expr_from_val(v: isl_val_abs(v: c));
1482	expr = isl_ast_expr_from_aff(aff, build);
1483
1484	expr = isl_ast_expr_alloc_binary(type: isl_ast_expr_op_zdiv_r, expr1: expr, expr2: cst);
1485	cst = isl_ast_expr_alloc_int_si(ctx, i: 0);
1486	expr = isl_ast_expr_alloc_binary(type: isl_ast_expr_op_eq, expr1: expr, expr2: cst);
1487
1488	return expr;
1489	}
1490
1491	/* Construct an isl_ast_expr evaluating
1492	*
1493	* "expr_pos" == "expr_neg", if "eq" is set, or
1494	* "expr_pos" >= "expr_neg", if "eq" is not set
1495	*
1496	* However, if "expr_pos" is an integer constant (and "expr_neg" is not),
1497	* then the two expressions are interchanged. This ensures that,
1498	* e.g., "i <= 5" is constructed rather than "5 >= i".
1499	*/
1500	static __isl_give isl_ast_expr *construct_constraint_expr(int eq,
1501	__isl_take isl_ast_expr *expr_pos, __isl_take isl_ast_expr *expr_neg)
1502	{
1503	isl_ast_expr *expr;
1504	enum isl_ast_expr_op_type type;
1505	int pos_is_cst, neg_is_cst;
1506
1507	pos_is_cst = isl_ast_expr_get_type(expr: expr_pos) == isl_ast_expr_int;
1508	neg_is_cst = isl_ast_expr_get_type(expr: expr_neg) == isl_ast_expr_int;
1509	if (pos_is_cst && !neg_is_cst) {
1510	type = eq ? isl_ast_expr_op_eq : isl_ast_expr_op_le;
1511	expr = isl_ast_expr_alloc_binary(type, expr1: expr_neg, expr2: expr_pos);
1512	} else {
1513	type = eq ? isl_ast_expr_op_eq : isl_ast_expr_op_ge;
1514	expr = isl_ast_expr_alloc_binary(type, expr1: expr_pos, expr2: expr_neg);
1515	}
1516
1517	return expr;
1518	}
1519
1520	/* Construct an isl_ast_expr that evaluates the condition "aff" == 0
1521	* (if "eq" is set) or "aff" >= 0 (otherwise).
1522	* The result is simplified in terms of build->domain.
1523	*
1524	* We first extract hidden modulo computations from "aff"
1525	* and then collect all the terms with a positive coefficient in cons_pos
1526	* and the terms with a negative coefficient in cons_neg.
1527	*
1528	* The result is then essentially of the form
1529	*
1530	* (isl_ast_expr_op_ge, expr(pos), expr(-neg)))
1531	*
1532	* or
1533	*
1534	* (isl_ast_expr_op_eq, expr(pos), expr(-neg)))
1535	*
1536	* However, if there are no terms with positive coefficients (or no terms
1537	* with negative coefficients), then the constant term is added to "pos"
1538	* (or "neg"), ignoring the sign of the constant term.
1539	*/
1540	static __isl_give isl_ast_expr *isl_ast_expr_from_constraint_no_stride(
1541	int eq, __isl_take isl_aff *aff, __isl_keep isl_ast_build *build)
1542	{
1543	isl_bool cst_is_pos;
1544	isl_ctx *ctx;
1545	isl_ast_expr *expr_pos;
1546	isl_ast_expr *expr_neg;
1547	isl_aff *aff_pos, *aff_neg;
1548	struct isl_ast_add_term_data data;
1549
1550	ctx = isl_aff_get_ctx(aff);
1551	expr_pos = isl_ast_expr_alloc_int_si(ctx, i: 0);
1552	expr_neg = isl_ast_expr_alloc_int_si(ctx, i: 0);
1553
1554	aff = extract_modulos(aff, pos: &expr_pos, neg: &expr_neg, build);
1555
1556	data.build = build;
1557	data.ls = isl_aff_get_domain_local_space(aff);
1558	data.cst = isl_aff_get_constant_val(aff);
1559
1560	aff_pos = coefficients_of_sign(aff: isl_aff_copy(aff), sign: 1);
1561	aff_neg = isl_aff_neg(aff: coefficients_of_sign(aff, sign: -1));
1562
1563	expr_pos = add_terms(expr: expr_pos, aff: aff_pos, data: &data);
1564	data.cst = isl_val_neg(v: data.cst);
1565	expr_neg = add_terms(expr: expr_neg, aff: aff_neg, data: &data);
1566	data.cst = isl_val_neg(v: data.cst);
1567	isl_local_space_free(ls: data.ls);
1568
1569	cst_is_pos =
1570	constant_is_considered_positive(v: data.cst, pos: expr_pos, neg: expr_neg);
1571	if (cst_is_pos < 0)
1572	expr_pos = isl_ast_expr_free(expr: expr_pos);
1573
1574	if (cst_is_pos) {
1575	expr_pos = isl_ast_expr_add_int(expr: expr_pos, v: data.cst);
1576	} else {
1577	data.cst = isl_val_neg(v: data.cst);
1578	expr_neg = isl_ast_expr_add_int(expr: expr_neg, v: data.cst);
1579	}
1580
1581	isl_aff_free(aff: aff_pos);
1582	isl_aff_free(aff: aff_neg);
1583	return construct_constraint_expr(eq, expr_pos, expr_neg);
1584	}
1585
1586	/* Construct an isl_ast_expr that evaluates the condition "constraint".
1587	* The result is simplified in terms of build->domain.
1588	*
1589	* We first check if the constraint is an equality of the form
1590	*
1591	* e - d floor(e/d) = 0
1592	*
1593	* i.e.,
1594	*
1595	* e mod d = 0
1596	*
1597	* If so, we convert it to
1598	*
1599	* (isl_ast_expr_op_eq,
1600	* (isl_ast_expr_op_zdiv_r, expr(e), expr(d)), expr(0))
1601	*/
1602	static __isl_give isl_ast_expr *isl_ast_expr_from_constraint(
1603	__isl_take isl_constraint *constraint, __isl_keep isl_ast_build *build)
1604	{
1605	int i;
1606	isl_size n;
1607	isl_aff *aff;
1608	isl_bool eq;
1609
1610	aff = isl_constraint_get_aff(constraint);
1611	eq = isl_constraint_is_equality(constraint);
1612	isl_constraint_free(c: constraint);
1613	if (eq < 0)
1614	goto error;
1615
1616	n = isl_aff_dim(aff, type: isl_dim_div);
1617	if (n < 0)
1618	aff = isl_aff_free(aff);
1619	if (eq && n > 0)
1620	for (i = 0; i < n; ++i) {
1621	isl_bool is_stride;
1622	is_stride = is_stride_constraint(aff, pos: i);
1623	if (is_stride < 0)
1624	goto error;
1625	if (is_stride)
1626	return extract_stride_constraint(aff, pos: i, build);
1627	}
1628
1629	return isl_ast_expr_from_constraint_no_stride(eq, aff, build);
1630	error:
1631	isl_aff_free(aff);
1632	return NULL;
1633	}
1634
1635	/* Wrapper around isl_constraint_cmp_last_non_zero for use
1636	* as a callback to isl_constraint_list_sort.
1637	* If isl_constraint_cmp_last_non_zero cannot tell the constraints
1638	* apart, then use isl_constraint_plain_cmp instead.
1639	*/
1640	static int cmp_constraint(__isl_keep isl_constraint *a,
1641	__isl_keep isl_constraint *b, void *user)
1642	{
1643	int cmp;
1644
1645	cmp = isl_constraint_cmp_last_non_zero(c1: a, c2: b);
1646	if (cmp != 0)
1647	return cmp;
1648	return isl_constraint_plain_cmp(c1: a, c2: b);
1649	}
1650
1651	/* Construct an isl_ast_expr that evaluates the conditions defining "bset".
1652	* The result is simplified in terms of build->domain.
1653	*
1654	* If "bset" is not bounded by any constraint, then we construct
1655	* the expression "1", i.e., "true".
1656	*
1657	* Otherwise, we sort the constraints, putting constraints that involve
1658	* integer divisions after those that do not, and construct an "and"
1659	* of the ast expressions of the individual constraints.
1660	*
1661	* Each constraint is added to the generated constraints of the build
1662	* after it has been converted to an AST expression so that it can be used
1663	* to simplify the following constraints. This may change the truth value
1664	* of subsequent constraints that do not satisfy the earlier constraints,
1665	* but this does not affect the outcome of the conjunction as it is
1666	* only true if all the conjuncts are true (no matter in what order
1667	* they are evaluated). In particular, the constraints that do not
1668	* involve integer divisions may serve to simplify some constraints
1669	* that do involve integer divisions.
1670	*/
1671	__isl_give isl_ast_expr *isl_ast_build_expr_from_basic_set(
1672	__isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
1673	{
1674	int i;
1675	isl_size n;
1676	isl_constraint *c;
1677	isl_constraint_list *list;
1678	isl_ast_expr *res;
1679	isl_set *set;
1680
1681	list = isl_basic_set_get_constraint_list(bset);
1682	isl_basic_set_free(bset);
1683	list = isl_constraint_list_sort(list, cmp: &cmp_constraint, NULL);
1684	n = isl_constraint_list_n_constraint(list);
1685	if (n < 0)
1686	build = NULL;
1687	if (n == 0) {
1688	isl_ctx *ctx = isl_constraint_list_get_ctx(list);
1689	isl_constraint_list_free(list);
1690	return isl_ast_expr_alloc_int_si(ctx, i: 1);
1691	}
1692
1693	build = isl_ast_build_copy(build);
1694
1695	c = isl_constraint_list_get_constraint(list, index: 0);
1696	bset = isl_basic_set_from_constraint(constraint: isl_constraint_copy(c));
1697	set = isl_set_from_basic_set(bset);
1698	res = isl_ast_expr_from_constraint(constraint: c, build);
1699	build = isl_ast_build_restrict_generated(build, set);
1700
1701	for (i = 1; i < n; ++i) {
1702	isl_ast_expr *expr;
1703
1704	c = isl_constraint_list_get_constraint(list, index: i);
1705	bset = isl_basic_set_from_constraint(constraint: isl_constraint_copy(c));
1706	set = isl_set_from_basic_set(bset);
1707	expr = isl_ast_expr_from_constraint(constraint: c, build);
1708	build = isl_ast_build_restrict_generated(build, set);
1709	res = isl_ast_expr_and(expr1: res, expr2: expr);
1710	}
1711
1712	isl_constraint_list_free(list);
1713	isl_ast_build_free(build);
1714	return res;
1715	}
1716
1717	/* Construct an isl_ast_expr that evaluates the conditions defining "set".
1718	* The result is simplified in terms of build->domain.
1719	*
1720	* If "set" is an (obviously) empty set, then return the expression "0".
1721	*
1722	* If there are multiple disjuncts in the description of the set,
1723	* then subsequent disjuncts are simplified in a context where
1724	* the previous disjuncts have been removed from build->domain.
1725	* In particular, constraints that ensure that there is no overlap
1726	* with these previous disjuncts, can be removed.
1727	* This is mostly useful for disjuncts that are only defined by
1728	* a single constraint (relative to the build domain) as the opposite
1729	* of that single constraint can then be removed from the other disjuncts.
1730	* In order not to increase the number of disjuncts in the build domain
1731	* after subtracting the previous disjuncts of "set", the simple hull
1732	* is computed after taking the difference with each of these disjuncts.
1733	* This means that constraints that prevent overlap with a union
1734	* of multiple previous disjuncts are not removed.
1735	*
1736	* "set" lives in the internal schedule space.
1737	*/
1738	__isl_give isl_ast_expr *isl_ast_build_expr_from_set_internal(
1739	__isl_keep isl_ast_build *build, __isl_take isl_set *set)
1740	{
1741	int i;
1742	isl_size n;
1743	isl_basic_set *bset;
1744	isl_basic_set_list *list;
1745	isl_set *domain;
1746	isl_ast_expr *res;
1747
1748	list = isl_set_get_basic_set_list(set);
1749	isl_set_free(set);
1750
1751	n = isl_basic_set_list_n_basic_set(list);
1752	if (n < 0)
1753	build = NULL;
1754	if (n == 0) {
1755	isl_ctx *ctx = isl_ast_build_get_ctx(build);
1756	isl_basic_set_list_free(list);
1757	return isl_ast_expr_from_val(v: isl_val_zero(ctx));
1758	}
1759
1760	domain = isl_ast_build_get_domain(build);
1761
1762	bset = isl_basic_set_list_get_basic_set(list, index: 0);
1763	set = isl_set_from_basic_set(bset: isl_basic_set_copy(bset));
1764	res = isl_ast_build_expr_from_basic_set(build, bset);
1765
1766	for (i = 1; i < n; ++i) {
1767	isl_ast_expr *expr;
1768	isl_set *rest;
1769
1770	rest = isl_set_subtract(set1: isl_set_copy(set: domain), set2: set);
1771	rest = isl_set_from_basic_set(bset: isl_set_simple_hull(set: rest));
1772	domain = isl_set_intersect(set1: domain, set2: rest);
1773	bset = isl_basic_set_list_get_basic_set(list, index: i);
1774	set = isl_set_from_basic_set(bset: isl_basic_set_copy(bset));
1775	bset = isl_basic_set_gist(bset,
1776	context: isl_set_simple_hull(set: isl_set_copy(set: domain)));
1777	expr = isl_ast_build_expr_from_basic_set(build, bset);
1778	res = isl_ast_expr_or(expr1: res, expr2: expr);
1779	}
1780
1781	isl_set_free(set: domain);
1782	isl_set_free(set);
1783	isl_basic_set_list_free(list);
1784	return res;
1785	}
1786
1787	/* Construct an isl_ast_expr that evaluates the conditions defining "set".
1788	* The result is simplified in terms of build->domain.
1789	*
1790	* If "set" is an (obviously) empty set, then return the expression "0".
1791	*
1792	* "set" lives in the external schedule space.
1793	*
1794	* The internal AST expression generation assumes that there are
1795	* no unknown divs, so make sure an explicit representation is available.
1796	* Since the set comes from the outside, it may have constraints that
1797	* are redundant with respect to the build domain. Remove them first.
1798	*/
1799	__isl_give isl_ast_expr *isl_ast_build_expr_from_set(
1800	__isl_keep isl_ast_build *build, __isl_take isl_set *set)
1801	{
1802	isl_bool needs_map;
1803
1804	needs_map = isl_ast_build_need_schedule_map(build);
1805	if (needs_map < 0) {
1806	set = isl_set_free(set);
1807	} else if (needs_map) {
1808	isl_multi_aff *ma;
1809	ma = isl_ast_build_get_schedule_map_multi_aff(build);
1810	set = isl_set_preimage_multi_aff(set, ma);
1811	}
1812
1813	set = isl_set_compute_divs(set);
1814	set = isl_ast_build_compute_gist(build, set);
1815	return isl_ast_build_expr_from_set_internal(build, set);
1816	}
1817
1818	/* State of data about previous pieces in
1819	* isl_ast_build_expr_from_pw_aff_internal.
1820	*
1821	* isl_state_none: no data about previous pieces
1822	* isl_state_single: data about a single previous piece
1823	* isl_state_min: data represents minimum of several pieces
1824	* isl_state_max: data represents maximum of several pieces
1825	*/
1826	enum isl_from_pw_aff_state {
1827	isl_state_none,
1828	isl_state_single,
1829	isl_state_min,
1830	isl_state_max
1831	};
1832
1833	/* Internal date structure representing a single piece in the input of
1834	* isl_ast_build_expr_from_pw_aff_internal.
1835	*
1836	* If "state" is isl_state_none, then "set_list" and "aff_list" are not used.
1837	* If "state" is isl_state_single, then "set_list" and "aff_list" contain the
1838	* single previous subpiece.
1839	* If "state" is isl_state_min, then "set_list" and "aff_list" contain
1840	* a sequence of several previous subpieces that are equal to the minimum
1841	* of the entries in "aff_list" over the union of "set_list"
1842	* If "state" is isl_state_max, then "set_list" and "aff_list" contain
1843	* a sequence of several previous subpieces that are equal to the maximum
1844	* of the entries in "aff_list" over the union of "set_list"
1845	*
1846	* During the construction of the pieces, "set" is NULL.
1847	* After the construction, "set" is set to the union of the elements
1848	* in "set_list", at which point "set_list" is set to NULL.
1849	*/
1850	struct isl_from_pw_aff_piece {
1851	enum isl_from_pw_aff_state state;
1852	isl_set *set;
1853	isl_set_list *set_list;
1854	isl_aff_list *aff_list;
1855	};
1856
1857	/* Internal data structure for isl_ast_build_expr_from_pw_aff_internal.
1858	*
1859	* "build" specifies the domain against which the result is simplified.
1860	* "dom" is the domain of the entire isl_pw_aff.
1861	*
1862	* "n" is the number of pieces constructed already.
1863	* In particular, during the construction of the pieces, "n" points to
1864	* the piece that is being constructed. After the construction of the
1865	* pieces, "n" is set to the total number of pieces.
1866	* "max" is the total number of allocated entries.
1867	* "p" contains the individual pieces.
1868	*/
1869	struct isl_from_pw_aff_data {
1870	isl_ast_build *build;
1871	isl_set *dom;
1872
1873	int n;
1874	int max;
1875	struct isl_from_pw_aff_piece *p;
1876	};
1877
1878	/* Initialize "data" based on "build" and "pa".
1879	*/
1880	static isl_stat isl_from_pw_aff_data_init(struct isl_from_pw_aff_data *data,
1881	__isl_keep isl_ast_build *build, __isl_keep isl_pw_aff *pa)
1882	{
1883	isl_size n;
1884	isl_ctx *ctx;
1885
1886	ctx = isl_pw_aff_get_ctx(pwaff: pa);
1887	n = isl_pw_aff_n_piece(pwaff: pa);
1888	if (n < 0)
1889	return isl_stat_error;
1890	if (n == 0)
1891	isl_die(ctx, isl_error_invalid,
1892	"cannot handle void expression", return isl_stat_error);
1893	data->max = n;
1894	data->p = isl_calloc_array(ctx, struct isl_from_pw_aff_piece, n);
1895	if (!data->p)
1896	return isl_stat_error;
1897	data->build = build;
1898	data->dom = isl_pw_aff_domain(pwaff: isl_pw_aff_copy(pwaff: pa));
1899	data->n = 0;
1900
1901	return isl_stat_ok;
1902	}
1903
1904	/* Free all memory allocated for "data".
1905	*/
1906	static void isl_from_pw_aff_data_clear(struct isl_from_pw_aff_data *data)
1907	{
1908	int i;
1909
1910	isl_set_free(set: data->dom);
1911	if (!data->p)
1912	return;
1913
1914	for (i = 0; i < data->max; ++i) {
1915	isl_set_free(set: data->p[i].set);
1916	isl_set_list_free(list: data->p[i].set_list);
1917	isl_aff_list_free(list: data->p[i].aff_list);
1918	}
1919	free(ptr: data->p);
1920	}
1921
1922	/* Initialize the current entry of "data" to an unused piece.
1923	*/
1924	static void set_none(struct isl_from_pw_aff_data *data)
1925	{
1926	data->p[data->n].state = isl_state_none;
1927	data->p[data->n].set_list = NULL;
1928	data->p[data->n].aff_list = NULL;
1929	}
1930
1931	/* Store "set" and "aff" in the current entry of "data" as a single subpiece.
1932	*/
1933	static void set_single(struct isl_from_pw_aff_data *data,
1934	__isl_take isl_set *set, __isl_take isl_aff *aff)
1935	{
1936	data->p[data->n].state = isl_state_single;
1937	data->p[data->n].set_list = isl_set_list_from_set(el: set);
1938	data->p[data->n].aff_list = isl_aff_list_from_aff(el: aff);
1939	}
1940
1941	/* Extend the current entry of "data" with "set" and "aff"
1942	* as a minimum expression.
1943	*/
1944	static isl_stat extend_min(struct isl_from_pw_aff_data *data,
1945	__isl_take isl_set *set, __isl_take isl_aff *aff)
1946	{
1947	int n = data->n;
1948	data->p[n].state = isl_state_min;
1949	data->p[n].set_list = isl_set_list_add(list: data->p[n].set_list, el: set);
1950	data->p[n].aff_list = isl_aff_list_add(list: data->p[n].aff_list, el: aff);
1951
1952	if (!data->p[n].set_list || !data->p[n].aff_list)
1953	return isl_stat_error;
1954	return isl_stat_ok;
1955	}
1956
1957	/* Extend the current entry of "data" with "set" and "aff"
1958	* as a maximum expression.
1959	*/
1960	static isl_stat extend_max(struct isl_from_pw_aff_data *data,
1961	__isl_take isl_set *set, __isl_take isl_aff *aff)
1962	{
1963	int n = data->n;
1964	data->p[n].state = isl_state_max;
1965	data->p[n].set_list = isl_set_list_add(list: data->p[n].set_list, el: set);
1966	data->p[n].aff_list = isl_aff_list_add(list: data->p[n].aff_list, el: aff);
1967
1968	if (!data->p[n].set_list || !data->p[n].aff_list)
1969	return isl_stat_error;
1970	return isl_stat_ok;
1971	}
1972
1973	/* Extend the domain of the current entry of "data", which is assumed
1974	* to contain a single subpiece, with "set". If "replace" is set,
1975	* then also replace the affine function by "aff". Otherwise,
1976	* simply free "aff".
1977	*/
1978	static isl_stat extend_domain(struct isl_from_pw_aff_data *data,
1979	__isl_take isl_set *set, __isl_take isl_aff *aff, int replace)
1980	{
1981	int n = data->n;
1982	isl_set *set_n;
1983
1984	set_n = isl_set_list_get_set(list: data->p[n].set_list, index: 0);
1985	set_n = isl_set_union(set1: set_n, set2: set);
1986	data->p[n].set_list =
1987	isl_set_list_set_set(list: data->p[n].set_list, index: 0, el: set_n);
1988
1989	if (replace)
1990	data->p[n].aff_list =
1991	isl_aff_list_set_aff(list: data->p[n].aff_list, index: 0, el: aff);
1992	else
1993	isl_aff_free(aff);
1994
1995	if (!data->p[n].set_list || !data->p[n].aff_list)
1996	return isl_stat_error;
1997	return isl_stat_ok;
1998	}
1999
2000	/* Construct an isl_ast_expr from "list" within "build".
2001	* If "state" is isl_state_single, then "list" contains a single entry and
2002	* an isl_ast_expr is constructed for that entry.
2003	* Otherwise a min or max expression is constructed from "list"
2004	* depending on "state".
2005	*/
2006	static __isl_give isl_ast_expr *ast_expr_from_aff_list(
2007	__isl_take isl_aff_list *list, enum isl_from_pw_aff_state state,
2008	__isl_keep isl_ast_build *build)
2009	{
2010	int i;
2011	isl_size n;
2012	isl_aff *aff;
2013	isl_ast_expr *expr = NULL;
2014	enum isl_ast_expr_op_type op_type;
2015
2016	if (state == isl_state_single) {
2017	aff = isl_aff_list_get_aff(list, index: 0);
2018	isl_aff_list_free(list);
2019	return isl_ast_expr_from_aff(aff, build);
2020	}
2021	n = isl_aff_list_n_aff(list);
2022	if (n < 0)
2023	goto error;
2024	op_type = state == isl_state_min ? isl_ast_expr_op_min
2025	: isl_ast_expr_op_max;
2026	expr = isl_ast_expr_alloc_op(ctx: isl_ast_build_get_ctx(build), op: op_type, n_arg: n);
2027
2028	for (i = 0; i < n; ++i) {
2029	isl_ast_expr *expr_i;
2030
2031	aff = isl_aff_list_get_aff(list, index: i);
2032	expr_i = isl_ast_expr_from_aff(aff, build);
2033	expr = isl_ast_expr_op_add_arg(expr, arg: expr_i);
2034	}
2035
2036	isl_aff_list_free(list);
2037	return expr;
2038	error:
2039	isl_aff_list_free(list);
2040	isl_ast_expr_free(expr);
2041	return NULL;
2042	}
2043
2044	/* Extend the list of expressions in "next" to take into account
2045	* the piece at position "pos" in "data", allowing for a further extension
2046	* for the next piece(s).
2047	* In particular, "next" is extended with a select operation that selects
2048	* an isl_ast_expr corresponding to data->aff_list on data->set and
2049	* to an expression that will be filled in by later calls.
2050	* Return a pointer to the arguments of this select operation.
2051	* Afterwards, the state of "data" is set to isl_state_none.
2052	*
2053	* The constraints of data->set are added to the generated
2054	* constraints of the build such that they can be exploited to simplify
2055	* the AST expression constructed from data->aff_list.
2056	*/
2057	static isl_ast_expr_list **add_intermediate_piece(
2058	struct isl_from_pw_aff_data *data,
2059	int pos, isl_ast_expr_list **next)
2060	{
2061	isl_ctx *ctx;
2062	isl_ast_build *build;
2063	isl_ast_expr *ternary, *arg;
2064	isl_set *set, *gist;
2065
2066	set = data->p[pos].set;
2067	data->p[pos].set = NULL;
2068	ctx = isl_ast_build_get_ctx(build: data->build);
2069	ternary = isl_ast_expr_alloc_op(ctx, op: isl_ast_expr_op_select, n_arg: 3);
2070	gist = isl_set_gist(set: isl_set_copy(set), context: isl_set_copy(set: data->dom));
2071	arg = isl_ast_build_expr_from_set_internal(build: data->build, set: gist);
2072	ternary = isl_ast_expr_op_add_arg(expr: ternary, arg);
2073	build = isl_ast_build_copy(build: data->build);
2074	build = isl_ast_build_restrict_generated(build, set);
2075	arg = ast_expr_from_aff_list(list: data->p[pos].aff_list,
2076	state: data->p[pos].state, build);
2077	data->p[pos].aff_list = NULL;
2078	isl_ast_build_free(build);
2079	ternary = isl_ast_expr_op_add_arg(expr: ternary, arg);
2080	data->p[pos].state = isl_state_none;
2081	if (!ternary)
2082	return NULL;
2083
2084	*next = isl_ast_expr_list_add(list: *next, el: ternary);
2085	return &ternary->u.op.args;
2086	}
2087
2088	/* Extend the list of expressions in "next" to take into account
2089	* the final piece, located at position "pos" in "data".
2090	* In particular, "next" is extended with an expression
2091	* to evaluate data->aff_list and the domain is ignored.
2092	* Return isl_stat_ok on success and isl_stat_error on failure.
2093	*
2094	* The constraints of data->set are however added to the generated
2095	* constraints of the build such that they can be exploited to simplify
2096	* the AST expression constructed from data->aff_list.
2097	*/
2098	static isl_stat add_last_piece(struct isl_from_pw_aff_data *data,
2099	int pos, isl_ast_expr_list **next)
2100	{
2101	isl_ast_build *build;
2102	isl_ast_expr *last;
2103
2104	if (data->p[pos].state == isl_state_none)
2105	isl_die(isl_ast_build_get_ctx(data->build), isl_error_invalid,
2106	"cannot handle void expression", return isl_stat_error);
2107
2108	build = isl_ast_build_copy(build: data->build);
2109	build = isl_ast_build_restrict_generated(build, set: data->p[pos].set);
2110	data->p[pos].set = NULL;
2111	last = ast_expr_from_aff_list(list: data->p[pos].aff_list,
2112	state: data->p[pos].state, build);
2113	*next = isl_ast_expr_list_add(list: *next, el: last);
2114	data->p[pos].aff_list = NULL;
2115	isl_ast_build_free(build);
2116	data->p[pos].state = isl_state_none;
2117	if (!*next)
2118	return isl_stat_error;
2119
2120	return isl_stat_ok;
2121	}
2122
2123	/* Return -1 if the piece "p1" should be sorted before "p2"
2124	* and 1 if it should be sorted after "p2".
2125	* Return 0 if they do not need to be sorted in a specific order.
2126	*
2127	* Pieces are sorted according to the number of disjuncts
2128	* in their domains.
2129	*/
2130	static int sort_pieces_cmp(const void *p1, const void *p2, void *arg)
2131	{
2132	const struct isl_from_pw_aff_piece *piece1 = p1;
2133	const struct isl_from_pw_aff_piece *piece2 = p2;
2134	isl_size n1, n2;
2135
2136	n1 = isl_set_n_basic_set(set: piece1->set);
2137	n2 = isl_set_n_basic_set(set: piece2->set);
2138
2139	return n1 - n2;
2140	}
2141
2142	/* Construct an isl_ast_expr from the pieces in "data".
2143	* Return the result or NULL on failure.
2144	*
2145	* When this function is called, data->n points to the current piece.
2146	* If this is an effective piece, then first increment data->n such
2147	* that data->n contains the number of pieces.
2148	* The "set_list" fields are subsequently replaced by the corresponding
2149	* "set" fields, after which the pieces are sorted according to
2150	* the number of disjuncts in these "set" fields.
2151	*
2152	* Construct intermediate AST expressions for the initial pieces and
2153	* finish off with the final pieces.
2154	*
2155	* Any piece that is not the very first is added to the list of arguments
2156	* of the previously constructed piece.
2157	* In order not to have to special case the first piece,
2158	* an extra list is created to hold the final result.
2159	*/
2160	static isl_ast_expr *build_pieces(struct isl_from_pw_aff_data *data)
2161	{
2162	int i;
2163	isl_ctx *ctx;
2164	isl_ast_expr_list *res_list;
2165	isl_ast_expr_list **next = &res_list;
2166	isl_ast_expr *res;
2167
2168	if (data->p[data->n].state != isl_state_none)
2169	data->n++;
2170	ctx = isl_ast_build_get_ctx(build: data->build);
2171	if (data->n == 0)
2172	isl_die(ctx, isl_error_invalid,
2173	"cannot handle void expression", return NULL);
2174
2175	for (i = 0; i < data->n; ++i) {
2176	data->p[i].set = isl_set_list_union(list: data->p[i].set_list);
2177	if (data->p[i].state != isl_state_single)
2178	data->p[i].set = isl_set_coalesce(set: data->p[i].set);
2179	data->p[i].set_list = NULL;
2180	}
2181
2182	if (isl_sort(pbase: data->p, total_elems: data->n, size: sizeof(data->p[0]),
2183	cmp: &sort_pieces_cmp, NULL) < 0)
2184	return NULL;
2185
2186	res_list = isl_ast_expr_list_alloc(ctx, n: 1);
2187	if (!res_list)
2188	return NULL;
2189	for (i = 0; i + 1 < data->n; ++i) {
2190	next = add_intermediate_piece(data, pos: i, next);
2191	if (!next)
2192	goto error;
2193	}
2194
2195	if (add_last_piece(data, pos: data->n - 1, next) < 0)
2196	goto error;
2197
2198	res = isl_ast_expr_list_get_at(list: res_list, index: 0);
2199	isl_ast_expr_list_free(list: res_list);
2200	return res;
2201	error:
2202	isl_ast_expr_list_free(list: res_list);
2203	return NULL;
2204	}
2205
2206	/* Is the domain of the current entry of "data", which is assumed
2207	* to contain a single subpiece, a subset of "set"?
2208	*/
2209	static isl_bool single_is_subset(struct isl_from_pw_aff_data *data,
2210	__isl_keep isl_set *set)
2211	{
2212	isl_bool subset;
2213	isl_set *set_n;
2214
2215	set_n = isl_set_list_get_set(list: data->p[data->n].set_list, index: 0);
2216	subset = isl_set_is_subset(set1: set_n, set2: set);
2217	isl_set_free(set: set_n);
2218
2219	return subset;
2220	}
2221
2222	/* Is "aff" a rational expression, i.e., does it have a denominator
2223	* different from one?
2224	*/
2225	static isl_bool aff_is_rational(__isl_keep isl_aff *aff)
2226	{
2227	isl_bool rational;
2228	isl_val *den;
2229
2230	den = isl_aff_get_denominator_val(aff);
2231	rational = isl_bool_not(b: isl_val_is_one(v: den));
2232	isl_val_free(v: den);
2233
2234	return rational;
2235	}
2236
2237	/* Does "list" consist of a single rational affine expression?
2238	*/
2239	static isl_bool is_single_rational_aff(__isl_keep isl_aff_list *list)
2240	{
2241	isl_size n;
2242	isl_bool rational;
2243	isl_aff *aff;
2244
2245	n = isl_aff_list_n_aff(list);
2246	if (n < 0)
2247	return isl_bool_error;
2248	if (n != 1)
2249	return isl_bool_false;
2250	aff = isl_aff_list_get_aff(list, index: 0);
2251	rational = aff_is_rational(aff);
2252	isl_aff_free(aff);
2253
2254	return rational;
2255	}
2256
2257	/* Can the list of subpieces in the last piece of "data" be extended with
2258	* "set" and "aff" based on "test"?
2259	* In particular, is it the case for each entry (set_i, aff_i) that
2260	*
2261	* test(aff, aff_i) holds on set_i, and
2262	* test(aff_i, aff) holds on set?
2263	*
2264	* "test" returns the set of elements where the tests holds, meaning
2265	* that test(aff_i, aff) holds on set if set is a subset of test(aff_i, aff).
2266	*
2267	* This function is used to detect min/max expressions.
2268	* If the ast_build_detect_min_max option is turned off, then
2269	* do not even try and perform any detection and return false instead.
2270	*
2271	* Rational affine expressions are not considered for min/max expressions
2272	* since the combined expression will be defined on the union of the domains,
2273	* while a rational expression may only yield integer values
2274	* on its own definition domain.
2275	*/
2276	static isl_bool extends(struct isl_from_pw_aff_data *data,
2277	__isl_keep isl_set *set, __isl_keep isl_aff *aff,
2278	__isl_give isl_basic_set *(*test)(__isl_take isl_aff *aff1,
2279	__isl_take isl_aff *aff2))
2280	{
2281	int i;
2282	isl_size n;
2283	isl_bool is_rational;
2284	isl_ctx *ctx;
2285	isl_set *dom;
2286
2287	is_rational = aff_is_rational(aff);
2288	if (is_rational >= 0 && !is_rational)
2289	is_rational = is_single_rational_aff(list: data->p[data->n].aff_list);
2290	if (is_rational < 0 || is_rational)
2291	return isl_bool_not(b: is_rational);
2292
2293	ctx = isl_ast_build_get_ctx(build: data->build);
2294	if (!isl_options_get_ast_build_detect_min_max(ctx))
2295	return isl_bool_false;
2296
2297	n = isl_set_list_n_set(list: data->p[data->n].set_list);
2298	if (n < 0)
2299	return isl_bool_error;
2300
2301	dom = isl_ast_build_get_domain(build: data->build);
2302	set = isl_set_intersect(set1: dom, set2: isl_set_copy(set));
2303
2304	for (i = 0; i < n ; ++i) {
2305	isl_aff *aff_i;
2306	isl_set *valid;
2307	isl_set *dom, *required;
2308	isl_bool is_valid;
2309
2310	aff_i = isl_aff_list_get_aff(list: data->p[data->n].aff_list, index: i);
2311	valid = isl_set_from_basic_set(bset: test(isl_aff_copy(aff), aff_i));
2312	required = isl_set_list_get_set(list: data->p[data->n].set_list, index: i);
2313	dom = isl_ast_build_get_domain(build: data->build);
2314	required = isl_set_intersect(set1: dom, set2: required);
2315	is_valid = isl_set_is_subset(set1: required, set2: valid);
2316	isl_set_free(set: required);
2317	isl_set_free(set: valid);
2318	if (is_valid < 0 || !is_valid) {
2319	isl_set_free(set);
2320	return is_valid;
2321	}
2322
2323	aff_i = isl_aff_list_get_aff(list: data->p[data->n].aff_list, index: i);
2324	valid = isl_set_from_basic_set(bset: test(aff_i, isl_aff_copy(aff)));
2325	is_valid = isl_set_is_subset(set1: set, set2: valid);
2326	isl_set_free(set: valid);
2327	if (is_valid < 0 || !is_valid) {
2328	isl_set_free(set);
2329	return is_valid;
2330	}
2331	}
2332
2333	isl_set_free(set);
2334	return isl_bool_true;
2335	}
2336
2337	/* Can the list of pieces in "data" be extended with "set" and "aff"
2338	* to form/preserve a minimum expression?
2339	* In particular, is it the case for each entry (set_i, aff_i) that
2340	*
2341	* aff >= aff_i on set_i, and
2342	* aff_i >= aff on set?
2343	*/
2344	static isl_bool extends_min(struct isl_from_pw_aff_data *data,
2345	__isl_keep isl_set *set, __isl_keep isl_aff *aff)
2346	{
2347	return extends(data, set, aff, test: &isl_aff_ge_basic_set);
2348	}
2349
2350	/* Can the list of pieces in "data" be extended with "set" and "aff"
2351	* to form/preserve a maximum expression?
2352	* In particular, is it the case for each entry (set_i, aff_i) that
2353	*
2354	* aff <= aff_i on set_i, and
2355	* aff_i <= aff on set?
2356	*/
2357	static isl_bool extends_max(struct isl_from_pw_aff_data *data,
2358	__isl_keep isl_set *set, __isl_keep isl_aff *aff)
2359	{
2360	return extends(data, set, aff, test: &isl_aff_le_basic_set);
2361	}
2362
2363	/* This function is called during the construction of an isl_ast_expr
2364	* that evaluates an isl_pw_aff.
2365	* If the last piece of "data" contains a single subpiece and
2366	* if its affine function is equal to "aff" on a part of the domain
2367	* that includes either "set" or the domain of that single subpiece,
2368	* then extend the domain of that single subpiece with "set".
2369	* If it was the original domain of the single subpiece where
2370	* the two affine functions are equal, then also replace
2371	* the affine function of the single subpiece by "aff".
2372	* If the last piece of "data" contains either a single subpiece
2373	* or a minimum, then check if this minimum expression can be extended
2374	* with (set, aff).
2375	* If so, extend the sequence and return.
2376	* Perform the same operation for maximum expressions.
2377	* If no such extension can be performed, then move to the next piece
2378	* in "data" (if the current piece contains any data), and then store
2379	* the current subpiece in the current piece of "data" for later handling.
2380	*/
2381	static isl_stat ast_expr_from_pw_aff(__isl_take isl_set *set,
2382	__isl_take isl_aff *aff, void *user)
2383	{
2384	struct isl_from_pw_aff_data *data = user;
2385	isl_bool test;
2386	enum isl_from_pw_aff_state state;
2387
2388	state = data->p[data->n].state;
2389	if (state == isl_state_single) {
2390	isl_aff *aff0;
2391	isl_set *eq;
2392	isl_bool subset1, subset2 = isl_bool_false;
2393	aff0 = isl_aff_list_get_aff(list: data->p[data->n].aff_list, index: 0);
2394	eq = isl_aff_eq_set(aff1: isl_aff_copy(aff), aff2: aff0);
2395	subset1 = isl_set_is_subset(set1: set, set2: eq);
2396	if (subset1 >= 0 && !subset1)
2397	subset2 = single_is_subset(data, set: eq);
2398	isl_set_free(set: eq);
2399	if (subset1 < 0 || subset2 < 0)
2400	goto error;
2401	if (subset1)
2402	return extend_domain(data, set, aff, replace: 0);
2403	if (subset2)
2404	return extend_domain(data, set, aff, replace: 1);
2405	}
2406	if (state == isl_state_single || state == isl_state_min) {
2407	test = extends_min(data, set, aff);
2408	if (test < 0)
2409	goto error;
2410	if (test)
2411	return extend_min(data, set, aff);
2412	}
2413	if (state == isl_state_single || state == isl_state_max) {
2414	test = extends_max(data, set, aff);
2415	if (test < 0)
2416	goto error;
2417	if (test)
2418	return extend_max(data, set, aff);
2419	}
2420	if (state != isl_state_none)
2421	data->n++;
2422	set_single(data, set, aff);
2423
2424	return isl_stat_ok;
2425	error:
2426	isl_set_free(set);
2427	isl_aff_free(aff);
2428	return isl_stat_error;
2429	}
2430
2431	/* Construct an isl_ast_expr that evaluates "pa".
2432	* The result is simplified in terms of build->domain.
2433	*
2434	* The domain of "pa" lives in the internal schedule space.
2435	*/
2436	__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff_internal(
2437	__isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2438	{
2439	struct isl_from_pw_aff_data data = { NULL };
2440	isl_ast_expr *res = NULL;
2441
2442	pa = isl_ast_build_compute_gist_pw_aff(build, pa);
2443	pa = isl_pw_aff_coalesce(pa);
2444	if (!pa)
2445	return NULL;
2446
2447	if (isl_from_pw_aff_data_init(data: &data, build, pa) < 0)
2448	goto error;
2449	set_none(&data);
2450
2451	if (isl_pw_aff_foreach_piece(pwaff: pa, fn: &ast_expr_from_pw_aff, user: &data) >= 0)
2452	res = build_pieces(data: &data);
2453
2454	isl_pw_aff_free(pwaff: pa);
2455	isl_from_pw_aff_data_clear(data: &data);
2456	return res;
2457	error:
2458	isl_pw_aff_free(pwaff: pa);
2459	isl_from_pw_aff_data_clear(data: &data);
2460	return NULL;
2461	}
2462
2463	/* Construct an isl_ast_expr that evaluates "pa".
2464	* The result is simplified in terms of build->domain.
2465	*
2466	* The domain of "pa" lives in the external schedule space.
2467	*/
2468	__isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
2469	__isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2470	{
2471	isl_ast_expr *expr;
2472	isl_bool needs_map;
2473
2474	needs_map = isl_ast_build_need_schedule_map(build);
2475	if (needs_map < 0) {
2476	pa = isl_pw_aff_free(pwaff: pa);
2477	} else if (needs_map) {
2478	isl_multi_aff *ma;
2479	ma = isl_ast_build_get_schedule_map_multi_aff(build);
2480	pa = isl_pw_aff_pullback_multi_aff(pa, ma);
2481	}
2482	expr = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2483	return expr;
2484	}
2485
2486	/* Set the ids of the input dimensions of "mpa" to the iterator ids
2487	* of "build".
2488	*
2489	* The domain of "mpa" is assumed to live in the internal schedule domain.
2490	*/
2491	static __isl_give isl_multi_pw_aff *set_iterator_names(
2492	__isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2493	{
2494	int i;
2495	isl_size n;
2496
2497	n = isl_multi_pw_aff_dim(multi: mpa, type: isl_dim_in);
2498	if (n < 0)
2499	return isl_multi_pw_aff_free(multi: mpa);
2500	for (i = 0; i < n; ++i) {
2501	isl_id *id;
2502
2503	id = isl_ast_build_get_iterator_id(build, pos: i);
2504	mpa = isl_multi_pw_aff_set_dim_id(multi: mpa, type: isl_dim_in, pos: i, id);
2505	}
2506
2507	return mpa;
2508	}
2509
2510	/* Construct an isl_ast_expr of type "type" with as first argument "arg0" and
2511	* the remaining arguments derived from "mpa".
2512	* That is, construct a call or access expression that calls/accesses "arg0"
2513	* with arguments/indices specified by "mpa".
2514	*/
2515	static __isl_give isl_ast_expr *isl_ast_build_with_arguments(
2516	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2517	__isl_take isl_ast_expr *arg0, __isl_take isl_multi_pw_aff *mpa)
2518	{
2519	int i;
2520	isl_size n;
2521	isl_ctx *ctx;
2522	isl_ast_expr *expr;
2523
2524	ctx = isl_ast_build_get_ctx(build);
2525
2526	n = isl_multi_pw_aff_dim(multi: mpa, type: isl_dim_out);
2527	expr = n >= 0 ? isl_ast_expr_alloc_op(ctx, op: type, n_arg: 1 + n) : NULL;
2528	expr = isl_ast_expr_op_add_arg(expr, arg: arg0);
2529	for (i = 0; i < n; ++i) {
2530	isl_pw_aff *pa;
2531	isl_ast_expr *arg;
2532
2533	pa = isl_multi_pw_aff_get_pw_aff(multi: mpa, pos: i);
2534	arg = isl_ast_build_expr_from_pw_aff_internal(build, pa);
2535	expr = isl_ast_expr_op_add_arg(expr, arg);
2536	}
2537
2538	isl_multi_pw_aff_free(multi: mpa);
2539	return expr;
2540	}
2541
2542	static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
2543	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2544	__isl_take isl_multi_pw_aff *mpa);
2545
2546	/* Construct an isl_ast_expr that accesses the member specified by "mpa".
2547	* The range of "mpa" is assumed to be wrapped relation.
2548	* The domain of this wrapped relation specifies the structure being
2549	* accessed, while the range of this wrapped relation spacifies the
2550	* member of the structure being accessed.
2551	*
2552	* The domain of "mpa" is assumed to live in the internal schedule domain.
2553	*/
2554	static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_member(
2555	__isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2556	{
2557	isl_id *id;
2558	isl_multi_pw_aff *domain;
2559	isl_ast_expr *domain_expr, *expr;
2560	enum isl_ast_expr_op_type type = isl_ast_expr_op_access;
2561
2562	domain = isl_multi_pw_aff_copy(multi: mpa);
2563	domain = isl_multi_pw_aff_range_factor_domain(multi: domain);
2564	domain_expr = isl_ast_build_from_multi_pw_aff_internal(build,
2565	type, mpa: domain);
2566	mpa = isl_multi_pw_aff_range_factor_range(multi: mpa);
2567	if (!isl_multi_pw_aff_has_tuple_id(multi: mpa, type: isl_dim_out))
2568	isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
2569	"missing field name", goto error);
2570	id = isl_multi_pw_aff_get_tuple_id(multi: mpa, type: isl_dim_out);
2571	expr = isl_ast_expr_from_id(id);
2572	expr = isl_ast_expr_alloc_binary(type: isl_ast_expr_op_member,
2573	expr1: domain_expr, expr2: expr);
2574	return isl_ast_build_with_arguments(build, type, arg0: expr, mpa);
2575	error:
2576	isl_multi_pw_aff_free(multi: mpa);
2577	return NULL;
2578	}
2579
2580	/* Construct an isl_ast_expr of type "type" that calls or accesses
2581	* the element specified by "mpa".
2582	* The first argument is obtained from the output tuple name.
2583	* The remaining arguments are given by the piecewise affine expressions.
2584	*
2585	* If the range of "mpa" is a mapped relation, then we assume it
2586	* represents an access to a member of a structure.
2587	*
2588	* The domain of "mpa" is assumed to live in the internal schedule domain.
2589	*/
2590	static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff_internal(
2591	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2592	__isl_take isl_multi_pw_aff *mpa)
2593	{
2594	isl_ctx *ctx;
2595	isl_id *id;
2596	isl_ast_expr *expr;
2597
2598	if (!mpa)
2599	goto error;
2600
2601	if (type == isl_ast_expr_op_access &&
2602	isl_multi_pw_aff_range_is_wrapping(multi: mpa))
2603	return isl_ast_build_from_multi_pw_aff_member(build, mpa);
2604
2605	mpa = set_iterator_names(build, mpa);
2606	if (!build || !mpa)
2607	goto error;
2608
2609	ctx = isl_ast_build_get_ctx(build);
2610
2611	if (isl_multi_pw_aff_has_tuple_id(multi: mpa, type: isl_dim_out))
2612	id = isl_multi_pw_aff_get_tuple_id(multi: mpa, type: isl_dim_out);
2613	else
2614	id = isl_id_alloc(ctx, name: "", NULL);
2615
2616	expr = isl_ast_expr_from_id(id);
2617	return isl_ast_build_with_arguments(build, type, arg0: expr, mpa);
2618	error:
2619	isl_multi_pw_aff_free(multi: mpa);
2620	return NULL;
2621	}
2622
2623	/* Construct an isl_ast_expr of type "type" that calls or accesses
2624	* the element specified by "pma".
2625	* The first argument is obtained from the output tuple name.
2626	* The remaining arguments are given by the piecewise affine expressions.
2627	*
2628	* The domain of "pma" is assumed to live in the internal schedule domain.
2629	*/
2630	static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff_internal(
2631	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2632	__isl_take isl_pw_multi_aff *pma)
2633	{
2634	isl_multi_pw_aff *mpa;
2635
2636	mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2637	return isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2638	}
2639
2640	/* Construct an isl_ast_expr of type "type" that calls or accesses
2641	* the element specified by "mpa".
2642	* The first argument is obtained from the output tuple name.
2643	* The remaining arguments are given by the piecewise affine expressions.
2644	*
2645	* The domain of "mpa" is assumed to live in the external schedule domain.
2646	*/
2647	static __isl_give isl_ast_expr *isl_ast_build_from_multi_pw_aff(
2648	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2649	__isl_take isl_multi_pw_aff *mpa)
2650	{
2651	isl_bool is_domain;
2652	isl_bool needs_map;
2653	isl_ast_expr *expr;
2654	isl_space *space_build, *space_mpa;
2655
2656	space_build = isl_ast_build_get_space(build, internal: 0);
2657	space_mpa = isl_multi_pw_aff_get_space(multi: mpa);
2658	is_domain = isl_space_tuple_is_equal(space1: space_build, type1: isl_dim_set,
2659	space2: space_mpa, type2: isl_dim_in);
2660	isl_space_free(space: space_build);
2661	isl_space_free(space: space_mpa);
2662	if (is_domain < 0)
2663	goto error;
2664	if (!is_domain)
2665	isl_die(isl_ast_build_get_ctx(build), isl_error_invalid,
2666	"spaces don't match", goto error);
2667
2668	needs_map = isl_ast_build_need_schedule_map(build);
2669	if (needs_map < 0)
2670	goto error;
2671	if (needs_map) {
2672	isl_multi_aff *ma;
2673	ma = isl_ast_build_get_schedule_map_multi_aff(build);
2674	mpa = isl_multi_pw_aff_pullback_multi_aff(mpa, ma);
2675	}
2676
2677	expr = isl_ast_build_from_multi_pw_aff_internal(build, type, mpa);
2678	return expr;
2679	error:
2680	isl_multi_pw_aff_free(multi: mpa);
2681	return NULL;
2682	}
2683
2684	/* Construct an isl_ast_expr that calls the domain element specified by "mpa".
2685	* The name of the function is obtained from the output tuple name.
2686	* The arguments are given by the piecewise affine expressions.
2687	*
2688	* The domain of "mpa" is assumed to live in the external schedule domain.
2689	*/
2690	__isl_give isl_ast_expr *isl_ast_build_call_from_multi_pw_aff(
2691	__isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2692	{
2693	return isl_ast_build_from_multi_pw_aff(build,
2694	type: isl_ast_expr_op_call, mpa);
2695	}
2696
2697	/* Construct an isl_ast_expr that accesses the array element specified by "mpa".
2698	* The name of the array is obtained from the output tuple name.
2699	* The index expressions are given by the piecewise affine expressions.
2700	*
2701	* The domain of "mpa" is assumed to live in the external schedule domain.
2702	*/
2703	__isl_give isl_ast_expr *isl_ast_build_access_from_multi_pw_aff(
2704	__isl_keep isl_ast_build *build, __isl_take isl_multi_pw_aff *mpa)
2705	{
2706	return isl_ast_build_from_multi_pw_aff(build,
2707	type: isl_ast_expr_op_access, mpa);
2708	}
2709
2710	/* Construct an isl_ast_expr of type "type" that calls or accesses
2711	* the element specified by "pma".
2712	* The first argument is obtained from the output tuple name.
2713	* The remaining arguments are given by the piecewise affine expressions.
2714	*
2715	* The domain of "pma" is assumed to live in the external schedule domain.
2716	*/
2717	static __isl_give isl_ast_expr *isl_ast_build_from_pw_multi_aff(
2718	__isl_keep isl_ast_build *build, enum isl_ast_expr_op_type type,
2719	__isl_take isl_pw_multi_aff *pma)
2720	{
2721	isl_multi_pw_aff *mpa;
2722
2723	mpa = isl_multi_pw_aff_from_pw_multi_aff(pma);
2724	return isl_ast_build_from_multi_pw_aff(build, type, mpa);
2725	}
2726
2727	/* Construct an isl_ast_expr that calls the domain element specified by "pma".
2728	* The name of the function is obtained from the output tuple name.
2729	* The arguments are given by the piecewise affine expressions.
2730	*
2731	* The domain of "pma" is assumed to live in the external schedule domain.
2732	*/
2733	__isl_give isl_ast_expr *isl_ast_build_call_from_pw_multi_aff(
2734	__isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2735	{
2736	return isl_ast_build_from_pw_multi_aff(build,
2737	type: isl_ast_expr_op_call, pma);
2738	}
2739
2740	/* Construct an isl_ast_expr that accesses the array element specified by "pma".
2741	* The name of the array is obtained from the output tuple name.
2742	* The index expressions are given by the piecewise affine expressions.
2743	*
2744	* The domain of "pma" is assumed to live in the external schedule domain.
2745	*/
2746	__isl_give isl_ast_expr *isl_ast_build_access_from_pw_multi_aff(
2747	__isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2748	{
2749	return isl_ast_build_from_pw_multi_aff(build,
2750	type: isl_ast_expr_op_access, pma);
2751	}
2752
2753	/* Construct an isl_ast_expr that calls the domain element
2754	* specified by "executed".
2755	*
2756	* "executed" is assumed to be single-valued, with a domain that lives
2757	* in the internal schedule space.
2758	*/
2759	__isl_give isl_ast_node *isl_ast_build_call_from_executed(
2760	__isl_keep isl_ast_build *build, __isl_take isl_map *executed)
2761	{
2762	isl_pw_multi_aff *iteration;
2763	isl_ast_expr *expr;
2764
2765	iteration = isl_pw_multi_aff_from_map(map: executed);
2766	iteration = isl_ast_build_compute_gist_pw_multi_aff(build, pma: iteration);
2767	iteration = isl_pw_multi_aff_intersect_domain(pma: iteration,
2768	set: isl_ast_build_get_domain(build));
2769	expr = isl_ast_build_from_pw_multi_aff_internal(build,
2770	type: isl_ast_expr_op_call, pma: iteration);
2771	return isl_ast_node_alloc_user(expr);
2772	}
2773