1/* 2 * Copyright 2008-2009 Katholieke Universiteit Leuven 3 * 4 * Use of this software is governed by the MIT license 5 * 6 * Written by Sven Verdoolaege, K.U.Leuven, Departement 7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium 8 */ 9 10#ifndef ISL_MAP_PRIVATE_H 11#define ISL_MAP_PRIVATE_H 12 13#define isl_basic_set isl_basic_map 14#define isl_set isl_map 15#define isl_basic_set_list isl_basic_map_list 16#define isl_set_list isl_map_list 17#include <isl/list.h> 18ISL_DECLARE_LIST(basic_map) 19ISL_DECLARE_LIST(map) 20#include <isl/set.h> 21#include <isl/map.h> 22#include <isl_reordering.h> 23#include <isl/vec.h> 24 25/* A "basic map" is a relation between two sets of variables, 26 * called the "in" and "out" variables. 27 * A "basic set" is a basic map with a zero-dimensional 28 * domain. 29 * 30 * It is implemented as a set with two extra fields: 31 * n_in is the number of in variables 32 * n_out is the number of out variables 33 * n_in + n_out should be equal to set.dim 34 */ 35struct isl_basic_map { 36 int ref; 37#define ISL_BASIC_MAP_FINAL (1 << 0) 38#define ISL_BASIC_MAP_EMPTY (1 << 1) 39#define ISL_BASIC_MAP_NO_IMPLICIT (1 << 2) 40#define ISL_BASIC_MAP_NO_REDUNDANT (1 << 3) 41#define ISL_BASIC_MAP_RATIONAL (1 << 4) 42#define ISL_BASIC_MAP_NORMALIZED (1 << 5) 43#define ISL_BASIC_MAP_NORMALIZED_DIVS (1 << 6) 44#define ISL_BASIC_MAP_ALL_EQUALITIES (1 << 7) 45#define ISL_BASIC_SET_FINAL (1 << 0) 46#define ISL_BASIC_SET_EMPTY (1 << 1) 47#define ISL_BASIC_SET_NO_IMPLICIT (1 << 2) 48#define ISL_BASIC_SET_NO_REDUNDANT (1 << 3) 49#define ISL_BASIC_SET_RATIONAL (1 << 4) 50#define ISL_BASIC_SET_NORMALIZED (1 << 5) 51#define ISL_BASIC_SET_NORMALIZED_DIVS (1 << 6) 52#define ISL_BASIC_SET_ALL_EQUALITIES (1 << 7) 53 unsigned flags; 54 55 struct isl_ctx *ctx; 56 57 isl_space *dim; 58 unsigned extra; 59 60 unsigned n_eq; 61 unsigned n_ineq; 62 63 size_t c_size; 64 isl_int **eq; 65 isl_int **ineq; 66 67 unsigned n_div; 68 69 isl_int **div; 70 71 struct isl_vec *sample; 72 73 struct isl_blk block; 74 struct isl_blk block2; 75}; 76 77#undef EL 78#define EL isl_basic_set 79 80#include <isl_list_templ.h> 81 82/* A "map" is a (possibly disjoint) union of basic maps. 83 * A "set" is a (possibly disjoint) union of basic sets. 84 * 85 * Currently, the isl_set structure is identical to the isl_map structure 86 * and the library depends on this correspondence internally. 87 * However, users should not depend on this correspondence. 88 */ 89struct isl_map { 90 int ref; 91#define ISL_MAP_DISJOINT (1 << 0) 92#define ISL_MAP_NORMALIZED (1 << 1) 93#define ISL_SET_DISJOINT (1 << 0) 94#define ISL_SET_NORMALIZED (1 << 1) 95 unsigned flags; 96 97 struct isl_ctx *ctx; 98 99 isl_space *dim; 100 101 int n; 102 103 size_t size; 104 struct isl_basic_map *p[1]; 105}; 106 107#undef EL 108#define EL isl_set 109 110#include <isl_list_templ.h> 111 112__isl_give isl_map *isl_map_realign(__isl_take isl_map *map, 113 __isl_take isl_reordering *r); 114__isl_give isl_set *isl_set_realign(__isl_take isl_set *set, 115 __isl_take isl_reordering *r); 116 117__isl_give isl_map *isl_map_reset(__isl_take isl_map *map, 118 enum isl_dim_type type); 119 120__isl_give isl_basic_set *isl_basic_set_reset_space( 121 __isl_take isl_basic_set *bset, __isl_take isl_space *dim); 122__isl_give isl_basic_map *isl_basic_map_reset_space( 123 __isl_take isl_basic_map *bmap, __isl_take isl_space *dim); 124__isl_give isl_map *isl_map_reset_space(__isl_take isl_map *map, 125 __isl_take isl_space *dim); 126 127unsigned isl_basic_map_offset(struct isl_basic_map *bmap, 128 enum isl_dim_type type); 129unsigned isl_basic_set_offset(struct isl_basic_set *bset, 130 enum isl_dim_type type); 131 132int isl_basic_map_may_be_set(__isl_keep isl_basic_map *bmap); 133int isl_map_may_be_set(__isl_keep isl_map *map); 134int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set); 135int isl_basic_map_compatible_domain(struct isl_basic_map *bmap, 136 struct isl_basic_set *bset); 137int isl_basic_map_compatible_range(struct isl_basic_map *bmap, 138 struct isl_basic_set *bset); 139 140struct isl_basic_map *isl_basic_map_extend_space(struct isl_basic_map *base, 141 __isl_take isl_space *dim, unsigned extra, 142 unsigned n_eq, unsigned n_ineq); 143struct isl_basic_set *isl_basic_set_extend_space(struct isl_basic_set *base, 144 __isl_take isl_space *dim, unsigned extra, 145 unsigned n_eq, unsigned n_ineq); 146struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1, 147 struct isl_basic_set *bset2, unsigned pos); 148 149struct isl_map *isl_map_grow(struct isl_map *map, int n); 150struct isl_set *isl_set_grow(struct isl_set *set, int n); 151 152int isl_basic_set_contains(struct isl_basic_set *bset, struct isl_vec *vec); 153int isl_basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec); 154 155__isl_give isl_basic_set *isl_basic_set_alloc_space(__isl_take isl_space *dim, 156 unsigned extra, unsigned n_eq, unsigned n_ineq); 157__isl_give isl_set *isl_set_alloc_space(__isl_take isl_space *dim, int n, 158 unsigned flags); 159__isl_give isl_basic_map *isl_basic_map_alloc_space(__isl_take isl_space *dim, 160 unsigned extra, unsigned n_eq, unsigned n_ineq); 161__isl_give isl_map *isl_map_alloc_space(__isl_take isl_space *dim, int n, 162 unsigned flags); 163 164unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap); 165 166int isl_basic_map_alloc_equality(struct isl_basic_map *bmap); 167int isl_basic_set_alloc_equality(struct isl_basic_set *bset); 168int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n); 169int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n); 170int isl_basic_set_free_equality(struct isl_basic_set *bset, unsigned n); 171int isl_basic_set_alloc_inequality(struct isl_basic_set *bset); 172int isl_basic_map_alloc_inequality(struct isl_basic_map *bmap); 173int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n); 174int isl_basic_map_alloc_div(struct isl_basic_map *bmap); 175int isl_basic_set_alloc_div(struct isl_basic_set *bset); 176int isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n); 177int isl_basic_set_free_div(struct isl_basic_set *bset, unsigned n); 178void isl_basic_map_inequality_to_equality( 179 struct isl_basic_map *bmap, unsigned pos); 180int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos); 181int isl_basic_set_drop_equality(struct isl_basic_set *bset, unsigned pos); 182int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos); 183int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos); 184__isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset, 185 isl_int *eq); 186__isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap, 187 isl_int *eq); 188__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset, 189 isl_int *ineq); 190__isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap, 191 isl_int *ineq); 192 193int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos); 194 195struct isl_basic_set *isl_basic_set_cow(struct isl_basic_set *bset); 196struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap); 197struct isl_set *isl_set_cow(struct isl_set *set); 198struct isl_map *isl_map_cow(struct isl_map *map); 199 200struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap); 201struct isl_basic_set *isl_basic_set_set_to_empty(struct isl_basic_set *bset); 202struct isl_basic_set *isl_basic_set_order_divs(struct isl_basic_set *bset); 203void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b); 204struct isl_basic_map *isl_basic_map_order_divs(struct isl_basic_map *bmap); 205__isl_give isl_map *isl_map_order_divs(__isl_take isl_map *map); 206struct isl_basic_map *isl_basic_map_align_divs( 207 struct isl_basic_map *dst, struct isl_basic_map *src); 208struct isl_basic_set *isl_basic_set_align_divs( 209 struct isl_basic_set *dst, struct isl_basic_set *src); 210__isl_give isl_basic_map *isl_basic_map_sort_divs( 211 __isl_take isl_basic_map *bmap); 212__isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map); 213struct isl_basic_map *isl_basic_map_gauss( 214 struct isl_basic_map *bmap, int *progress); 215struct isl_basic_set *isl_basic_set_gauss( 216 struct isl_basic_set *bset, int *progress); 217__isl_give isl_basic_set *isl_basic_set_sort_constraints( 218 __isl_take isl_basic_set *bset); 219int isl_basic_map_plain_cmp(const __isl_keep isl_basic_map *bmap1, 220 const __isl_keep isl_basic_map *bmap2); 221int isl_basic_set_plain_is_equal(__isl_keep isl_basic_set *bset1, 222 __isl_keep isl_basic_set *bset2); 223int isl_basic_map_plain_is_equal(__isl_keep isl_basic_map *bmap1, 224 __isl_keep isl_basic_map *bmap2); 225struct isl_basic_map *isl_basic_map_normalize_constraints( 226 struct isl_basic_map *bmap); 227struct isl_basic_set *isl_basic_set_normalize_constraints( 228 struct isl_basic_set *bset); 229struct isl_basic_map *isl_basic_map_implicit_equalities( 230 struct isl_basic_map *bmap); 231struct isl_basic_set *isl_basic_map_underlying_set(struct isl_basic_map *bmap); 232__isl_give isl_basic_set *isl_basic_set_underlying_set( 233 __isl_take isl_basic_set *bset); 234struct isl_set *isl_map_underlying_set(struct isl_map *map); 235struct isl_basic_map *isl_basic_map_overlying_set(struct isl_basic_set *bset, 236 struct isl_basic_map *like); 237__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving( 238 __isl_take isl_basic_set *bset, unsigned first, unsigned n); 239__isl_give isl_basic_set *isl_basic_set_drop(__isl_take isl_basic_set *bset, 240 enum isl_dim_type type, unsigned first, unsigned n); 241struct isl_basic_map *isl_basic_map_drop(struct isl_basic_map *bmap, 242 enum isl_dim_type type, unsigned first, unsigned n); 243struct isl_set *isl_set_drop(struct isl_set *set, 244 enum isl_dim_type type, unsigned first, unsigned n); 245struct isl_basic_set *isl_basic_set_drop_dims( 246 struct isl_basic_set *bset, unsigned first, unsigned n); 247struct isl_set *isl_set_drop_dims( 248 struct isl_set *set, unsigned first, unsigned n); 249struct isl_map *isl_map_drop_inputs( 250 struct isl_map *map, unsigned first, unsigned n); 251struct isl_map *isl_map_drop(struct isl_map *map, 252 enum isl_dim_type type, unsigned first, unsigned n); 253 254struct isl_map *isl_map_remove_empty_parts(struct isl_map *map); 255struct isl_set *isl_set_remove_empty_parts(struct isl_set *set); 256 257struct isl_set *isl_set_normalize(struct isl_set *set); 258 259struct isl_set *isl_set_drop_vars( 260 struct isl_set *set, unsigned first, unsigned n); 261 262struct isl_basic_map *isl_basic_map_eliminate_vars( 263 struct isl_basic_map *bmap, unsigned pos, unsigned n); 264struct isl_basic_set *isl_basic_set_eliminate_vars( 265 struct isl_basic_set *bset, unsigned pos, unsigned n); 266 267__isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map, 268 enum isl_dim_type type, unsigned first, unsigned n); 269__isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set, 270 enum isl_dim_type type, unsigned first, unsigned n); 271 272int isl_basic_set_constraint_is_redundant(struct isl_basic_set **bset, 273 isl_int *c, isl_int *opt_n, isl_int *opt_d); 274 275int isl_basic_map_add_div_constraint(__isl_keep isl_basic_map *bmap, 276 unsigned div, int sign); 277int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div); 278struct isl_basic_map *isl_basic_map_drop_redundant_divs( 279 struct isl_basic_map *bmap); 280struct isl_basic_set *isl_basic_set_drop_redundant_divs( 281 struct isl_basic_set *bset); 282 283struct isl_basic_set *isl_basic_set_recession_cone(struct isl_basic_set *bset); 284struct isl_basic_set *isl_basic_set_lineality_space(struct isl_basic_set *bset); 285 286struct isl_basic_set *isl_basic_set_set_rational(struct isl_basic_set *bset); 287__isl_give isl_set *isl_set_set_rational(__isl_take isl_set *set); 288__isl_give isl_basic_map *isl_basic_map_set_rational( 289 __isl_take isl_basic_map *bmap); 290__isl_give isl_map *isl_map_set_rational(__isl_take isl_map *map); 291 292int isl_map_has_rational(__isl_keep isl_map *map); 293int isl_set_has_rational(__isl_keep isl_set *set); 294 295struct isl_mat; 296 297struct isl_basic_set *isl_basic_set_preimage(struct isl_basic_set *bset, 298 struct isl_mat *mat); 299struct isl_set *isl_set_preimage(struct isl_set *set, struct isl_mat *mat); 300 301__isl_give isl_basic_set *isl_basic_set_transform_dims( 302 __isl_take isl_basic_set *bset, enum isl_dim_type type, unsigned first, 303 __isl_take isl_mat *trans); 304 305isl_int *isl_set_wrap_facet(__isl_keep isl_set *set, 306 isl_int *facet, isl_int *ridge); 307 308int isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap, 309 __isl_keep isl_point *point); 310int isl_set_contains_point(__isl_keep isl_set *set, __isl_keep isl_point *point); 311 312int isl_basic_set_vars_get_sign(__isl_keep isl_basic_set *bset, 313 unsigned first, unsigned n, int *signs); 314int isl_set_foreach_orthant(__isl_keep isl_set *set, 315 int (*fn)(__isl_take isl_set *orthant, int *signs, void *user), 316 void *user); 317 318int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap, 319 unsigned pos, isl_int *div); 320int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset, 321 unsigned pos, isl_int *div); 322int isl_basic_map_is_div_constraint(__isl_keep isl_basic_map *bmap, 323 isl_int *constraint, unsigned div); 324int isl_basic_set_is_div_constraint(__isl_keep isl_basic_set *bset, 325 isl_int *constraint, unsigned div); 326 327__isl_give isl_basic_set *isl_basic_set_from_local_space( 328 __isl_take isl_local_space *ls); 329__isl_give isl_basic_map *isl_basic_map_from_local_space( 330 __isl_take isl_local_space *ls); 331__isl_give isl_basic_set *isl_basic_set_expand_divs( 332 __isl_take isl_basic_set *bset, __isl_take isl_mat *div, int *exp); 333 334int isl_basic_map_divs_known(__isl_keep isl_basic_map *bmap); 335__isl_give isl_mat *isl_basic_set_get_divs(__isl_keep isl_basic_set *bset); 336__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap); 337 338__isl_give isl_map *isl_map_inline_foreach_basic_map(__isl_take isl_map *map, 339 __isl_give isl_basic_map *(*fn)(__isl_take isl_basic_map *bmap)); 340 341__isl_give isl_map *isl_map_align_params_map_map_and( 342 __isl_take isl_map *map1, __isl_take isl_map *map2, 343 __isl_give isl_map *(*fn)(__isl_take isl_map *map1, 344 __isl_take isl_map *map2)); 345int isl_map_align_params_map_map_and_test(__isl_keep isl_map *map1, 346 __isl_keep isl_map *map2, 347 int (*fn)(__isl_keep isl_map *map1, __isl_keep isl_map *map2)); 348 349int isl_basic_map_foreach_lexopt(__isl_keep isl_basic_map *bmap, int max, 350 int (*fn)(__isl_take isl_basic_set *dom, __isl_take isl_aff_list *list, 351 void *user), 352 void *user); 353int isl_basic_set_foreach_lexopt(__isl_keep isl_basic_set *bset, int max, 354 int (*fn)(__isl_take isl_basic_set *dom, __isl_take isl_aff_list *list, 355 void *user), 356 void *user); 357 358__isl_give isl_set *isl_set_substitute(__isl_take isl_set *set, 359 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs); 360 361__isl_give isl_set *isl_set_gist_params_basic_set(__isl_take isl_set *set, 362 __isl_take isl_basic_set *context); 363 364int isl_map_compatible_range(__isl_keep isl_map *map, __isl_keep isl_set *set); 365 366int isl_basic_map_plain_is_single_valued(__isl_keep isl_basic_map *bmap); 367 368int isl_map_is_set(__isl_keep isl_map *map); 369 370#endif 371