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 /* Internal data structure for pet_union_map_move_dims.
  38  *
  39  * dst_type, dst_pos, src_type, src_pos and n are the arguments
  40  * to the isl_map_move_dims calls
  41  * res collects the results.
  42  */
  43 struct pet_union_map_move_dims_data {
  44         enum isl_dim_type dst_type;
  45         unsigned dst_pos;
  46         enum isl_dim_type src_type;
  47         unsigned src_pos;
  48         unsigned n;
  49
  50         isl_union_map *res;
  51 };
  52
  53 /* Call isl_map_move_dims on "map" using the arguments in "data" and
  54  * add the result to data->res.
  55  */
  56 static isl_stat map_move_dims(__isl_take isl_map *map, void *user)
  57 {
  58         struct pet_union_map_move_dims_data *data = user;
  59
  60         map = isl_map_move_dims(map, data->dst_type, data->dst_pos,
  61                                 data->src_type, data->src_pos, data->n);
  62         data->res = isl_union_map_add_map(data->res, map);
  63
  64         return isl_stat_ok;
  65 }
  66
  67 /* Call isl_map_move_dims with the given arguments on each of the maps
  68  * in "umap" and return the union of the results.
  69  *
  70  * This function can only meaningfully be called on a union map
  71  * where all maps have the same space for both dst_type and src_type.
  72  * One of these should then be isl_dim_param as otherwise the union map
  73  * could only contain a single map.
  74  */
  75 __isl_give isl_union_map *pet_union_map_move_dims(
  76         __isl_take isl_union_map *umap,
  77         enum isl_dim_type dst_type, unsigned dst_pos,
  78         enum isl_dim_type src_type, unsigned src_pos, unsigned n)
  79 {
  80         isl_space *space;
  81         struct pet_union_map_move_dims_data data =
  82                 { dst_type, dst_pos, src_type, src_pos, n };
  83
  84         space = isl_union_map_get_space(umap);
  85         if (src_type == isl_dim_param)
  86                 space = isl_space_drop_dims(space, src_type, src_pos, n);
  87         data.res = isl_union_map_empty(space);
  88         if (isl_union_map_foreach_map(umap, &map_move_dims, &data) < 0)
  89                 data.res = isl_union_map_free(data.res);
  90
  91         isl_union_map_free(umap);
  92         return data.res;
  93 }
  94
  95 /* Return a function that projects "space" onto its first "n" dimensions,
  96  * with anonymous target space.
  97  */
  98 __isl_give isl_multi_aff *pet_prefix_projection(__isl_take isl_space *space,
  99         int n)
 100 {
 101         int dim;
 102
 103         dim = isl_space_dim(space, isl_dim_set);
 104         return isl_multi_aff_project_out_map(space, isl_dim_set, n, dim - n);
 105 }
 106
 107 /* If the isl_pw_aff on which isl_pw_aff_foreach_piece is called
 108  * has a constant expression on its only domain, then replace
 109  * the isl_val in *user by this constant.
 110  * The caller is assumed to have checked that this function will
 111  * be called exactly once.
 112  */
 113 static isl_stat extract_cst(__isl_take isl_set *set, __isl_take isl_aff *aff,
 114         void *user)
 115 {
 116         isl_val **inc = (isl_val **)user;
 117
 118         if (isl_aff_is_cst(aff)) {
 119                 isl_val_free(*inc);
 120                 *inc = isl_aff_get_constant_val(aff);
 121         }
 122
 123         isl_set_free(set);
 124         isl_aff_free(aff);
 125
 126         return isl_stat_ok;
 127 }
 128
 129 /* If "pa" represents a constant value over a single domain,
 130  * then return this constant.
 131  * Otherwise return NaN.
 132  */
 133 __isl_give isl_val *pet_extract_cst(__isl_keep isl_pw_aff *pa)
 134 {
 135         isl_val *v;
 136
 137         if (!pa)
 138                 return NULL;
 139         v = isl_val_nan(isl_pw_aff_get_ctx(pa));
 140         if (isl_pw_aff_n_piece(pa) != 1)
 141                 return v;
 142         if (isl_pw_aff_foreach_piece(pa, &extract_cst, &v) < 0)
 143                 v = isl_val_free(v);
 144         return v;
 145 }
 146
 147 /* Return the piecewise affine expression "set ? 1 : 0" defined on "dom".
 148  */
 149 static __isl_give isl_pw_aff *indicator_function(__isl_take isl_set *set,
 150         __isl_take isl_set *dom)
 151 {
 152         isl_pw_aff *pa;
 153         pa = isl_set_indicator_function(set);
 154         pa = isl_pw_aff_intersect_domain(pa, isl_set_coalesce(dom));
 155         return pa;
 156 }
 157
 158 /* Return "lhs && rhs", defined on the shared definition domain.
 159  */
 160 __isl_give isl_pw_aff *pet_and(__isl_take isl_pw_aff *lhs,
 161         __isl_take isl_pw_aff *rhs)
 162 {
 163         isl_set *cond;
 164         isl_set *dom;
 165
 166         dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(lhs)),
 167                                  isl_pw_aff_domain(isl_pw_aff_copy(rhs)));
 168         cond = isl_set_intersect(isl_pw_aff_non_zero_set(lhs),
 169                                  isl_pw_aff_non_zero_set(rhs));
 170         return indicator_function(cond, dom);
 171 }
 172
 173 /* Return "!pa", defined on the domain of "pa".
 174  *
 175  * If "pa" involves any NaN, then return NaN.
 176  */
 177 __isl_give isl_pw_aff *pet_not(__isl_take isl_pw_aff *pa)
 178 {
 179         isl_set *cond, *dom;
 180
 181         if (!pa)
 182                 return NULL;
 183         if (isl_pw_aff_involves_nan(pa)) {
 184                 isl_space *space = isl_pw_aff_get_domain_space(pa);
 185                 isl_local_space *ls = isl_local_space_from_space(space);
 186                 isl_pw_aff_free(pa);
 187                 return isl_pw_aff_nan_on_domain(ls);
 188         }
 189
 190         dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
 191         cond = isl_pw_aff_zero_set(pa);
 192         pa = indicator_function(cond, dom);
 193
 194         return pa;
 195 }
 196
 197 /* Return "!!pa", i.e., a function that is equal to 1 when "pa"
 198  * is non-zero and equal to 0 when "pa" is equal to zero,
 199  * on the domain of "pa".
 200  *
 201  * If "pa" involves any NaN, then return NaN.
 202  */
 203 __isl_give isl_pw_aff *pet_to_bool(__isl_take isl_pw_aff *pa)
 204 {
 205         isl_set *cond, *dom;
 206
 207         if (!pa)
 208                 return NULL;
 209         if (isl_pw_aff_involves_nan(pa)) {
 210                 isl_space *space = isl_pw_aff_get_domain_space(pa);
 211                 isl_local_space *ls = isl_local_space_from_space(space);
 212                 isl_pw_aff_free(pa);
 213                 return isl_pw_aff_nan_on_domain(ls);
 214         }
 215
 216         dom = isl_pw_aff_domain(isl_pw_aff_copy(pa));
 217         cond = isl_pw_aff_non_zero_set(pa);
 218         pa = indicator_function(cond, dom);
 219
 220         return pa;
 221 }
 222
 223 /* Return the result of applying the comparison operator "type"
 224  * to "pa1" and "pa2".
 225  *
 226  * In particular, construct an isl_pw_aff that is equal to 1
 227  * on the subset of the shared domain of "pa1" and "pa2" where
 228  * the comparison holds and 0 on the other part of the shared domain.
 229  *
 230  * If "pa1" or "pa2" involve any NaN, then return NaN.
 231  */
 232 __isl_give isl_pw_aff *pet_comparison(enum pet_op_type type,
 233         __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
 234 {
 235         isl_set *dom;
 236         isl_set *cond;
 237         isl_pw_aff *res;
 238
 239         if (!pa1 || !pa2)
 240                 goto error;
 241         if (isl_pw_aff_involves_nan(pa1) || isl_pw_aff_involves_nan(pa2)) {
 242                 isl_space *space = isl_pw_aff_get_domain_space(pa1);
 243                 isl_local_space *ls = isl_local_space_from_space(space);
 244                 isl_pw_aff_free(pa1);
 245                 isl_pw_aff_free(pa2);
 246                 return isl_pw_aff_nan_on_domain(ls);
 247         }
 248
 249         dom = isl_pw_aff_domain(isl_pw_aff_copy(pa1));
 250         dom = isl_set_intersect(dom, isl_pw_aff_domain(isl_pw_aff_copy(pa2)));
 251
 252         switch (type) {
 253         case pet_op_lt:
 254                 cond = isl_pw_aff_lt_set(pa1, pa2);
 255                 break;
 256         case pet_op_le:
 257                 cond = isl_pw_aff_le_set(pa1, pa2);
 258                 break;
 259         case pet_op_gt:
 260                 cond = isl_pw_aff_gt_set(pa1, pa2);
 261                 break;
 262         case pet_op_ge:
 263                 cond = isl_pw_aff_ge_set(pa1, pa2);
 264                 break;
 265         case pet_op_eq:
 266                 cond = isl_pw_aff_eq_set(pa1, pa2);
 267                 break;
 268         case pet_op_ne:
 269                 cond = isl_pw_aff_ne_set(pa1, pa2);
 270                 break;
 271         default:
 272                 isl_die(isl_pw_aff_get_ctx(pa1), isl_error_internal,
 273                         "not a comparison operator", cond = NULL);
 274                 isl_pw_aff_free(pa1);
 275                 isl_pw_aff_free(pa2);
 276         }
 277
 278         cond = isl_set_coalesce(cond);
 279         res = indicator_function(cond, dom);
 280
 281         return res;
 282 error:
 283         isl_pw_aff_free(pa1);
 284         isl_pw_aff_free(pa2);
 285         return NULL;
 286 }
 287
 288 /* Return "lhs && rhs", with shortcut semantics.
 289  * That is, if lhs is false, then the result is defined even if rhs is not.
 290  * In practice, we compute lhs ? rhs : lhs.
 291  */
 292 static __isl_give isl_pw_aff *pw_aff_and_then(__isl_take isl_pw_aff *lhs,
 293         __isl_take isl_pw_aff *rhs)
 294 {
 295         return isl_pw_aff_cond(isl_pw_aff_copy(lhs), rhs, lhs);
 296 }
 297
 298 /* Return "lhs || rhs", with shortcut semantics.
 299  * That is, if lhs is true, then the result is defined even if rhs is not.
 300  * In practice, we compute lhs ? lhs : rhs.
 301  */
 302 static __isl_give isl_pw_aff *pw_aff_or_else(__isl_take isl_pw_aff *lhs,
 303         __isl_take isl_pw_aff *rhs)
 304 {
 305         return isl_pw_aff_cond(isl_pw_aff_copy(lhs), lhs, rhs);
 306 }
 307
 308 /* Return the result of applying the boolean operator "type"
 309  * to "pa1" and "pa2".
 310  */
 311 __isl_give isl_pw_aff *pet_boolean(enum pet_op_type type,
 312         __isl_take isl_pw_aff *pa1, __isl_take isl_pw_aff *pa2)
 313 {
 314         isl_ctx *ctx;
 315
 316         switch (type) {
 317         case pet_op_land:
 318                 return pw_aff_and_then(pa1, pa2);
 319         case pet_op_lor:
 320                 return pw_aff_or_else(pa1, pa2);
 321         default:
 322                 ctx = isl_pw_aff_get_ctx(pa1);
 323                 isl_pw_aff_free(pa1);
 324                 isl_pw_aff_free(pa2);
 325                 isl_die(ctx, isl_error_internal,
 326                         "not a boolean operator", return NULL);
 327         }
 328 }