isl_pw_union_opt.c

   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 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         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 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         if (!pw)
  33                 return NULL;
  34         ctx = FN(PW,get_ctx)(pw);
  35         list = isl_set_list_alloc(ctx, pw->n);
  36         for (i = 0; i < pw->n; ++i)
  37                 list = isl_set_list_add(list, isl_set_copy(pw->p[i].set));
  38
  39         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 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         set_better = isl_set_intersect(isl_set_copy(set), isl_set_copy(better));
  52         set_out = isl_set_subtract(isl_set_subtract(set, better), out);
  53
  54         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 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         set_worse = isl_set_subtract(isl_set_copy(set), isl_set_copy(better));
  67         set_out = isl_set_subtract(isl_set_intersect(set, better), out);
  68
  69         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 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         if (!pw1 || !pw2)
  94                 goto error;
  95
  96         res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->n + pw2->n);
  97
  98         i = 0; j = 0;
  99         while (i < pw1->n || j < pw2->n) {
 100                 int cmp;
 101                 isl_set *set;
 102                 EL *el;
 103
 104                 if (i < pw1->n && j < pw2->n)
 105                         cmp = FN(EL,plain_cmp)(pw1->p[i].FIELD,
 106                                                 pw2->p[j].FIELD);
 107                 else
 108                         cmp = i < pw1->n ? -1 : 1;
 109
 110                 if (cmp < 0) {
 111                         set = isl_set_list_get_set(list1, i);
 112                         el = FN(EL,copy)(pw1->p[i].FIELD);
 113                         ++i;
 114                 } else if (cmp > 0) {
 115                         set = isl_set_list_get_set(list2, j);
 116                         el = FN(EL,copy)(pw2->p[j].FIELD);
 117                         ++j;
 118                 } else {
 119                         set = isl_set_union(isl_set_list_get_set(list1, i),
 120                                             isl_set_list_get_set(list2, j));
 121                         el = FN(EL,copy)(pw1->p[i].FIELD);
 122                         ++i;
 123                         ++j;
 124                 }
 125                 res = FN(PW,add_piece)(res, set, el);
 126         }
 127
 128         isl_set_list_free(list1);
 129         isl_set_list_free(list2);
 130         FN(PW,free)(pw1);
 131         FN(PW,free)(pw2);
 132         return res;
 133 error:
 134         isl_set_list_free(list1);
 135         isl_set_list_free(list2);
 136         FN(PW,free)(pw1);
 137         FN(PW,free)(pw2);
 138         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 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         PW *res = NULL;
 188         isl_ctx *ctx;
 189         isl_set *set = NULL;
 190         isl_set_list *list1 = NULL, *list2 = NULL;
 191
 192         if (!pw1 || !pw2)
 193                 goto error;
 194
 195         ctx = isl_space_get_ctx(pw1->dim);
 196         if (!isl_space_is_equal(pw1->dim, pw2->dim))
 197                 isl_die(ctx, isl_error_invalid,
 198                         "arguments should live in the same space", goto error);
 199
 200         if (FN(PW,is_empty)(pw1)) {
 201                 FN(PW,free)(pw1);
 202                 return pw2;
 203         }
 204
 205         if (FN(PW,is_empty)(pw2)) {
 206                 FN(PW,free)(pw2);
 207                 return pw1;
 208         }
 209
 210         pw1 = FN(PW,sort)(pw1);
 211         pw2 = FN(PW,sort)(pw2);
 212         if (!pw1 || !pw2)
 213                 goto error;
 214
 215         list1 = FN(PW,extract_domains)(pw1);
 216         list2 = FN(PW,extract_domains)(pw2);
 217
 218         for (i = 0; i < pw1->n; ++i) {
 219                 for (j = 0; j < pw2->n; ++j) {
 220                         isl_bool disjoint;
 221                         isl_set *better, *set_i, *set_j;
 222
 223                         disjoint = isl_set_is_disjoint(pw1->p[i].set,
 224                                                         pw2->p[j].set);
 225                         if (disjoint < 0)
 226                                 goto error;
 227                         if (disjoint)
 228                                 continue;
 229                         better = FN(PW,better)(pw2->p[j].FIELD,
 230                                                 pw1->p[i].FIELD, cmp);
 231                         set_i = isl_set_list_get_set(list1, i);
 232                         set_j = isl_set_copy(pw2->p[j].set);
 233                         set_i = FN(PW,worse_or_out)(set_i,
 234                                                 isl_set_copy(better), set_j);
 235                         list1 = isl_set_list_set_set(list1, i, set_i);
 236                         set_i = isl_set_copy(pw1->p[i].set);
 237                         set_j = isl_set_list_get_set(list2, j);
 238                         set_j = FN(PW,better_or_out)(set_j, better, set_i);
 239                         list2 = isl_set_list_set_set(list2, j, set_j);
 240                 }
 241         }
 242
 243         res = FN(PW,merge)(pw1, pw2, list1, list2);
 244
 245         return res;
 246 error:
 247         isl_set_list_free(list1);
 248         isl_set_list_free(list2);
 249         FN(PW,free)(pw1);
 250         FN(PW,free)(pw2);
 251         isl_set_free(set);
 252         return FN(PW,free)(res);
 253 }