aff.c

   1 /*
   2  * Copyright 2011      Leiden University. All rights reserved.
   3  * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  *    1. Redistributions of source code must retain the above copyright
  10  *       notice, this list of conditions and the following disclaimer.
  11  *
  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.
  16  *
  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.
  28  *
  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
  32  * Leiden University.
  33  */
  34
  35 #include "aff.h"
  36
  37 /* Return a function that projects "space" onto its first "n" dimensions,
  38  * with anonymous target space.
  39  */
  40 __isl_give isl_multi_aff *pet_prefix_projection(__isl_take isl_space *space,
  41         int n)
  42 {
  43         int dim;
  44
  45         dim = isl_space_dim(space, isl_dim_set);
  46         return isl_multi_aff_project_out_map(space, isl_dim_set, n, dim - n);
  47 }
  48
  49 /* If the isl_pw_aff on which isl_pw_aff_foreach_piece is called
  50  * has a constant expression on its only domain, then replace
  51  * the isl_val in *user by this constant.
  52  * The caller is assumed to have checked that this function will
  53  * be called exactly once.
  54  */
  55 static int extract_cst(__isl_take isl_set *set, __isl_take isl_aff *aff,
  56         void *user)
  57 {
  58         isl_val **inc = (isl_val **)user;
  59
  60         if (isl_aff_is_cst(aff)) {
  61                 isl_val_free(*inc);
  62                 *inc = isl_aff_get_constant_val(aff);
  63         }
  64
  65         isl_set_free(set);
  66         isl_aff_free(aff);
  67
  68         return 0;
  69 }
  70
  71 /* If "pa" represents a constant value over a single domain,
  72  * then return this constant.
  73  * Otherwise return NaN.
  74  */
  75 __isl_give isl_val *pet_extract_cst(__isl_keep isl_pw_aff *pa)
  76 {
  77         isl_val *v;
  78
  79         if (!pa)
  80                 return NULL;
  81         v = isl_val_nan(isl_pw_aff_get_ctx(pa));
  82         if (isl_pw_aff_n_piece(pa) != 1)
  83                 return v;
  84         if (isl_pw_aff_foreach_piece(pa, &extract_cst, &v) < 0)
  85                 v = isl_val_free(v);
  86         return v;
  87 }
  88
  89 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
  90  */
  91 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
  92         __isl_take isl_set *dom)
  93 {
  94         isl_pw_aff *pa;
  95         pa = isl_set_indicator_function(set);
  96         pa = isl_pw_aff_intersect_domain(pa, isl_set_coalesce(dom));
  97         return pa;
  98 }
  99
 100 /* Return "lhs && rhs", defined on the shared definition domain.
 101  */
 102 __isl_give isl_pw_aff *pet_and(__isl_take isl_pw_aff *lhs,
 103         __isl_take isl_pw_aff *rhs)
 104 {
 105         isl_set *cond;
 106         isl_set *dom;
 107
 108         dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
 109                                  isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
 110         cond = isl_set_intersect(isl_pw_aff_non_zero_set(lhs),
 111                                  isl_pw_aff_non_zero_set(rhs));
 112         return indicator_function(cond, dom);
 113 }
 114
 115 /* Return "!pa", defined on the domain of "pa".
 116  *
 117  * If "pa" involves any NaN, then return NaN.
 118  */
 119 __isl_give isl_pw_aff *pet_not(__isl_take isl_pw_aff *pa)
 120 {
 121         isl_set *cond, *dom;
 122
 123         if (!pa)
 124                 return NULL;
 125         if (isl_pw_aff_involves_nan(pa)) {
 126                 isl_space *space = isl_pw_aff_get_domain_space(pa);
 127                 isl_local_space *ls = isl_local_space_from_space(space);
 128                 isl_pw_aff_free(pa);
 129                 return isl_pw_aff_nan_on_domain(ls);
 130         }
 131
 132         dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
 133         cond = isl_pw_aff_zero_set(pa);
 134         pa = indicator_function(cond, dom);
 135
 136         return pa;
 137 }
 138
 139 /* Return "!!pa", i.e., a function that is equal to 1 when "pa"
 140  * is non-zero and equal to 0 when "pa" is equal to zero,
 141  * on the domain of "pa".
 142  *
 143  * If "pa" involves any NaN, then return NaN.
 144  */
 145 __isl_give isl_pw_aff *pet_to_bool(__isl_take isl_pw_aff *pa)
 146 {
 147         isl_set *cond, *dom;
 148
 149         if (!pa)
 150                 return NULL;
 151         if (isl_pw_aff_involves_nan(pa)) {
 152                 isl_space *space = isl_pw_aff_get_domain_space(pa);
 153                 isl_local_space *ls = isl_local_space_from_space(space);
 154                 isl_pw_aff_free(pa);
 155                 return isl_pw_aff_nan_on_domain(ls);
 156         }
 157
 158         dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
 159         cond = isl_pw_aff_non_zero_set(pa);
 160         pa = indicator_function(cond, dom);
 161
 162         return pa;
 163 }
 164
 165 /* Return the result of applying the comparison operator "type"
 166  * to "pa1" and "pa2".
 167  *
 168  * In particular, construct an isl_pw_aff that is equal to 1
 169  * on the subset of the shared domain of "pa1" and "pa2" where
 170  * the comparison holds and 0 on the other part of the shared domain.
 171  *
 172  * If "pa1" or "pa2" involve any NaN, then return NaN.
 173  */
 174 __isl_give isl_pw_aff *pet_comparison(enum pet_op_type type,
 175         __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
 176 {
 177         isl_set *dom;
 178         isl_set *cond;
 179         isl_pw_aff *res;
 180
 181         if (!pa1 || !pa2)
 182                 goto error;
 183         if (isl_pw_aff_involves_nan(pa1) || isl_pw_aff_involves_nan(pa2)) {
 184                 isl_space *space = isl_pw_aff_get_domain_space(pa1);
 185                 isl_local_space *ls = isl_local_space_from_space(space);
 186                 isl_pw_aff_free(pa1);
 187                 isl_pw_aff_free(pa2);
 188                 return isl_pw_aff_nan_on_domain(ls);
 189         }
 190
 191         dom = isl_pw_aff_domain(isl_pw_aff_copy(pa1));
 192         dom = isl_set_intersect(dom, isl_pw_aff_domain(isl_pw_aff_copy(pa2)));
 193
 194         switch (type) {
 195         case pet_op_lt:
 196                 cond = isl_pw_aff_lt_set(pa1, pa2);
 197                 break;
 198         case pet_op_le:
 199                 cond = isl_pw_aff_le_set(pa1, pa2);
 200                 break;
 201         case pet_op_gt:
 202                 cond = isl_pw_aff_gt_set(pa1, pa2);
 203                 break;
 204         case pet_op_ge:
 205                 cond = isl_pw_aff_ge_set(pa1, pa2);
 206                 break;
 207         case pet_op_eq:
 208                 cond = isl_pw_aff_eq_set(pa1, pa2);
 209                 break;
 210         case pet_op_ne:
 211                 cond = isl_pw_aff_ne_set(pa1, pa2);
 212                 break;
 213         default:
 214                 isl_die(isl_pw_aff_get_ctx(pa1), isl_error_internal,
 215                         "not a comparison operator", cond = NULL);
 216                 isl_pw_aff_free(pa1);
 217                 isl_pw_aff_free(pa2);
 218         }
 219
 220         cond = isl_set_coalesce(cond);
 221         res = indicator_function(cond, dom);
 222
 223         return res;
 224 error:
 225         isl_pw_aff_free(pa1);
 226         isl_pw_aff_free(pa2);
 227         return NULL;
 228 }
 229
 230 /* Return "lhs && rhs", with shortcut semantics.
 231  * That is, if lhs is false, then the result is defined even if rhs is not.
 232  * In practice, we compute lhs ? rhs : lhs.
 233  */
 234 static __isl_give isl_pw_aff *pw_aff_and_then(__isl_take isl_pw_aff *lhs,
 235         __isl_take isl_pw_aff *rhs)
 236 {
 237         return isl_pw_aff_cond(isl_pw_aff_copy(lhs), rhs, lhs);
 238 }
 239
 240 /* Return "lhs || rhs", with shortcut semantics.
 241  * That is, if lhs is true, then the result is defined even if rhs is not.
 242  * In practice, we compute lhs ? lhs : rhs.
 243  */
 244 static __isl_give isl_pw_aff *pw_aff_or_else(__isl_take isl_pw_aff *lhs,
 245         __isl_take isl_pw_aff *rhs)
 246 {
 247         return isl_pw_aff_cond(isl_pw_aff_copy(lhs), lhs, rhs);
 248 }
 249
 250 /* Return the result of applying the boolean operator "type"
 251  * to "pa1" and "pa2".
 252  */
 253 __isl_give isl_pw_aff *pet_boolean(enum pet_op_type type,
 254         __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
 255 {
 256         isl_ctx *ctx;
 257
 258         switch (type) {
 259         case pet_op_land:
 260                 return pw_aff_and_then(pa1, pa2);
 261         case pet_op_lor:
 262                 return pw_aff_or_else(pa1, pa2);
 263         default:
 264                 ctx = isl_pw_aff_get_ctx(pa1);
 265                 isl_pw_aff_free(pa1);
 266                 isl_pw_aff_free(pa2);
 267                 isl_die(ctx, isl_error_internal,
 268                         "not a boolean operator", return NULL);
 269         }
 270 }