2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2014 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
42 /* A pet_context represents the context in which a pet_expr
43 * in converted to an affine expression.
45 * "domain" prescribes the domain of the affine expressions.
47 * "assignments" maps variable names to their currently known values.
48 * The domains of the values are equal to the space of "domain".
49 * If a variable has been assigned an unknown value (possibly because
50 * it may be assigned a different expression in each iteration) or a value
51 * that is not an affine expression, then the corresponding isl_pw_aff
54 * If "allow_nested" is set, then the affine expression created
55 * in this context may involve new parameters that encode a pet_expr.
61 isl_id_to_pw_aff
*assignments
;
65 /* Create a pet_context with the given domain, assignments,
66 * and value for allow_nested.
68 static __isl_give pet_context
*context_alloc(__isl_take isl_set
*domain
,
69 __isl_take isl_id_to_pw_aff
*assignments
, int allow_nested
)
73 if (!domain
|| !assignments
)
76 pc
= isl_calloc_type(isl_set_get_ctx(domain
), struct pet_context
);
82 pc
->assignments
= assignments
;
83 pc
->allow_nested
= allow_nested
;
88 isl_id_to_pw_aff_free(assignments
);
92 /* Create a pet_context with the given domain.
94 * Initially, there are no assigned values and parameters that
95 * encode a pet_expr are not allowed.
97 __isl_give pet_context
*pet_context_alloc(__isl_take isl_set
*domain
)
99 isl_id_to_pw_aff
*assignments
;
104 assignments
= isl_id_to_pw_aff_alloc(isl_set_get_ctx(domain
), 0);;
105 return context_alloc(domain
, assignments
, 0);
108 /* Return an independent duplicate of "pc".
110 static __isl_give pet_context
*pet_context_dup(__isl_keep pet_context
*pc
)
117 dup
= context_alloc(isl_set_copy(pc
->domain
),
118 isl_id_to_pw_aff_copy(pc
->assignments
),
124 /* Return a pet_context that is equal to "pc" and that has only one reference.
126 static __isl_give pet_context
*pet_context_cow(__isl_take pet_context
*pc
)
134 return pet_context_dup(pc
);
137 /* Return an extra reference to "pc".
139 __isl_give pet_context
*pet_context_copy(__isl_keep pet_context
*pc
)
148 /* Free a reference to "pc" and return NULL.
150 __isl_null pet_context
*pet_context_free(__isl_take pet_context
*pc
)
157 isl_set_free(pc
->domain
);
158 isl_id_to_pw_aff_free(pc
->assignments
);
163 /* Return the isl_ctx in which "pc" was created.
165 isl_ctx
*pet_context_get_ctx(__isl_keep pet_context
*pc
)
167 return pc
? isl_set_get_ctx(pc
->domain
) : NULL
;
170 /* Return the domain of "pc".
172 __isl_give isl_set
*pet_context_get_domain(__isl_keep pet_context
*pc
)
176 return isl_set_copy(pc
->domain
);
179 /* Return the domain space of "pc".
181 * The domain of "pc" may have constraints involving parameters
182 * that encode a pet_expr. These parameters are not relevant
183 * outside this domain. Furthermore, they need to be resolved
184 * from the final result, so we do not want to propagate them needlessly.
186 __isl_give isl_space
*pet_context_get_space(__isl_keep pet_context
*pc
)
193 space
= isl_set_get_space(pc
->domain
);
194 space
= pet_nested_remove_from_space(space
);
198 /* Return the dimension of the domain space of "pc".
200 unsigned pet_context_dim(__isl_keep pet_context
*pc
)
204 return isl_set_dim(pc
->domain
, isl_dim_set
);
207 /* Return the assignments of "pc".
209 __isl_give isl_id_to_pw_aff
*pet_context_get_assignments(
210 __isl_keep pet_context
*pc
)
214 return isl_id_to_pw_aff_copy(pc
->assignments
);
217 /* Is "id" assigned any value in "pc"?
219 int pet_context_is_assigned(__isl_keep pet_context
*pc
, __isl_keep isl_id
*id
)
223 return isl_id_to_pw_aff_has(pc
->assignments
, id
);
226 /* Return the value assigned to "id" in "pc".
228 __isl_give isl_pw_aff
*pet_context_get_value(__isl_keep pet_context
*pc
,
229 __isl_take isl_id
*id
)
234 return isl_id_to_pw_aff_get(pc
->assignments
, id
);
240 /* Assign the value "value" to "id" in "pc", replacing the previously
241 * assigned value, if any.
243 __isl_give pet_context
*pet_context_set_value(__isl_take pet_context
*pc
,
244 __isl_take isl_id
*id
, isl_pw_aff
*value
)
246 pc
= pet_context_cow(pc
);
249 pc
->assignments
= isl_id_to_pw_aff_set(pc
->assignments
, id
, value
);
250 if (!pc
->assignments
)
251 return pet_context_free(pc
);
255 isl_pw_aff_free(value
);
259 /* Remove any assignment to "id" in "pc".
261 __isl_give pet_context
*pet_context_clear_value(__isl_keep pet_context
*pc
,
262 __isl_take isl_id
*id
)
264 pc
= pet_context_cow(pc
);
267 pc
->assignments
= isl_id_to_pw_aff_drop(pc
->assignments
, id
);
268 if (!pc
->assignments
)
269 return pet_context_free(pc
);
276 /* Return a piecewise affine expression defined on the specified domain
277 * that represents NaN.
279 static __isl_give isl_pw_aff
*nan_on_domain(__isl_take isl_space
*space
)
281 return isl_pw_aff_nan_on_domain(isl_local_space_from_space(space
));
284 /* Assign the value NaN to "id" in "pc", marked it as having an unknown
287 __isl_give pet_context
*pet_context_mark_unknown(__isl_take pet_context
*pc
,
288 __isl_take isl_id
*id
)
292 pa
= nan_on_domain(pet_context_get_space(pc
));
293 pc
= pet_context_set_value(pc
, id
, pa
);
298 /* Are affine expressions created in this context allowed to involve
299 * parameters that encode a pet_expr?
301 int pet_context_allow_nesting(__isl_keep pet_context
*pc
)
305 return pc
->allow_nested
;
308 /* Allow affine expressions created in this context to involve
309 * parameters that encode a pet_expr based on the value of "allow_nested".
311 __isl_give pet_context
*pet_context_set_allow_nested(__isl_take pet_context
*pc
,
316 if (pc
->allow_nested
== allow_nested
)
318 pc
= pet_context_cow(pc
);
321 pc
->allow_nested
= allow_nested
;
325 /* If the access expression "expr" writes to a (non-virtual) scalar,
326 * then mark the scalar as having an unknown value in "pc".
328 static int clear_write(__isl_keep pet_expr
*expr
, void *user
)
331 pet_context
**pc
= (pet_context
**) user
;
333 if (!pet_expr_access_is_write(expr
))
335 if (!pet_expr_is_scalar_access(expr
))
338 id
= pet_expr_access_get_id(expr
);
339 if (isl_id_get_user(id
))
340 *pc
= pet_context_mark_unknown(*pc
, id
);
347 /* Look for any writes to scalar variables in "expr" and
348 * mark them as having an unknown value in "pc".
350 __isl_give pet_context
*pet_context_clear_writes_in_expr(
351 __isl_take pet_context
*pc
, __isl_keep pet_expr
*expr
)
353 if (pet_expr_foreach_access_expr(expr
, &clear_write
, &pc
) < 0)
354 pc
= pet_context_free(pc
);
359 /* Look for any writes to scalar variables in "tree" and
360 * mark them as having an unknown value in "pc".
362 __isl_give pet_context
*pet_context_clear_writes_in_tree(
363 __isl_take pet_context
*pc
, __isl_keep pet_tree
*tree
)
365 if (pet_tree_foreach_access_expr(tree
, &clear_write
, &pc
) < 0)
366 pc
= pet_context_free(pc
);
371 /* Given an access expression, check if it reads a scalar variable
372 * that has a known value in "pc".
373 * If so, then replace the access by an access to that value.
375 static __isl_give pet_expr
*access_plug_in_affine_read(
376 __isl_take pet_expr
*expr
, void *user
)
378 pet_context
*pc
= user
;
381 if (pet_expr_access_is_write(expr
))
383 if (!pet_expr_is_scalar_access(expr
))
386 pa
= pet_expr_extract_affine(expr
, pc
);
388 return pet_expr_free(expr
);
389 if (isl_pw_aff_involves_nan(pa
)) {
395 expr
= pet_expr_from_index(isl_multi_pw_aff_from_pw_aff(pa
));
400 /* Replace every read access in "expr" to a scalar variable
401 * that has a known value in "pc" by that known value.
403 static __isl_give pet_expr
*plug_in_affine_read(__isl_take pet_expr
*expr
,
404 __isl_keep pet_context
*pc
)
406 return pet_expr_map_access(expr
, &access_plug_in_affine_read
, pc
);
409 /* Evaluate "expr" in the context of "pc".
411 * In particular, plug in affine expressions for scalar reads and
412 * plug in the arguments of all access expressions in "expr".
414 __isl_give pet_expr
*pet_context_evaluate_expr(__isl_keep pet_context
*pc
,
415 __isl_take pet_expr
*expr
)
417 expr
= plug_in_affine_read(expr
, pc
);
418 return pet_expr_plug_in_args(expr
, pc
);
421 void pet_context_dump(__isl_keep pet_context
*pc
)
425 fprintf(stderr
, "domain: ");
426 isl_set_dump(pc
->domain
);
427 fprintf(stderr
, "assignments: ");
428 isl_id_to_pw_aff_dump(pc
->assignments
);
429 fprintf(stderr
, "nesting allowed: %d\n", pc
->allow_nested
);