1/* 2 * Copyright 2010 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, 8 * INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, 9 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 10 * and Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France 11 */ 12 13/* Function for computing the lexicographic optimum of a map 14 * in the form of either an isl_map or an isl_pw_multi_aff. 15 */ 16 17#define xSF(TYPE,SUFFIX) TYPE ## SUFFIX 18#define SF(TYPE,SUFFIX) xSF(TYPE,SUFFIX) 19 20/* Given a basic map "bmap", compute the lexicographically minimal 21 * (or maximal) image element for each domain element in dom. 22 * Set *empty to those elements in dom that do not have an image element. 23 * 24 * We first make sure the basic sets in dom are disjoint and then 25 * simply collect the results over each of the basic sets separately. 26 * We could probably improve the efficiency a bit by moving the union 27 * domain down into the parametric integer programming. 28 */ 29static __isl_give TYPE *SF(basic_map_partial_lexopt,SUFFIX)( 30 __isl_take isl_basic_map *bmap, __isl_take isl_set *dom, 31 __isl_give isl_set **empty, int max) 32{ 33 int i; 34 TYPE *res; 35 36 dom = isl_set_make_disjoint(dom); 37 if (!dom) 38 goto error; 39 40 if (isl_set_plain_is_empty(dom)) { 41 isl_space *space = isl_basic_map_get_space(bmap); 42 if (empty) 43 *empty = dom; 44 else 45 isl_set_free(dom); 46 isl_basic_map_free(bmap); 47 return EMPTY(space); 48 } 49 50 res = SF(isl_basic_map_partial_lexopt,SUFFIX)(isl_basic_map_copy(bmap), 51 isl_basic_set_copy(dom->p[0]), empty, max); 52 53 for (i = 1; i < dom->n; ++i) { 54 TYPE *res_i; 55 isl_set *empty_i; 56 57 res_i = SF(isl_basic_map_partial_lexopt,SUFFIX)( 58 isl_basic_map_copy(bmap), 59 isl_basic_set_copy(dom->p[i]), &empty_i, max); 60 61 res = ADD(res, res_i); 62 *empty = isl_set_union_disjoint(*empty, empty_i); 63 } 64 65 isl_set_free(dom); 66 isl_basic_map_free(bmap); 67 return res; 68error: 69 *empty = NULL; 70 isl_set_free(dom); 71 isl_basic_map_free(bmap); 72 return NULL; 73} 74 75static __isl_give TYPE *SF(isl_map_partial_lexopt_aligned,SUFFIX)( 76 __isl_take isl_map *map, __isl_take isl_set *dom, 77 __isl_give isl_set **empty, int max); 78 79/* Given a map "map", compute the lexicographically minimal 80 * (or maximal) image element for each domain element in dom. 81 * Set *empty to those elements in dom that do not have an image element. 82 * 83 * Align parameters if needed and then call isl_map_partial_lexopt_aligned. 84 */ 85static __isl_give TYPE *SF(isl_map_partial_lexopt,SUFFIX)( 86 __isl_take isl_map *map, __isl_take isl_set *dom, 87 __isl_give isl_set **empty, int max) 88{ 89 if (!map || !dom) 90 goto error; 91 if (isl_space_match(map->dim, isl_dim_param, dom->dim, isl_dim_param)) 92 return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, 93 empty, max); 94 if (!isl_space_has_named_params(map->dim) || 95 !isl_space_has_named_params(dom->dim)) 96 isl_die(map->ctx, isl_error_invalid, 97 "unaligned unnamed parameters", goto error); 98 map = isl_map_align_params(map, isl_map_get_space(dom)); 99 dom = isl_map_align_params(dom, isl_map_get_space(map)); 100 return SF(isl_map_partial_lexopt_aligned,SUFFIX)(map, dom, empty, max); 101error: 102 if (empty) 103 *empty = NULL; 104 isl_set_free(dom); 105 isl_map_free(map); 106 return NULL; 107} 108 109__isl_give TYPE *SF(isl_map_lexopt,SUFFIX)(__isl_take isl_map *map, int max) 110{ 111 isl_set *dom = NULL; 112 isl_space *dom_space; 113 114 if (!map) 115 goto error; 116 dom_space = isl_space_domain(isl_space_copy(map->dim)); 117 dom = isl_set_universe(dom_space); 118 return SF(isl_map_partial_lexopt,SUFFIX)(map, dom, NULL, max); 119error: 120 isl_map_free(map); 121 return NULL; 122} 123 124__isl_give TYPE *SF(isl_map_lexmin,SUFFIX)(__isl_take isl_map *map) 125{ 126 return SF(isl_map_lexopt,SUFFIX)(map, 0); 127} 128 129__isl_give TYPE *SF(isl_map_lexmax,SUFFIX)(__isl_take isl_map *map) 130{ 131 return SF(isl_map_lexopt,SUFFIX)(map, 1); 132} 133 134__isl_give TYPE *SF(isl_set_lexmin,SUFFIX)(__isl_take isl_set *set) 135{ 136 return SF(isl_map_lexmin,SUFFIX)(set); 137} 138 139__isl_give TYPE *SF(isl_set_lexmax,SUFFIX)(__isl_take isl_set *set) 140{ 141 return SF(isl_map_lexmax,SUFFIX)(set); 142} 143