Line data Source code
1 : /*
2 : * Copyright 2011 INRIA Saclay
3 : * Copyright 2012 Ecole Normale Superieure
4 : *
5 : * Use of this software is governed by the MIT license
6 : *
7 : * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 : * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 : * 91893 Orsay, France
10 : * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
11 : */
12 :
13 : #include <isl_pw_macro.h>
14 :
15 : /* Given a function "cmp" that returns the set of elements where
16 : * "el1" is "better" than "el2", return this set.
17 : */
18 0 : static __isl_give isl_set *FN(PW,better)(__isl_keep EL *el1, __isl_keep EL *el2,
19 : __isl_give isl_set *(*cmp)(__isl_take EL *el1, __isl_take EL *el2))
20 : {
21 0 : return cmp(FN(EL,copy)(el1), FN(EL,copy)(el2));
22 : }
23 :
24 : /* Return a list containing the domains of the pieces of "pw".
25 : */
26 0 : static __isl_give isl_set_list *FN(PW,extract_domains)(__isl_keep PW *pw)
27 : {
28 : int i;
29 : isl_ctx *ctx;
30 : isl_set_list *list;
31 :
32 0 : if (!pw)
33 0 : return NULL;
34 0 : ctx = FN(PW,get_ctx)(pw);
35 0 : list = isl_set_list_alloc(ctx, pw->n);
36 0 : for (i = 0; i < pw->n; ++i)
37 0 : list = isl_set_list_add(list, isl_set_copy(pw->p[i].set));
38 :
39 0 : return list;
40 : }
41 :
42 : /* Given sets B ("set"), C ("better") and A' ("out"), return
43 : *
44 : * (B \cap C) \cup ((B \setminus C) \setminus A')
45 : */
46 0 : static __isl_give isl_set *FN(PW,better_or_out)(__isl_take isl_set *set,
47 : __isl_take isl_set *better, __isl_take isl_set *out)
48 : {
49 : isl_set *set_better, *set_out;
50 :
51 0 : set_better = isl_set_intersect(isl_set_copy(set), isl_set_copy(better));
52 0 : set_out = isl_set_subtract(isl_set_subtract(set, better), out);
53 :
54 0 : return isl_set_union(set_better, set_out);
55 : }
56 :
57 : /* Given sets A ("set"), C ("better") and B' ("out"), return
58 : *
59 : * (A \setminus C) \cup ((A \cap C) \setminus B')
60 : */
61 0 : static __isl_give isl_set *FN(PW,worse_or_out)(__isl_take isl_set *set,
62 : __isl_take isl_set *better, __isl_take isl_set *out)
63 : {
64 : isl_set *set_worse, *set_out;
65 :
66 0 : set_worse = isl_set_subtract(isl_set_copy(set), isl_set_copy(better));
67 0 : set_out = isl_set_subtract(isl_set_intersect(set, better), out);
68 :
69 0 : return isl_set_union(set_worse, set_out);
70 : }
71 :
72 : /* Given two piecewise expressions "pw1" and "pw2", replace their domains
73 : * by the sets in "list1" and "list2" and combine the results into
74 : * a single piecewise expression.
75 : * The pieces of "pw1" and "pw2" are assumed to have been sorted
76 : * according to the function value expressions.
77 : * The pieces of the result are also sorted in this way.
78 : *
79 : * Run through the pieces of "pw1" and "pw2" in order until they
80 : * have both been exhausted, picking the piece from "pw1" or "pw2"
81 : * depending on which should come first, together with the corresponding
82 : * domain from "list1" or "list2". In cases where the next pieces
83 : * in both "pw1" and "pw2" have the same function value expression,
84 : * construct only a single piece in the result with as domain
85 : * the union of the domains in "list1" and "list2".
86 : */
87 0 : static __isl_give PW *FN(PW,merge)(__isl_take PW *pw1, __isl_take PW *pw2,
88 : __isl_take isl_set_list *list1, __isl_take isl_set_list *list2)
89 : {
90 : int i, j;
91 : PW *res;
92 :
93 0 : if (!pw1 || !pw2)
94 : goto error;
95 :
96 0 : res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->n + pw2->n);
97 :
98 0 : i = 0; j = 0;
99 0 : while (i < pw1->n || j < pw2->n) {
100 : int cmp;
101 : isl_set *set;
102 : EL *el;
103 :
104 0 : if (i < pw1->n && j < pw2->n)
105 0 : cmp = FN(EL,plain_cmp)(pw1->p[i].FIELD,
106 0 : pw2->p[j].FIELD);
107 : else
108 0 : cmp = i < pw1->n ? -1 : 1;
109 :
110 0 : if (cmp < 0) {
111 0 : set = isl_set_list_get_set(list1, i);
112 0 : el = FN(EL,copy)(pw1->p[i].FIELD);
113 0 : ++i;
114 0 : } else if (cmp > 0) {
115 0 : set = isl_set_list_get_set(list2, j);
116 0 : el = FN(EL,copy)(pw2->p[j].FIELD);
117 0 : ++j;
118 : } else {
119 0 : set = isl_set_union(isl_set_list_get_set(list1, i),
120 0 : isl_set_list_get_set(list2, j));
121 0 : el = FN(EL,copy)(pw1->p[i].FIELD);
122 0 : ++i;
123 0 : ++j;
124 : }
125 0 : res = FN(PW,add_piece)(res, set, el);
126 : }
127 :
128 0 : isl_set_list_free(list1);
129 0 : isl_set_list_free(list2);
130 0 : FN(PW,free)(pw1);
131 0 : FN(PW,free)(pw2);
132 0 : return res;
133 : error:
134 0 : isl_set_list_free(list1);
135 0 : isl_set_list_free(list2);
136 0 : FN(PW,free)(pw1);
137 0 : FN(PW,free)(pw2);
138 0 : return NULL;
139 : }
140 :
141 : /* Given a function "cmp" that returns the set of elements where
142 : * "el1" is "better" than "el2", return a piecewise
143 : * expression defined on the union of the definition domains
144 : * of "pw1" and "pw2" that maps to the "best" of "pw1" and
145 : * "pw2" on each cell. If only one of the two input functions
146 : * is defined on a given cell, then it is considered the best.
147 : *
148 : * Run through all pairs of pieces in "pw1" and "pw2".
149 : * If the domains of these pieces intersect, then the intersection
150 : * needs to be distributed over the two pieces based on "cmp".
151 : * Let C be the set where the piece from "pw2" is better (according to "cmp")
152 : * than the piece from "pw1". Let A be the domain of the piece from "pw1" and
153 : * B the domain of the piece from "pw2".
154 : *
155 : * The elements in C need to be removed from A, except for those parts
156 : * that lie outside of B. That is,
157 : *
158 : * A <- (A \setminus C) \cup ((A \cap C) \setminus B')
159 : *
160 : * Conversely, the elements in B need to be restricted to C, except
161 : * for those parts that lie outside of A. That is
162 : *
163 : * B <- (B \cap C) \cup ((B \setminus C) \setminus A')
164 : *
165 : * Since all pairs of pieces are considered, the domains are updated
166 : * several times. A and B refer to these updated domains
167 : * (kept track of in "list1" and "list2"), while A' and B' refer
168 : * to the original domains of the pieces. It is safe to use these
169 : * original domains because the difference between, say, A' and A is
170 : * the domains of pw2-pieces that have been removed before and
171 : * those domains are disjoint from B. A' is used instead of A
172 : * because the continued updating of A may result in this domain
173 : * getting broken up into more disjuncts.
174 : *
175 : * After the updated domains have been computed, the result is constructed
176 : * from "pw1", "pw2", "list1" and "list2". If there are any pieces
177 : * in "pw1" and "pw2" with the same function value expression, then
178 : * they are combined into a single piece in the result.
179 : * In order to be able to do this efficiently, the pieces of "pw1" and
180 : * "pw2" are first sorted according to their function value expressions.
181 : */
182 0 : static __isl_give PW *FN(PW,union_opt_cmp)(
183 : __isl_take PW *pw1, __isl_take PW *pw2,
184 : __isl_give isl_set *(*cmp)(__isl_take EL *el1, __isl_take EL *el2))
185 : {
186 : int i, j;
187 0 : PW *res = NULL;
188 : isl_ctx *ctx;
189 0 : isl_set *set = NULL;
190 0 : isl_set_list *list1 = NULL, *list2 = NULL;
191 :
192 0 : if (!pw1 || !pw2)
193 : goto error;
194 :
195 0 : ctx = isl_space_get_ctx(pw1->dim);
196 0 : if (!isl_space_is_equal(pw1->dim, pw2->dim))
197 0 : isl_die(ctx, isl_error_invalid,
198 : "arguments should live in the same space", goto error);
199 :
200 0 : if (FN(PW,is_empty)(pw1)) {
201 0 : FN(PW,free)(pw1);
202 0 : return pw2;
203 : }
204 :
205 0 : if (FN(PW,is_empty)(pw2)) {
206 0 : FN(PW,free)(pw2);
207 0 : return pw1;
208 : }
209 :
210 0 : pw1 = FN(PW,sort)(pw1);
211 0 : pw2 = FN(PW,sort)(pw2);
212 0 : if (!pw1 || !pw2)
213 : goto error;
214 :
215 0 : list1 = FN(PW,extract_domains)(pw1);
216 0 : list2 = FN(PW,extract_domains)(pw2);
217 :
218 0 : for (i = 0; i < pw1->n; ++i) {
219 0 : for (j = 0; j < pw2->n; ++j) {
220 : isl_bool disjoint;
221 : isl_set *better, *set_i, *set_j;
222 :
223 0 : disjoint = isl_set_is_disjoint(pw1->p[i].set,
224 0 : pw2->p[j].set);
225 0 : if (disjoint < 0)
226 0 : goto error;
227 0 : if (disjoint)
228 0 : continue;
229 0 : better = FN(PW,better)(pw2->p[j].FIELD,
230 0 : pw1->p[i].FIELD, cmp);
231 0 : set_i = isl_set_list_get_set(list1, i);
232 0 : set_j = isl_set_copy(pw2->p[j].set);
233 0 : set_i = FN(PW,worse_or_out)(set_i,
234 : isl_set_copy(better), set_j);
235 0 : list1 = isl_set_list_set_set(list1, i, set_i);
236 0 : set_i = isl_set_copy(pw1->p[i].set);
237 0 : set_j = isl_set_list_get_set(list2, j);
238 0 : set_j = FN(PW,better_or_out)(set_j, better, set_i);
239 0 : list2 = isl_set_list_set_set(list2, j, set_j);
240 : }
241 : }
242 :
243 0 : res = FN(PW,merge)(pw1, pw2, list1, list2);
244 :
245 0 : return res;
246 : error:
247 0 : isl_set_list_free(list1);
248 0 : isl_set_list_free(list2);
249 0 : FN(PW,free)(pw1);
250 0 : FN(PW,free)(pw2);
251 0 : isl_set_free(set);
252 0 : return FN(PW,free)(res);
253 : }
|
