/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_map.c

Source (jump to first uncovered line)
/*
 * Copyright 2008-2009 Katholieke Universiteit Leuven
 * Copyright 2010      INRIA Saclay
 * Copyright 2012-2014 Ecole Normale Superieure
 * Copyright 2014      INRIA Rocquencourt
 * Copyright 2016      INRIA Paris
 * Copyright 2016      Sven Verdoolaege
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
 * B.P. 105 - 78153 Le Chesnay, France
 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
 * CS 42112, 75589 Paris Cedex 12, France
 */

#include <string.h>
#include <isl_ctx_private.h>
#include <isl_map_private.h>
#include <isl_blk.h>
#include <isl/id.h>
#include <isl/constraint.h>
#include "isl_space_private.h"
#include "isl_equalities.h"
#include <isl_lp_private.h>
#include <isl_seq.h>
#include <isl/set.h>
#include <isl/map.h>
#include <isl_reordering.h>
#include "isl_sample.h"
#include <isl_sort.h>
#include "isl_tab.h"
#include <isl/vec.h>
#include <isl_mat_private.h>
#include <isl_vec_private.h>
#include <isl_dim_map.h>
#include <isl_local_space_private.h>
#include <isl_aff_private.h>
#include <isl_options_private.h>
#include <isl_morph.h>
#include <isl_val_private.h>

#include <bset_to_bmap.c>
#include <bset_from_bmap.c>
#include <set_to_map.c>
#include <set_from_map.c>

static unsigned n(__isl_keep isl_space *dim, enum isl_dim_type type)
{
  switch (type) {
  case isl_dim_param: return dim->nparam8.61k;
  case isl_dim_in:  return dim->n_in71.2k;
  case isl_dim_out: return dim->n_out288k;
  case isl_dim_all: return dim->nparam + dim->n_in + dim->n_out134;
  default:    return 00;
  }
}

static unsigned pos(__isl_keep isl_space *dim, enum isl_dim_type type)
{
  switch (type) {
  case isl_dim_param: return 1386;
  case isl_dim_in:  return 1 + dim->nparam14.3k;
  case isl_dim_out: return 1 + dim->nparam + dim->n_in170k;
  default:    return 00;
  }
}

unsigned isl_basic_map_dim(__isl_keep isl_basic_map *bmap,
        enum isl_dim_type type)
{
  if (!bmap)
    return 0;
  switch (type) {
  case isl_dim_cst: return 10;
  case isl_dim_param:
  case isl_dim_in:
  case isl_dim_out: return isl_space_dim(bmap->dim, type);
  case isl_dim_div: return bmap->n_div3.27M;
  case isl_dim_all: return isl_basic_map_total_dim(bmap)359k;
  default:    return 00;
  }
}

/* Return the space of "map".
 */
__isl_keep isl_space *isl_map_peek_space(__isl_keep const isl_map *map)
{
  return map ? map->dim4.11M : NULL;
}

unsigned isl_map_dim(__isl_keep isl_map *map, enum isl_dim_type type)
{
  return map ? n(map->dim, type) : 00;
}

unsigned isl_set_dim(__isl_keep isl_set *set, enum isl_dim_type type)
{
  return set ? n(set->dim, type) : 00;
}

unsigned isl_basic_map_offset(struct isl_basic_map *bmap,
          enum isl_dim_type type)
{
  isl_space *space;

  if (!bmap)
    return 0;

  space = bmap->dim;
  switch (type) {
  case isl_dim_cst: return 00;
  case isl_dim_param: return 14.21k;
  case isl_dim_in:  return 1 + space->nparam338k;
  case isl_dim_out: return 1 + space->nparam + space->n_in1.13M;
  case isl_dim_div: return 1 + space->nparam + space->n_in +
                space->n_out;
  default:    return 00;
  }
}

unsigned isl_basic_set_offset(__isl_keep isl_basic_set *bset,
          enum isl_dim_type type)
{
  return isl_basic_map_offset(bset, type);
}

static unsigned map_offset(__isl_keep isl_map *map, enum isl_dim_type type)
{
  return pos(map->dim, type);
}

unsigned isl_basic_set_dim(__isl_keep isl_basic_set *bset,
        enum isl_dim_type type)
{
  return isl_basic_map_dim(bset, type);
}

unsigned isl_basic_set_n_dim(__isl_keep isl_basic_set *bset)
{
  return isl_basic_set_dim(bset, isl_dim_set);
}

unsigned isl_basic_set_n_param(__isl_keep isl_basic_set *bset)
{
  return isl_basic_set_dim(bset, isl_dim_param);
}

unsigned isl_basic_set_total_dim(__isl_keep const isl_basic_set *bset)
{
  if (!bset)
    return 0;
  return isl_space_dim(bset->dim, isl_dim_all) + bset->n_div;
}

unsigned isl_set_n_dim(__isl_keep isl_set *set)
{
  return isl_set_dim(set, isl_dim_set);
}

unsigned isl_set_n_param(__isl_keep isl_set *set)
{
  return isl_set_dim(set, isl_dim_param);
}

unsigned isl_basic_map_n_in(__isl_keep const isl_basic_map *bmap)
{
  return bmap ? bmap->dim->n_in : 0;
}

unsigned isl_basic_map_n_out(__isl_keep const isl_basic_map *bmap)
{
  return bmap ? bmap->dim->n_out : 0;
}

unsigned isl_basic_map_n_param(__isl_keep const isl_basic_map *bmap)
{
  return bmap ? bmap->dim->nparam : 0;
}

unsigned isl_basic_map_n_div(__isl_keep const isl_basic_map *bmap)
{
  return bmap ? bmap->n_div : 0;
}

unsigned isl_basic_map_total_dim(__isl_keep const isl_basic_map *bmap)
{
  return bmap ? isl_space_dim(bmap->dim, isl_dim_all) + bmap->n_div : 00;
}

unsigned isl_map_n_in(__isl_keep const isl_map *map)
{
  return map ? map->dim->n_in : 0;
}

unsigned isl_map_n_out(__isl_keep const isl_map *map)
{
  return map ? map->dim->n_out : 0;
}

unsigned isl_map_n_param(__isl_keep const isl_map *map)
{
  return map ? map->dim->nparam : 0;
}

/* Return the number of equality constraints in the description of "bmap".
 * Return -1 on error.
 */
int isl_basic_map_n_equality(__isl_keep isl_basic_map *bmap)
{
  if (!bmap)
    return -1;
  return bmap->n_eq;
}

/* Return the number of equality constraints in the description of "bset".
 * Return -1 on error.
 */
int isl_basic_set_n_equality(__isl_keep isl_basic_set *bset)
{
  return isl_basic_map_n_equality(bset_to_bmap(bset));
}

/* Return the number of inequality constraints in the description of "bmap".
 * Return -1 on error.
 */
int isl_basic_map_n_inequality(__isl_keep isl_basic_map *bmap)
{
  if (!bmap)
    return -1;
  return bmap->n_ineq;
}

/* Return the number of inequality constraints in the description of "bset".
 * Return -1 on error.
 */
int isl_basic_set_n_inequality(__isl_keep isl_basic_set *bset)
{
  return isl_basic_map_n_inequality(bset_to_bmap(bset));
}

/* Do "bmap1" and "bmap2" have the same parameters?
 */
static isl_bool isl_basic_map_has_equal_params(__isl_keep isl_basic_map *bmap1,
  __isl_keep isl_basic_map *bmap2)
{
  isl_space *space1, *space2;

  space1 = isl_basic_map_peek_space(bmap1);
  space2 = isl_basic_map_peek_space(bmap2);
  return isl_space_has_equal_params(space1, space2);
}

/* Do "map1" and "map2" have the same parameters?
 */
isl_bool isl_map_has_equal_params(__isl_keep isl_map *map1,
  __isl_keep isl_map *map2)
{
  isl_space *space1, *space2;

  space1 = isl_map_peek_space(map1);
  space2 = isl_map_peek_space(map2);
  return isl_space_has_equal_params(space1, space2);
}

/* Do "map" and "set" have the same parameters?
 */
static isl_bool isl_map_set_has_equal_params(__isl_keep isl_map *map,
  __isl_keep isl_set *set)
{
  return isl_map_has_equal_params(map, set_to_map(set));
}

isl_bool isl_map_compatible_domain(__isl_keep isl_map *map,
  __isl_keep isl_set *set)
{
  isl_bool m;
  if (!map || !set)
    return isl_bool_error;
  m = isl_map_has_equal_params(map, set_to_map(set));
  if (m < 0 || !m)
    return m;
  return isl_space_tuple_is_equal(map->dim, isl_dim_in,
          set->dim, isl_dim_set);
}

isl_bool isl_basic_map_compatible_domain(__isl_keep isl_basic_map *bmap,
  __isl_keep isl_basic_set *bset)
{
  isl_bool m;
  if (!bmap || !bset)
    return isl_bool_error;
  m = isl_basic_map_has_equal_params(bmap, bset_to_bmap(bset));
  if (m < 0 || !m)
    return m;
  return isl_space_tuple_is_equal(bmap->dim, isl_dim_in,
          bset->dim, isl_dim_set);
}

isl_bool isl_map_compatible_range(__isl_keep isl_map *map,
  __isl_keep isl_set *set)
{
  isl_bool m;
  if (!map || !set)
    return isl_bool_error;
  m = isl_map_has_equal_params(map, set_to_map(set));
  if (m < 0 || !m)
    return m;
  return isl_space_tuple_is_equal(map->dim, isl_dim_out,
          set->dim, isl_dim_set);
}

isl_bool isl_basic_map_compatible_range(__isl_keep isl_basic_map *bmap,
  __isl_keep isl_basic_set *bset)
{
  isl_bool m;
  if (!bmap || !bset)
    return isl_bool_error;
  m = isl_basic_map_has_equal_params(bmap, bset_to_bmap(bset));
  if (m < 0 || !m)
    return m;
  return isl_space_tuple_is_equal(bmap->dim, isl_dim_out,
          bset->dim, isl_dim_set);
}

isl_ctx *isl_basic_map_get_ctx(__isl_keep isl_basic_map *bmap)
{
  return bmap ? bmap->ctx : NULL;
}

isl_ctx *isl_basic_set_get_ctx(__isl_keep isl_basic_set *bset)
{
  return bset ? bset->ctx : NULL;
}

isl_ctx *isl_map_get_ctx(__isl_keep isl_map *map)
{
  return map ? map->ctx : NULL;
}

isl_ctx *isl_set_get_ctx(__isl_keep isl_set *set)
{
  return set ? set->ctx : NULL;
}

/* Return the space of "bmap".
 */
__isl_keep isl_space *isl_basic_map_peek_space(
  __isl_keep const isl_basic_map *bmap)
{
  return bmap ? bmap->dim : NULL;
}

/* Return the space of "bset".
 */
__isl_keep isl_space *isl_basic_set_peek_space(__isl_keep isl_basic_set *bset)
{
  return isl_basic_map_peek_space(bset_to_bmap(bset));
}

__isl_give isl_space *isl_basic_map_get_space(__isl_keep isl_basic_map *bmap)
{
  return isl_space_copy(isl_basic_map_peek_space(bmap));
}

__isl_give isl_space *isl_basic_set_get_space(__isl_keep isl_basic_set *bset)
{
  return isl_basic_map_get_space(bset_to_bmap(bset));
}

/* Extract the divs in "bmap" as a matrix.
 */
__isl_give isl_mat *isl_basic_map_get_divs(__isl_keep isl_basic_map *bmap)
{
  int i;
  isl_ctx *ctx;
  isl_mat *div;
  unsigned total;
  unsigned cols;

  if (!bmap)
    return NULL;

  ctx = isl_basic_map_get_ctx(bmap);
  total = isl_space_dim(bmap->dim, isl_dim_all);
  cols = 1 + 1 + total + bmap->n_div;
  div = isl_mat_alloc(ctx, bmap->n_div, cols);
  if (!div)
    return NULL;

  for (i = 0; 76.9ki < bmap->n_div; ++i15.5k)
    isl_seq_cpy(div->row[i], bmap->div[i], cols);

  return div;
}

/* Extract the divs in "bset" as a matrix.
 */
__isl_give isl_mat *isl_basic_set_get_divs(__isl_keep isl_basic_set *bset)
{
  return isl_basic_map_get_divs(bset);
}

__isl_give isl_local_space *isl_basic_map_get_local_space(
  __isl_keep isl_basic_map *bmap)
{
  isl_mat *div;

  if (!bmap)
    return NULL;

  div = isl_basic_map_get_divs(bmap);
  return isl_local_space_alloc_div(isl_space_copy(bmap->dim), div);
}

__isl_give isl_local_space *isl_basic_set_get_local_space(
  __isl_keep isl_basic_set *bset)
{
  return isl_basic_map_get_local_space(bset);
}

/* For each known div d = floor(f/m), add the constraints
 *
 *    f - m d >= 0
 *    -(f-(m-1)) + m d >= 0
 *
 * Do not finalize the result.
 */
static __isl_give isl_basic_map *add_known_div_constraints(
  __isl_take isl_basic_map *bmap)
{
  int i;
  unsigned n_div;

  if (!bmap)
    return NULL;
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
  if (n_div == 0)
    return bmap;
  bmap = isl_basic_map_cow(bmap);
  bmap = isl_basic_map_extend_constraints(bmap, 0, 2 * n_div);
  if (!bmap)
    return NULL;
  for (i = 0; 35.3ki < n_div; ++i40.2k) {
    if (isl_int_is_zero(bmap->div[i][0]))
      continue421;
    if (isl_basic_map_add_div_constraints(bmap, i) < 0)
      return isl_basic_map_free(bmap);
  }

  return bmap;
}

__isl_give isl_basic_map *isl_basic_map_from_local_space(
  __isl_take isl_local_space *ls)
{
  int i;
  int n_div;
  isl_basic_map *bmap;

  if (!ls)
    return NULL;

  n_div = isl_local_space_dim(ls, isl_dim_div);
  bmap = isl_basic_map_alloc_space(isl_local_space_get_space(ls),
          n_div, 0, 2 * n_div);

  for (i = 0; i < n_div; ++i34.7k)
    if (isl_basic_map_alloc_div(bmap) < 0)
      goto error;

  for (i = 0; 141ki < n_div; ++i34.7k)
    isl_seq_cpy(bmap->div[i], ls->div->row[i], ls->div->n_col);
  bmap = add_known_div_constraints(bmap);
          
  isl_local_space_free(ls);
  return bmap;
error:
  isl_local_space_free(ls);
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_from_local_space(
  __isl_take isl_local_space *ls)
{
  return isl_basic_map_from_local_space(ls);
}

__isl_give isl_space *isl_map_get_space(__isl_keep isl_map *map)
{
  return isl_space_copy(isl_map_peek_space(map));
}

__isl_give isl_space *isl_set_get_space(__isl_keep isl_set *set)
{
  if (!set)
    return NULL;
  return isl_space_copy(set->dim);
}

__isl_give isl_basic_map *isl_basic_map_set_tuple_name(
  __isl_take isl_basic_map *bmap, enum isl_dim_type type, const char *s)
{
  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;
  bmap->dim = isl_space_set_tuple_name(bmap->dim, type, s);
  if (!bmap->dim)
    goto error;
  bmap = isl_basic_map_finalize(bmap);
  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_set_tuple_name(
  __isl_take isl_basic_set *bset, const char *s)
{
  return isl_basic_map_set_tuple_name(bset, isl_dim_set, s);
}

const char *isl_basic_map_get_tuple_name(__isl_keep isl_basic_map *bmap,
  enum isl_dim_type type)
{
  return bmap ? isl_space_get_tuple_name(bmap->dim, type) : NULL;
}

__isl_give isl_map *isl_map_set_tuple_name(__isl_take isl_map *map,
  enum isl_dim_type type, const char *s)
{
  int i;

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  map->dim = isl_space_set_tuple_name(map->dim, type, s);
  if (!map->dim)
    goto error;

  for (i = 0; i < map->n; ++i) {
    map->p[i] = isl_basic_map_set_tuple_name(map->p[i], type, s);
    if (!map->p[i])
      goto error;
  }

  return map;
error:
  isl_map_free(map);
  return NULL;
}

/* Replace the identifier of the tuple of type "type" by "id".
 */
__isl_give isl_basic_map *isl_basic_map_set_tuple_id(
  __isl_take isl_basic_map *bmap,
  enum isl_dim_type type, __isl_take isl_id *id)
{
  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    goto error;
  bmap->dim = isl_space_set_tuple_id(bmap->dim, type, id);
  if (!bmap->dim)
    return isl_basic_map_free(bmap);
  bmap = isl_basic_map_finalize(bmap);
  return bmap;
error:
  isl_id_free(id);
  return NULL;
}

/* Replace the identifier of the tuple by "id".
 */
__isl_give isl_basic_set *isl_basic_set_set_tuple_id(
  __isl_take isl_basic_set *bset, __isl_take isl_id *id)
{
  return isl_basic_map_set_tuple_id(bset, isl_dim_set, id);
}

/* Does the input or output tuple have a name?
 */
isl_bool isl_map_has_tuple_name(__isl_keep isl_map *map, enum isl_dim_type type)
{
  return map ? isl_space_has_tuple_name(map->dim, type) : isl_bool_error0;
}

const char *isl_map_get_tuple_name(__isl_keep isl_map *map,
  enum isl_dim_type type)
{
  return map ? isl_space_get_tuple_name(map->dim, type) : NULL;
}

__isl_give isl_set *isl_set_set_tuple_name(__isl_take isl_set *set,
  const char *s)
{
  return set_from_map(isl_map_set_tuple_name(set_to_map(set),
            isl_dim_set, s));
}

__isl_give isl_map *isl_map_set_tuple_id(__isl_take isl_map *map,
  enum isl_dim_type type, __isl_take isl_id *id)
{
  map = isl_map_cow(map);
  if (!map)
    goto error;

  map->dim = isl_space_set_tuple_id(map->dim, type, id);

  return isl_map_reset_space(map, isl_space_copy(map->dim));
error:
  isl_id_free(id);
  return NULL;
}

__isl_give isl_set *isl_set_set_tuple_id(__isl_take isl_set *set,
  __isl_take isl_id *id)
{
  return isl_map_set_tuple_id(set, isl_dim_set, id);
}

__isl_give isl_map *isl_map_reset_tuple_id(__isl_take isl_map *map,
  enum isl_dim_type type)
{
  map = isl_map_cow(map);
  if (!map)
    return NULL;

  map->dim = isl_space_reset_tuple_id(map->dim, type);

  return isl_map_reset_space(map, isl_space_copy(map->dim));
}

__isl_give isl_set *isl_set_reset_tuple_id(__isl_take isl_set *set)
{
  return isl_map_reset_tuple_id(set, isl_dim_set);
}

isl_bool isl_map_has_tuple_id(__isl_keep isl_map *map, enum isl_dim_type type)
{
  return map ? isl_space_has_tuple_id(map->dim, type) : isl_bool_error0;
}

__isl_give isl_id *isl_map_get_tuple_id(__isl_keep isl_map *map,
  enum isl_dim_type type)
{
  return map ? isl_space_get_tuple_id(map->dim, type)28.3k : NULL;
}

isl_bool isl_set_has_tuple_id(__isl_keep isl_set *set)
{
  return isl_map_has_tuple_id(set, isl_dim_set);
}

__isl_give isl_id *isl_set_get_tuple_id(__isl_keep isl_set *set)
{
  return isl_map_get_tuple_id(set, isl_dim_set);
}

/* Does the set tuple have a name?
 */
isl_bool isl_set_has_tuple_name(__isl_keep isl_set *set)
{
  if (!set)
    return isl_bool_error;
  return isl_space_has_tuple_name(set->dim, isl_dim_set);
}


const char *isl_basic_set_get_tuple_name(__isl_keep isl_basic_set *bset)
{
  return bset ? isl_space_get_tuple_name(bset->dim, isl_dim_set) : NULL;
}

const char *isl_set_get_tuple_name(__isl_keep isl_set *set)
{
  return set ? isl_space_get_tuple_name(set->dim, isl_dim_set) : NULL;
}

const char *isl_basic_map_get_dim_name(__isl_keep isl_basic_map *bmap,
  enum isl_dim_type type, unsigned pos)
{
  return bmap ? isl_space_get_dim_name(bmap->dim, type, pos) : NULL;
}

const char *isl_basic_set_get_dim_name(__isl_keep isl_basic_set *bset,
  enum isl_dim_type type, unsigned pos)
{
  return bset ? isl_space_get_dim_name(bset->dim, type, pos) : NULL;
}

/* Does the given dimension have a name?
 */
isl_bool isl_map_has_dim_name(__isl_keep isl_map *map,
  enum isl_dim_type type, unsigned pos)
{
  if (!map)
    return isl_bool_error;
  return isl_space_has_dim_name(map->dim, type, pos);
}

const char *isl_map_get_dim_name(__isl_keep isl_map *map,
  enum isl_dim_type type, unsigned pos)
{
  return map ? isl_space_get_dim_name(map->dim, type, pos) : NULL;
}

const char *isl_set_get_dim_name(__isl_keep isl_set *set,
  enum isl_dim_type type, unsigned pos)
{
  return set ? isl_space_get_dim_name(set->dim, type, pos) : NULL;
}

/* Does the given dimension have a name?
 */
isl_bool isl_set_has_dim_name(__isl_keep isl_set *set,
  enum isl_dim_type type, unsigned pos)
{
  if (!set)
    return isl_bool_error;
  return isl_space_has_dim_name(set->dim, type, pos);
}

__isl_give isl_basic_map *isl_basic_map_set_dim_name(
  __isl_take isl_basic_map *bmap,
  enum isl_dim_type type, unsigned pos, const char *s)
{
  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;
  bmap->dim = isl_space_set_dim_name(bmap->dim, type, pos, s);
  if (!bmap->dim)
    goto error;
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_map *isl_map_set_dim_name(__isl_take isl_map *map,
  enum isl_dim_type type, unsigned pos, const char *s)
{
  int i;

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  map->dim = isl_space_set_dim_name(map->dim, type, pos, s);
  if (!map->dim)
    goto error;

  for (i = 0; i < map->n; ++i) {
    map->p[i] = isl_basic_map_set_dim_name(map->p[i], type, pos, s);
    if (!map->p[i])
      goto error;
  }

  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_set_dim_name(
  __isl_take isl_basic_set *bset,
  enum isl_dim_type type, unsigned pos, const char *s)
{
  return bset_from_bmap(isl_basic_map_set_dim_name(bset_to_bmap(bset),
              type, pos, s));
}

__isl_give isl_set *isl_set_set_dim_name(__isl_take isl_set *set,
  enum isl_dim_type type, unsigned pos, const char *s)
{
  return set_from_map(isl_map_set_dim_name(set_to_map(set),
              type, pos, s));
}

isl_bool isl_basic_map_has_dim_id(__isl_keep isl_basic_map *bmap,
  enum isl_dim_type type, unsigned pos)
{
  if (!bmap)
    return isl_bool_error;
  return isl_space_has_dim_id(bmap->dim, type, pos);
}

__isl_give isl_id *isl_basic_set_get_dim_id(__isl_keep isl_basic_set *bset,
  enum isl_dim_type type, unsigned pos)
{
  return bset ? isl_space_get_dim_id(bset->dim, type, pos) : NULL;
}

isl_bool isl_map_has_dim_id(__isl_keep isl_map *map,
  enum isl_dim_type type, unsigned pos)
{
  return map ? isl_space_has_dim_id(map->dim, type, pos) : isl_bool_error;
}

__isl_give isl_id *isl_map_get_dim_id(__isl_keep isl_map *map,
  enum isl_dim_type type, unsigned pos)
{
  return map ? isl_space_get_dim_id(map->dim, type, pos) : NULL;
}

isl_bool isl_set_has_dim_id(__isl_keep isl_set *set,
  enum isl_dim_type type, unsigned pos)
{
  return isl_map_has_dim_id(set, type, pos);
}

__isl_give isl_id *isl_set_get_dim_id(__isl_keep isl_set *set,
  enum isl_dim_type type, unsigned pos)
{
  return isl_map_get_dim_id(set, type, pos);
}

__isl_give isl_map *isl_map_set_dim_id(__isl_take isl_map *map,
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
{
  map = isl_map_cow(map);
  if (!map)
    goto error;

  map->dim = isl_space_set_dim_id(map->dim, type, pos, id);

  return isl_map_reset_space(map, isl_space_copy(map->dim));
error:
  isl_id_free(id);
  return NULL;
}

__isl_give isl_set *isl_set_set_dim_id(__isl_take isl_set *set,
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
{
  return isl_map_set_dim_id(set, type, pos, id);
}

int isl_map_find_dim_by_id(__isl_keep isl_map *map, enum isl_dim_type type,
  __isl_keep isl_id *id)
{
  if (!map)
    return -1;
  return isl_space_find_dim_by_id(map->dim, type, id);
}

int isl_set_find_dim_by_id(__isl_keep isl_set *set, enum isl_dim_type type,
  __isl_keep isl_id *id)
{
  return isl_map_find_dim_by_id(set, type, id);
}

/* Return the position of the dimension of the given type and name
 * in "bmap".
 * Return -1 if no such dimension can be found.
 */
int isl_basic_map_find_dim_by_name(__isl_keep isl_basic_map *bmap,
  enum isl_dim_type type, const char *name)
{
  if (!bmap)
    return -1;
  return isl_space_find_dim_by_name(bmap->dim, type, name);
}

int isl_map_find_dim_by_name(__isl_keep isl_map *map, enum isl_dim_type type,
  const char *name)
{
  if (!map)
    return -1;
  return isl_space_find_dim_by_name(map->dim, type, name);
}

int isl_set_find_dim_by_name(__isl_keep isl_set *set, enum isl_dim_type type,
  const char *name)
{
  return isl_map_find_dim_by_name(set, type, name);
}

/* Check whether equality i of bset is a pure stride constraint
 * on a single dimension, i.e., of the form
 *
 *  v = k e
 *
 * with k a constant and e an existentially quantified variable.
 */
isl_bool isl_basic_set_eq_is_stride(__isl_keep isl_basic_set *bset, int i)
{
  unsigned nparam;
  unsigned d;
  unsigned n_div;
  int pos1;
  int pos2;

  if (!bset)
    return isl_bool_error;

  if (!isl_int_is_zero(bset->eq[i][0]))
    return isl_bool_false;

  nparam = isl_basic_set_dim(bset, isl_dim_param);
  d = isl_basic_set_dim(bset, isl_dim_set);
  n_div = isl_basic_set_dim(bset, isl_dim_div);

  if (isl_seq_first_non_zero(bset->eq[i] + 1, nparam) != -1)
    return isl_bool_false;
  pos1 = isl_seq_first_non_zero(bset->eq[i] + 1 + nparam, d);
  if (pos1 == -1)
    return isl_bool_false;
  if (isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + pos1 + 1,
          d - pos1 - 1) != -1)
    return isl_bool_false;

  pos2 = isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + d, n_div);
  if (pos2 == -1)
    return isl_bool_false;
  if (isl_seq_first_non_zero(bset->eq[i] + 1 + nparam + d  + pos2 + 1,
           n_div - pos2 - 1) != -1)
    return isl_bool_false;
  if (!isl_int_is_one(bset->eq[i][1 + nparam + pos1]) &&
      !isl_int_is_negone(bset->eq[i][1 + nparam + pos1]))
    return isl_bool_false;

  return isl_bool_true;
}

/* Reset the user pointer on all identifiers of parameters and tuples
 * of the space of "map".
 */
__isl_give isl_map *isl_map_reset_user(__isl_take isl_map *map)
{
  isl_space *space;

  space = isl_map_get_space(map);
  space = isl_space_reset_user(space);
  map = isl_map_reset_space(map, space);

  return map;
}

/* Reset the user pointer on all identifiers of parameters and tuples
 * of the space of "set".
 */
__isl_give isl_set *isl_set_reset_user(__isl_take isl_set *set)
{
  return isl_map_reset_user(set);
}

isl_bool isl_basic_map_is_rational(__isl_keep isl_basic_map *bmap)
{
  if (!bmap)
    return isl_bool_error;
  return ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL);
}

/* Has "map" been marked as a rational map?
 * In particular, have all basic maps in "map" been marked this way?
 * An empty map is not considered to be rational.
 * Maps where only some of the basic maps are marked rational
 * are not allowed.
 */
isl_bool isl_map_is_rational(__isl_keep isl_map *map)
{
  int i;
  isl_bool rational;

  if (!map)
    return isl_bool_error;
  if (map->n == 0)
    return isl_bool_false;
  rational = isl_basic_map_is_rational(map->p[0]);
  if (rational < 0)
    return rational;
  for (i = 1; 9.38ki < map->n; ++i929) {
    isl_bool rational_i;

    rational_i = isl_basic_map_is_rational(map->p[i]);
    if (rational_i < 0)
      return rational_i;
    if (rational != rational_i)
      isl_die0(isl_map_get_ctx(map), isl_error_unsupported,
        "mixed rational and integer basic maps "
        "not supported", return isl_bool_error);
  }

  return rational;
}

/* Has "set" been marked as a rational set?
 * In particular, have all basic set in "set" been marked this way?
 * An empty set is not considered to be rational.
 * Sets where only some of the basic sets are marked rational
 * are not allowed.
 */
isl_bool isl_set_is_rational(__isl_keep isl_set *set)
{
  return isl_map_is_rational(set);
}

int isl_basic_set_is_rational(__isl_keep isl_basic_set *bset)
{
  return isl_basic_map_is_rational(bset);
}

/* Does "bmap" contain any rational points?
 *
 * If "bmap" has an equality for each dimension, equating the dimension
 * to an integer constant, then it has no rational points, even if it
 * is marked as rational.
 */
isl_bool isl_basic_map_has_rational(__isl_keep isl_basic_map *bmap)
{
  isl_bool has_rational = isl_bool_true;
  unsigned total;

  if (!bmap)
    return isl_bool_error;
  if (isl_basic_map_plain_is_empty(bmap))
    return isl_bool_false;
  if (!isl_basic_map_is_rational(bmap))
    return isl_bool_false;
  bmap = isl_basic_map_copy(bmap);
  bmap = isl_basic_map_implicit_equalities(bmap);
  if (!bmap)
    return isl_bool_error;
  total = isl_basic_map_total_dim(bmap);
  if (bmap->n_eq == total) {
    int i, j;
    for (i = 0; i < bmap->n_eq; ++i1) {
      j = isl_seq_first_non_zero(bmap->eq[i] + 1, total);
      if (j < 0)
        break;
      if (!isl_int_is_one(bmap->eq[i][1 + j]) &&
          !1isl_int_is_negone1(bmap->eq[i][1 + j]))
        break1;
      j = isl_seq_first_non_zero(bmap->eq[i] + 1 + j + 1,
                total - j - 1);
      if (j >= 0)
        break;
    }
    if (i == bmap->n_eq)
      has_rational = isl_bool_false;
  }
  isl_basic_map_free(bmap);

  return has_rational;
}

/* Does "map" contain any rational points?
 */
isl_bool isl_map_has_rational(__isl_keep isl_map *map)
{
  int i;
  isl_bool has_rational;

  if (!map)
    return isl_bool_error;
  for (i = 0; 80.5ki < map->n; ++i95.1k) {
    has_rational = isl_basic_map_has_rational(map->p[i]);
    if (has_rational < 0 || has_rational)
      return has_rational;
  }
  return isl_bool_false80.2k;
}

/* Does "set" contain any rational points?
 */
isl_bool isl_set_has_rational(__isl_keep isl_set *set)
{
  return isl_map_has_rational(set);
}

/* Is this basic set a parameter domain?
 */
isl_bool isl_basic_set_is_params(__isl_keep isl_basic_set *bset)
{
  if (!bset)
    return isl_bool_error;
  return isl_space_is_params(bset->dim);
}

/* Is this set a parameter domain?
 */
isl_bool isl_set_is_params(__isl_keep isl_set *set)
{
  if (!set)
    return isl_bool_error;
  return isl_space_is_params(set->dim);
}

/* Is this map actually a parameter domain?
 * Users should never call this function.  Outside of isl,
 * a map can never be a parameter domain.
 */
isl_bool isl_map_is_params(__isl_keep isl_map *map)
{
  if (!map)
    return isl_bool_error;
  return isl_space_is_params(map->dim);
}

static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
    struct isl_basic_map *bmap, unsigned extra,
    unsigned n_eq, unsigned n_ineq)
{
  int i;
  size_t row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + extra;

  bmap->ctx = ctx;
  isl_ctx_ref(ctx);

  bmap->block = isl_blk_alloc(ctx, (n_ineq + n_eq) * row_size);
  if (isl_blk_is_error(bmap->block))
    goto error;

  bmap->ineq = isl_alloc_array(ctx, isl_int *, n_ineq + n_eq);
  if ((n_ineq + n_eq) && !bmap->ineq5.39M)
    goto error;

  if (extra == 0) {
    bmap->block2 = isl_blk_empty();
    bmap->div = NULL;
  } else {
    bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
    if (isl_blk_is_error(bmap->block2))
      goto error;

    bmap->div = isl_alloc_array(ctx, isl_int *, extra);
    if (!bmap->div)
      goto error;
  }

  for (i = 0; 6.98Mi < n_ineq + n_eq; ++i48.0M)
    bmap->ineq[i] = bmap->block.data + i * row_size;

  for (i = 0; i < extra; ++i645k)
    bmap->div[i] = bmap->block2.data + i * (1 + row_size);

  bmap->ref = 1;
  bmap->flags = 0;
  bmap->c_size = n_eq + n_ineq;
  bmap->eq = bmap->ineq + n_ineq;
  bmap->extra = extra;
  bmap->n_eq = 0;
  bmap->n_ineq = 0;
  bmap->n_div = 0;
  bmap->sample = NULL;

  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
    unsigned nparam, unsigned dim, unsigned extra,
    unsigned n_eq, unsigned n_ineq)
{
  struct isl_basic_map *bmap;
  isl_space *space;

  space = isl_space_set_alloc(ctx, nparam, dim);
  if (!space)
    return NULL;

  bmap = isl_basic_map_alloc_space(space, extra, n_eq, n_ineq);
  return bset_from_bmap(bmap);
}

__isl_give isl_basic_set *isl_basic_set_alloc_space(__isl_take isl_space *dim,
    unsigned extra, unsigned n_eq, unsigned n_ineq)
{
  struct isl_basic_map *bmap;
  if (!dim)
    return NULL;
  isl_assert(dim->ctx, dim->n_in == 0, goto error);
  bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
  return bset_from_bmap(bmap);
error:
  isl_space_free(dim);
  return NULL;
}

struct isl_basic_map *isl_basic_map_alloc_space(__isl_take isl_space *dim,
    unsigned extra, unsigned n_eq, unsigned n_ineq)
{
  struct isl_basic_map *bmap;

  if (!dim)
    return NULL;
  bmap = isl_calloc_type(dim->ctx, struct isl_basic_map);
  if (!bmap)
    goto error;
  bmap->dim = dim;

  return basic_map_init(dim->ctx, bmap, extra, n_eq, n_ineq);
error:
  isl_space_free(dim);
  return NULL;
}

struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
    unsigned nparam, unsigned in, unsigned out, unsigned extra,
    unsigned n_eq, unsigned n_ineq)
{
  struct isl_basic_map *bmap;
  isl_space *dim;

  dim = isl_space_alloc(ctx, nparam, in, out);
  if (!dim)
    return NULL;

  bmap = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
  return bmap;
}

static void dup_constraints(
    struct isl_basic_map *dst, struct isl_basic_map *src)
{
  int i;
  unsigned total = isl_basic_map_total_dim(src);

  for (i = 0; i < src->n_eq; ++i3.43M) {
    int j = isl_basic_map_alloc_equality(dst);
    isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
  }

  for (i = 0; i < src->n_ineq; ++i24.5M) {
    int j = isl_basic_map_alloc_inequality(dst);
    isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
  }

  for (i = 0; i < src->n_div; ++i140k) {
    int j = isl_basic_map_alloc_div(dst);
    isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
  }
  ISL_F_SET(dst, ISL_BASIC_SET_FINAL);
}

__isl_give isl_basic_map *isl_basic_map_dup(__isl_keep isl_basic_map *bmap)
{
  struct isl_basic_map *dup;

  if (!bmap)
    return NULL;
  dup = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
  if (!dup)
    return NULL;
  dup_constraints(dup, bmap);
  dup->flags = bmap->flags;
  dup->sample = isl_vec_copy(bmap->sample);
  return dup;
}

struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
{
  struct isl_basic_map *dup;

  dup = isl_basic_map_dup(bset_to_bmap(bset));
  return bset_from_bmap(dup);
}

__isl_give isl_basic_set *isl_basic_set_copy(__isl_keep isl_basic_set *bset)
{
  if (!bset)
    return NULL;

  if (ISL_F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
    bset->ref++;
    return bset;
  }
  return isl_basic_set_dup(bset);
}

__isl_give isl_set *isl_set_copy(__isl_keep isl_set *set)
{
  if (!set)
    return NULL;

  set->ref++;
  return set;
}

__isl_give isl_basic_map *isl_basic_map_copy(__isl_keep isl_basic_map *bmap)
{
  if (!bmap)
    return NULL;

  if (ISL_F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
    bmap->ref++;
    return bmap;
  }
  bmap = isl_basic_map_dup(bmap);
  if (bmap)
    ISL_F_SET(bmap, ISL_BASIC_SET_FINAL);
  return bmap;
}

__isl_give isl_map *isl_map_copy(__isl_keep isl_map *map)
{
  if (!map)
    return NULL;

  map->ref++;
  return map;
}

__isl_null isl_basic_map *isl_basic_map_free(__isl_take isl_basic_map *bmap)
{
  if (!bmap)
    return NULL;

  if (--bmap->ref > 0)
    return NULL;

  isl_ctx_deref(bmap->ctx);
  free(bmap->div);
  isl_blk_free(bmap->ctx, bmap->block2);
  free(bmap->ineq);
  isl_blk_free(bmap->ctx, bmap->block);
  isl_vec_free(bmap->sample);
  isl_space_free(bmap->dim);
  free(bmap);

  return NULL;
}

__isl_null isl_basic_set *isl_basic_set_free(__isl_take isl_basic_set *bset)
{
  return isl_basic_map_free(bset_to_bmap(bset));
}

static int room_for_con(struct isl_basic_map *bmap, unsigned n)
{
  return bmap->n_eq + bmap->n_ineq + n <= bmap->c_size;
}

/* Check that "map" has only named parameters, reporting an error
 * if it does not.
 */
isl_stat isl_map_check_named_params(__isl_keep isl_map *map)
{
  return isl_space_check_named_params(isl_map_peek_space(map));
}

/* Check that "bmap" has only named parameters, reporting an error
 * if it does not.
 */
static isl_stat isl_basic_map_check_named_params(__isl_keep isl_basic_map *bmap)
{
  return isl_space_check_named_params(isl_basic_map_peek_space(bmap));
}

/* Check that "bmap1" and "bmap2" have the same parameters,
 * reporting an error if they do not.
 */
static isl_stat isl_basic_map_check_equal_params(
  __isl_keep isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2)
{
  isl_bool match;

  match = isl_basic_map_has_equal_params(bmap1, bmap2);
  if (match < 0)
    return isl_stat_error;
  if (!match)
    isl_die0(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
      "parameters don't match", return isl_stat_error);
  return isl_stat_ok;
}

__isl_give isl_map *isl_map_align_params_map_map_and(
  __isl_take isl_map *map1, __isl_take isl_map *map2,
  __isl_give isl_map *(*fn)(__isl_take isl_map *map1,
            __isl_take isl_map *map2))
{
  if (!map1 || !map21.07M)
    goto error;
  if (isl_map_has_equal_params(map1, map2))
    return fn(map1, map2);
  if (isl_map_check_named_params(map1) < 0)
    goto error;
  if (isl_map_check_named_params(map2) < 0)
    goto error;
  map1 = isl_map_align_params(map1, isl_map_get_space(map2));
  map2 = isl_map_align_params(map2, isl_map_get_space(map1));
  return fn(map1, map2);
error:
  isl_map_free(map1);
  isl_map_free(map2);
  return NULL;
}

isl_bool isl_map_align_params_map_map_and_test(__isl_keep isl_map *map1,
  __isl_keep isl_map *map2,
  isl_bool (*fn)(__isl_keep isl_map *map1, __isl_keep isl_map *map2))
{
  isl_bool r;

  if (!map1 || !map2)
    return isl_bool_error;
  if (isl_map_has_equal_params(map1, map2))
    return fn(map1, map2);
  if (isl_map_check_named_params(map1) < 0)
    return isl_bool_error;
  if (isl_map_check_named_params(map2) < 0)
    return isl_bool_error;
  map1 = isl_map_copy(map1);
  map2 = isl_map_copy(map2);
  map1 = isl_map_align_params(map1, isl_map_get_space(map2));
  map2 = isl_map_align_params(map2, isl_map_get_space(map1));
  r = fn(map1, map2);
  isl_map_free(map1);
  isl_map_free(map2);
  return r;
}

int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
{
  struct isl_ctx *ctx;
  if (!bmap)
    return -1;
  ctx = bmap->ctx;
  isl_assert(ctx, room_for_con(bmap, 1), return -1);
  isl_assert(ctx, (bmap->eq - bmap->ineq) + bmap->n_eq <= bmap->c_size,
      return -1);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
  if ((bmap->eq - bmap->ineq) + bmap->n_eq == bmap->c_size) {
    isl_int *t;
    int j = isl_basic_map_alloc_inequality(bmap);
    if (j < 0)
      return -1;
    t = bmap->ineq[j];
    bmap->ineq[j] = bmap->ineq[bmap->n_ineq - 1];
    bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
    bmap->eq[-1] = t;
    bmap->n_eq++;
    bmap->n_ineq--;
    bmap->eq--;
    return 0;
  }
  isl_seq_clr(bmap->eq[bmap->n_eq] + 1 + isl_basic_map_total_dim(bmap),
          bmap->extra - bmap->n_div);
  return bmap->n_eq++;
}

int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
{
  return isl_basic_map_alloc_equality(bset_to_bmap(bset));
}

int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
{
  if (!bmap)
    return -1;
  isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
  bmap->n_eq -= n;
  return 0;
}

int isl_basic_set_free_equality(struct isl_basic_set *bset, unsigned n)
{
  return isl_basic_map_free_equality(bset_to_bmap(bset), n);
}

int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
{
  isl_int *t;
  if (!bmap)
    return -1;
  isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);

  if (pos != bmap->n_eq - 1) {
    t = bmap->eq[pos];
    bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
    bmap->eq[bmap->n_eq - 1] = t;
  }
  bmap->n_eq--;
  return 0;
}

/* Turn inequality "pos" of "bmap" into an equality.
 *
 * In particular, we move the inequality in front of the equalities
 * and move the last inequality in the position of the moved inequality.
 * Note that isl_tab_make_equalities_explicit depends on this particular
 * change in the ordering of the constraints.
 */
void isl_basic_map_inequality_to_equality(
    struct isl_basic_map *bmap, unsigned pos)
{
  isl_int *t;

  t = bmap->ineq[pos];
  bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
  bmap->ineq[bmap->n_ineq - 1] = bmap->eq[-1];
  bmap->eq[-1] = t;
  bmap->n_eq++;
  bmap->n_ineq--;
  bmap->eq--;
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
}

static int room_for_ineq(struct isl_basic_map *bmap, unsigned n)
{
  return bmap->n_ineq + n <= bmap->eq - bmap->ineq;
}

int isl_basic_map_alloc_inequality(__isl_keep isl_basic_map *bmap)
{
  struct isl_ctx *ctx;
  if (!bmap)
    return -1;
  ctx = bmap->ctx;
  isl_assert(ctx, room_for_ineq(bmap, 1), return -1);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_ALL_EQUALITIES);
  isl_seq_clr(bmap->ineq[bmap->n_ineq] +
          1 + isl_basic_map_total_dim(bmap),
          bmap->extra - bmap->n_div);
  return bmap->n_ineq++;
}

int isl_basic_set_alloc_inequality(__isl_keep isl_basic_set *bset)
{
  return isl_basic_map_alloc_inequality(bset_to_bmap(bset));
}

int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
{
  if (!bmap)
    return -1;
  isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
  bmap->n_ineq -= n;
  return 0;
}

int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
{
  return isl_basic_map_free_inequality(bset_to_bmap(bset), n);
}

int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
{
  isl_int *t;
  if (!bmap)
    return -1;
  isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);

  if (pos != bmap->n_ineq - 1) {
    t = bmap->ineq[pos];
    bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
    bmap->ineq[bmap->n_ineq - 1] = t;
    ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  }
  bmap->n_ineq--;
  return 0;
}

int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
{
  return isl_basic_map_drop_inequality(bset_to_bmap(bset), pos);
}

__isl_give isl_basic_map *isl_basic_map_add_eq(__isl_take isl_basic_map *bmap,
  isl_int *eq)
{
  int k;

  bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
  if (!bmap)
    return NULL;
  k = isl_basic_map_alloc_equality(bmap);
  if (k < 0)
    goto error;
  isl_seq_cpy(bmap->eq[k], eq, 1 + isl_basic_map_total_dim(bmap));
  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_add_eq(__isl_take isl_basic_set *bset,
  isl_int *eq)
{
  return bset_from_bmap(isl_basic_map_add_eq(bset_to_bmap(bset), eq));
}

__isl_give isl_basic_map *isl_basic_map_add_ineq(__isl_take isl_basic_map *bmap,
  isl_int *ineq)
{
  int k;

  bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
  if (!bmap)
    return NULL;
  k = isl_basic_map_alloc_inequality(bmap);
  if (k < 0)
    goto error;
  isl_seq_cpy(bmap->ineq[k], ineq, 1 + isl_basic_map_total_dim(bmap));
  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_add_ineq(__isl_take isl_basic_set *bset,
  isl_int *ineq)
{
  return bset_from_bmap(isl_basic_map_add_ineq(bset_to_bmap(bset), ineq));
}

int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
{
  if (!bmap)
    return -1;
  isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
  isl_seq_clr(bmap->div[bmap->n_div] +
          1 + 1 + isl_basic_map_total_dim(bmap),
          bmap->extra - bmap->n_div);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED_DIVS);
  return bmap->n_div++;
}

int isl_basic_set_alloc_div(struct isl_basic_set *bset)
{
  return isl_basic_map_alloc_div(bset_to_bmap(bset));
}

/* Check that there are "n" dimensions of type "type" starting at "first"
 * in "bmap".
 */
static isl_stat isl_basic_map_check_range(__isl_keep isl_basic_map *bmap,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  unsigned dim;

  if (!bmap)
    return isl_stat_error;
  dim = isl_basic_map_dim(bmap, type);
  if (first + n > dim || first + n < first)
    isl_die0(isl_basic_map_get_ctx(bmap), isl_error_invalid,
      "position or range out of bounds",
      return isl_stat_error);
  return isl_stat_ok;
}

/* Insert an extra integer division, prescribed by "div", to "bmap"
 * at (integer division) position "pos".
 *
 * The integer division is first added at the end and then moved
 * into the right position.
 */
__isl_give isl_basic_map *isl_basic_map_insert_div(
  __isl_take isl_basic_map *bmap, int pos, __isl_keep isl_vec *div)
{
  int i, k;

  bmap = isl_basic_map_cow(bmap);
  if (!bmap || !div)
    return isl_basic_map_free(bmap);

  if (div->size != 1 + 1 + isl_basic_map_dim(bmap, isl_dim_all))
    isl_die0(isl_basic_map_get_ctx(bmap), isl_error_invalid,
      "unexpected size", return isl_basic_map_free(bmap));
  if (isl_basic_map_check_range(bmap, isl_dim_div, pos, 0) < 0)
    return isl_basic_map_free(bmap);

  bmap = isl_basic_map_extend_space(bmap,
          isl_basic_map_get_space(bmap), 1, 0, 2);
  k = isl_basic_map_alloc_div(bmap);
  if (k < 0)
    return isl_basic_map_free(bmap);
  isl_seq_cpy(bmap->div[k], div->el, div->size);
  isl_int_set_si(bmap->div[k][div->size], 0);

  for (i = k; i > pos; --i486)
    isl_basic_map_swap_div(bmap, i, i - 1);

  return bmap;
}

isl_stat isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
{
  if (!bmap)
    return isl_stat_error;
  isl_assert(bmap->ctx, n <= bmap->n_div, return isl_stat_error);
  bmap->n_div -= n;
  return isl_stat_ok;
}

/* Copy constraint from src to dst, putting the vars of src at offset
 * dim_off in dst and the divs of src at offset div_off in dst.
 * If both sets are actually map, then dim_off applies to the input
 * variables.
 */
static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
          struct isl_basic_map *src_map, isl_int *src,
          unsigned in_off, unsigned out_off, unsigned div_off)
{
  unsigned src_nparam = isl_basic_map_dim(src_map, isl_dim_param);
  unsigned dst_nparam = isl_basic_map_dim(dst_map, isl_dim_param);
  unsigned src_in = isl_basic_map_dim(src_map, isl_dim_in);
  unsigned dst_in = isl_basic_map_dim(dst_map, isl_dim_in);
  unsigned src_out = isl_basic_map_dim(src_map, isl_dim_out);
  unsigned dst_out = isl_basic_map_dim(dst_map, isl_dim_out);
  isl_int_set(dst[0], src[0]);
  isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
  if (dst_nparam > src_nparam)
    isl_seq_clr(dst+1+src_nparam,
        dst_nparam - src_nparam);
  isl_seq_clr(dst+1+dst_nparam, in_off);
  isl_seq_cpy(dst+1+dst_nparam+in_off,
        src+1+src_nparam,
        isl_min(dst_in-in_off, src_in));
  if (dst_in-in_off > src_in)
    isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
        dst_in - in_off - src_in);
  isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
  isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
        src+1+src_nparam+src_in,
        isl_min(dst_out-out_off, src_out));
  if (dst_out-out_off > src_out)
    isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
        dst_out - out_off - src_out);
  isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
  isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
        src+1+src_nparam+src_in+src_out,
        isl_min(dst_map->extra-div_off, src_map->n_div));
  if (dst_map->n_div-div_off > src_map->n_div)
    isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
        div_off+src_map->n_div,
        dst_map->n_div - div_off - src_map->n_div);
}

static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
         struct isl_basic_map *src_map, isl_int *src,
         unsigned in_off, unsigned out_off, unsigned div_off)
{
  isl_int_set(dst[0], src[0]);
  copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
}

static __isl_give isl_basic_map *add_constraints(
  __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2,
  unsigned i_pos, unsigned o_pos)
{
  int i;
  unsigned div_off;

  if (!bmap1 || !bmap21.80M)
    goto error;

  div_off = bmap1->n_div;

  for (i = 0; i < bmap2->n_eq; ++i1.79M) {
    int i1 = isl_basic_map_alloc_equality(bmap1);
    if (i1 < 0)
      goto error;
    copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
        i_pos, o_pos, div_off);
  }

  for (i = 0; 1.80Mi < bmap2->n_ineq; ++i9.11M) {
    int i1 = isl_basic_map_alloc_inequality(bmap1);
    if (i1 < 0)
      goto error;
    copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
        i_pos, o_pos, div_off);
  }

  for (i = 0; 1.80Mi < bmap2->n_div; ++i162k) {
    int i1 = isl_basic_map_alloc_div(bmap1);
    if (i1 < 0)
      goto error;
    copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
       i_pos, o_pos, div_off);
  }

  isl_basic_map_free(bmap2);

  return bmap1;

error:
  isl_basic_map_free(bmap1);
  isl_basic_map_free(bmap2);
  return NULL;
}

struct isl_basic_set *isl_basic_set_add_constraints(struct isl_basic_set *bset1,
    struct isl_basic_set *bset2, unsigned pos)
{
  return bset_from_bmap(add_constraints(bset_to_bmap(bset1),
            bset_to_bmap(bset2), 0, pos));
}

__isl_give isl_basic_map *isl_basic_map_extend_space(
  __isl_take isl_basic_map *base, __isl_take isl_space *dim,
  unsigned extra, unsigned n_eq, unsigned n_ineq)
{
  struct isl_basic_map *ext;
  unsigned flags;
  int dims_ok;

  if (!dim)
    goto error;

  if (!base)
    goto error;

  dims_ok = isl_space_is_equal(base->dim, dim) &&
      base->extra >= base->n_div + extra1.70M;

  if (dims_ok && room_for_con(base, n_eq + n_ineq)1.67M &&
           room_for_ineq(base, n_ineq)781k) {
    isl_space_free(dim);
    return base;
  }

  isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
  isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
  isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
  extra += base->extra;
  n_eq += base->n_eq;
  n_ineq += base->n_ineq;

  ext = isl_basic_map_alloc_space(dim, extra, n_eq, n_ineq);
  dim = NULL;
  if (!ext)
    goto error;

  if (dims_ok)
    ext->sample = isl_vec_copy(base->sample);
  flags = base->flags;
  ext = add_constraints(ext, base, 0, 0);
  if (ext) {
    ext->flags = flags;
    ISL_F_CLR(ext, ISL_BASIC_SET_FINAL);
  }

  return ext;

error:
  isl_space_free(dim);
  isl_basic_map_free(base);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_extend_space(
  __isl_take isl_basic_set *base,
    __isl_take isl_space *dim, unsigned extra,
    unsigned n_eq, unsigned n_ineq)
{
  return bset_from_bmap(isl_basic_map_extend_space(bset_to_bmap(base),
                dim, extra, n_eq, n_ineq));
}

struct isl_basic_map *isl_basic_map_extend_constraints(
    struct isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
{
  if (!base)
    return NULL;
  return isl_basic_map_extend_space(base, isl_space_copy(base->dim),
          0, n_eq, n_ineq);
}

struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
    unsigned nparam, unsigned n_in, unsigned n_out, unsigned extra,
    unsigned n_eq, unsigned n_ineq)
{
  struct isl_basic_map *bmap;
  isl_space *dim;

  if (!base)
    return NULL;
  dim = isl_space_alloc(base->ctx, nparam, n_in, n_out);
  if (!dim)
    goto error;

  bmap = isl_basic_map_extend_space(base, dim, extra, n_eq, n_ineq);
  return bmap;
error:
  isl_basic_map_free(base);
  return NULL;
}

struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base,
    unsigned nparam, unsigned dim, unsigned extra,
    unsigned n_eq, unsigned n_ineq)
{
  return bset_from_bmap(isl_basic_map_extend(bset_to_bmap(base),
          nparam, 0, dim, extra, n_eq, n_ineq));
}

struct isl_basic_set *isl_basic_set_extend_constraints(
    struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
{
  isl_basic_map *bmap = bset_to_bmap(base);
  bmap = isl_basic_map_extend_constraints(bmap, n_eq, n_ineq);
  return bset_from_bmap(bmap);
}

__isl_give isl_basic_set *isl_basic_set_cow(__isl_take isl_basic_set *bset)
{
  return bset_from_bmap(isl_basic_map_cow(bset_to_bmap(bset)));
}

__isl_give isl_basic_map *isl_basic_map_cow(__isl_take isl_basic_map *bmap)
{
  if (!bmap)
    return NULL;

  if (bmap->ref > 1) {
    bmap->ref--;
    bmap = isl_basic_map_dup(bmap);
  }
  if (bmap) {
    ISL_F_CLR(bmap, ISL_BASIC_SET_FINAL);
    ISL_F_CLR(bmap, ISL_BASIC_MAP_REDUCED_COEFFICIENTS);
  }
  return bmap;
}

/* Clear all cached information in "map", either because it is about
 * to be modified or because it is being freed.
 * Always return the same pointer that is passed in.
 * This is needed for the use in isl_map_free.
 */
static __isl_give isl_map *clear_caches(__isl_take isl_map *map)
{
  isl_basic_map_free(map->cached_simple_hull[0]);
  isl_basic_map_free(map->cached_simple_hull[1]);
  map->cached_simple_hull[0] = NULL;
  map->cached_simple_hull[1] = NULL;
  return map;
}

__isl_give isl_set *isl_set_cow(__isl_take isl_set *set)
{
  return isl_map_cow(set);
}

/* Return an isl_map that is equal to "map" and that has only
 * a single reference.
 *
 * If the original input already has only one reference, then
 * simply return it, but clear all cached information, since
 * it may be rendered invalid by the operations that will be
 * performed on the result.
 *
 * Otherwise, create a duplicate (without any cached information).
 */
__isl_give isl_map *isl_map_cow(__isl_take isl_map *map)
{
  if (!map)
    return NULL;

  if (map->ref == 1)
    return clear_caches(map);
  map->ref--;
  return isl_map_dup(map);
}

static void swap_vars(struct isl_blk blk, isl_int *a,
      unsigned a_len, unsigned b_len)
{
  isl_seq_cpy(blk.data, a+a_len, b_len);
  isl_seq_cpy(blk.data+b_len, a, a_len);
  isl_seq_cpy(a, blk.data, b_len+a_len);
}

static __isl_give isl_basic_map *isl_basic_map_swap_vars(
  __isl_take isl_basic_map *bmap, unsigned pos, unsigned n1, unsigned n2)
{
  int i;
  struct isl_blk blk;

  if (!bmap)
    goto error;

  isl_assert(bmap->ctx,
    pos + n1 + n2 <= 1 + isl_basic_map_total_dim(bmap), goto error);

  if (n1 == 0 || n2 == 075.4k)
    return bmap;

  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;

  blk = isl_blk_alloc(bmap->ctx, n1 + n2);
  if (isl_blk_is_error(blk))
    goto error;

  for (i = 0; 67.9ki < bmap->n_eq; ++i202k)
    swap_vars(blk,
        bmap->eq[i] + pos, n1, n2);

  for (i = 0; i < bmap->n_ineq; ++i212k)
    swap_vars(blk,
        bmap->ineq[i] + pos, n1, n2);

  for (i = 0; i < bmap->n_div; ++i4.26k)
    swap_vars(blk,
        bmap->div[i]+1 + pos, n1, n2);

  isl_blk_free(bmap->ctx, blk);

  ISL_F_CLR(bmap, ISL_BASIC_SET_NORMALIZED);
  bmap = isl_basic_map_gauss(bmap, NULL);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_map *isl_basic_map_set_to_empty(
  __isl_take isl_basic_map *bmap)
{
  int i = 0;
  unsigned total;
  if (!bmap)
    goto error;
  total = isl_basic_map_total_dim(bmap);
  if (isl_basic_map_free_div(bmap, bmap->n_div) < 0)
    return isl_basic_map_free(bmap);
  isl_basic_map_free_inequality(bmap, bmap->n_ineq);
  if (bmap->n_eq > 0)
    isl_basic_map_free_equality(bmap, bmap->n_eq-1);
  else {
    i = isl_basic_map_alloc_equality(bmap);
    if (i < 0)
      goto error;
  }
  isl_int_set_si(bmap->eq[i][0], 1);
  isl_seq_clr(bmap->eq[i]+1, total);
  ISL_F_SET(bmap, ISL_BASIC_MAP_EMPTY);
  isl_vec_free(bmap->sample);
  bmap->sample = NULL;
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_set_to_empty(
  __isl_take isl_basic_set *bset)
{
  return bset_from_bmap(isl_basic_map_set_to_empty(bset_to_bmap(bset)));
}

__isl_give isl_basic_map *isl_basic_map_set_rational(
  __isl_take isl_basic_map *bmap)
{
  if (!bmap)
    return NULL;

  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
    return bmap53.9k;

  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;

  ISL_F_SET(bmap, ISL_BASIC_MAP_RATIONAL);

  return isl_basic_map_finalize(bmap);
}

__isl_give isl_basic_set *isl_basic_set_set_rational(
  __isl_take isl_basic_set *bset)
{
  return isl_basic_map_set_rational(bset);
}

__isl_give isl_basic_set *isl_basic_set_set_integral(
  __isl_take isl_basic_set *bset)
{
  if (!bset)
    return NULL;

  if (!ISL_F_ISSET(bset, ISL_BASIC_MAP_RATIONAL))
    return bset0;

  bset = isl_basic_set_cow(bset);
  if (!bset)
    return NULL;

  ISL_F_CLR(bset, ISL_BASIC_MAP_RATIONAL);

  return isl_basic_set_finalize(bset);
}

__isl_give isl_map *isl_map_set_rational(__isl_take isl_map *map)
{
  int i;

  map = isl_map_cow(map);
  if (!map)
    return NULL;
  for (i = 0; 35.7ki < map->n; ++i62.7k) {
    map->p[i] = isl_basic_map_set_rational(map->p[i]);
    if (!map->p[i])
      goto error;
  }
  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_set *isl_set_set_rational(__isl_take isl_set *set)
{
  return isl_map_set_rational(set);
}

/* Swap divs "a" and "b" in "bmap" (without modifying any of the constraints
 * of "bmap").
 */
static void swap_div(__isl_keep isl_basic_map *bmap, int a, int b)
{
  isl_int *t = bmap->div[a];
  bmap->div[a] = bmap->div[b];
  bmap->div[b] = t;
}

/* Swap divs "a" and "b" in "bmap" and adjust the constraints and
 * div definitions accordingly.
 */
void isl_basic_map_swap_div(struct isl_basic_map *bmap, int a, int b)
{
  int i;
  unsigned off = isl_space_dim(bmap->dim, isl_dim_all);

  swap_div(bmap, a, b);

  for (i = 0; i < bmap->n_eq; ++i56.9k)
    isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);

  for (i = 0; i < bmap->n_ineq; ++i113k)
    isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);

  for (i = 0; i < bmap->n_div; ++i50.7k)
    isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
}

/* Swap divs "a" and "b" in "bset" and adjust the constraints and
 * div definitions accordingly.
 */
void isl_basic_set_swap_div(__isl_keep isl_basic_set *bset, int a, int b)
{
  isl_basic_map_swap_div(bset, a, b);
}

static void constraint_drop_vars(isl_int *c, unsigned n, unsigned rem)
{
  isl_seq_cpy(c, c + n, rem);
  isl_seq_clr(c + rem, n);
}

/* Drop n dimensions starting at first.
 *
 * In principle, this frees up some extra variables as the number
 * of columns remains constant, but we would have to extend
 * the div array too as the number of rows in this array is assumed
 * to be equal to extra.
 */
__isl_give isl_basic_set *isl_basic_set_drop_dims(
  __isl_take isl_basic_set *bset, unsigned first, unsigned n)
{
  return isl_basic_map_drop(bset_to_bmap(bset), isl_dim_set, first, n);
}

/* Move "n" divs starting at "first" to the end of the list of divs.
 */
static struct isl_basic_map *move_divs_last(struct isl_basic_map *bmap,
  unsigned first, unsigned n)
{
  isl_int **div;
  int i;

  if (first + n == bmap->n_div)
    return bmap;

  div = isl_alloc_array(bmap->ctx, isl_int *, n);
  if (!div)
    goto error;
  for (i = 0; 103i < n; ++i103)
    div[i] = bmap->div[first + i];
  for (i = 0; i < bmap->n_div - first - n; ++i163)
    bmap->div[first + i] = bmap->div[first + n + i];
  for (i = 0; i < n; ++i103)
    bmap->div[bmap->n_div - n + i] = div[i];
  free(div);
  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

/* Check that there are "n" dimensions of type "type" starting at "first"
 * in "map".
 */
static isl_stat isl_map_check_range(__isl_keep isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  if (!map)
    return isl_stat_error;
  if (first + n > isl_map_dim(map, type) || first + n < first)
    isl_die0(isl_map_get_ctx(map), isl_error_invalid,
      "position or range out of bounds",
      return isl_stat_error);
  return isl_stat_ok;
}

/* Drop "n" dimensions of type "type" starting at "first".
 *
 * In principle, this frees up some extra variables as the number
 * of columns remains constant, but we would have to extend
 * the div array too as the number of rows in this array is assumed
 * to be equal to extra.
 */
__isl_give isl_basic_map *isl_basic_map_drop(__isl_take isl_basic_map *bmap,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;
  unsigned dim;
  unsigned offset;
  unsigned left;

  if (!bmap)
    goto error;

  dim = isl_basic_map_dim(bmap, type);
  isl_assert(bmap->ctx, first + n <= dim, goto error);

  if (n == 0 && !isl_space_is_named_or_nested(bmap->dim, type)187k)
    return bmap;

  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;

  offset = isl_basic_map_offset(bmap, type) + first;
  left = isl_basic_map_total_dim(bmap) - (offset - 1) - n;
  for (i = 0; i < bmap->n_eq; ++i4.60k)
    constraint_drop_vars(bmap->eq[i]+offset, n, left);

  for (i = 0; i < bmap->n_ineq; ++i3.22M)
    constraint_drop_vars(bmap->ineq[i]+offset, n, left);

  for (i = 0; i < bmap->n_div; ++i2.14k)
    constraint_drop_vars(bmap->div[i]+1+offset, n, left);

  if (type == isl_dim_div) {
    bmap = move_divs_last(bmap, first, n);
    if (!bmap)
      goto error;
    if (isl_basic_map_free_div(bmap, n) < 0)
      return isl_basic_map_free(bmap);
  } else
    bmap->dim = isl_space_drop_dims(bmap->dim, type, first, n);
  if (!bmap->dim)
    goto error;

  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  bmap = isl_basic_map_simplify(bmap);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_drop(__isl_take isl_basic_set *bset,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return bset_from_bmap(isl_basic_map_drop(bset_to_bmap(bset),
              type, first, n));
}

/* No longer consider "map" to be normalized.
 */
static __isl_give isl_map *isl_map_unmark_normalized(__isl_take isl_map *map)
{
  if (!map)
    return NULL;
  ISL_F_CLR(map, ISL_MAP_NORMALIZED);
  return map;
}

__isl_give isl_map *isl_map_drop(__isl_take isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (isl_map_check_range(map, type, first, n) < 0)
    return isl_map_free(map);

  if (n == 0 && !isl_space_is_named_or_nested(map->dim, type)0)
    return map;
  map = isl_map_cow(map);
  if (!map)
    goto error;
  map->dim = isl_space_drop_dims(map->dim, type, first, n);
  if (!map->dim)
    goto error;

  for (i = 0; 805i < map->n; ++i955) {
    map->p[i] = isl_basic_map_drop(map->p[i], type, first, n);
    if (!map->p[i])
      goto error;
  }
  map = isl_map_unmark_normalized(map);

  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_set *isl_set_drop(__isl_take isl_set *set,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return set_from_map(isl_map_drop(set_to_map(set), type, first, n));
}

/*
 * We don't cow, as the div is assumed to be redundant.
 */
__isl_give isl_basic_map *isl_basic_map_drop_div(
  __isl_take isl_basic_map *bmap, unsigned div)
{
  int i;
  unsigned pos;

  if (!bmap)
    goto error;

  pos = 1 + isl_space_dim(bmap->dim, isl_dim_all) + div;

  isl_assert(bmap->ctx, div < bmap->n_div, goto error);

  for (i = 0; 654ki < bmap->n_eq; ++i2.70M)
    constraint_drop_vars(bmap->eq[i]+pos, 1, bmap->extra-div-1);

  for (i = 0; i < bmap->n_ineq; ++i4.56M) {
    if (!isl_int_is_zero(bmap->ineq[i][pos])) {
      isl_basic_map_drop_inequality(bmap, i);
      --i;
      continue;
    }
    constraint_drop_vars(bmap->ineq[i]+pos, 1, bmap->extra-div-1);
  }

  for (i = 0; i < bmap->n_div; ++i1.49M)
    constraint_drop_vars(bmap->div[i]+1+pos, 1, bmap->extra-div-1);

  if (div != bmap->n_div - 1) {
    int j;
    isl_int *t = bmap->div[div];

    for (j = div; j < bmap->n_div - 1; ++j69.7k)
      bmap->div[j] = bmap->div[j+1];

    bmap->div[bmap->n_div - 1] = t;
  }
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  if (isl_basic_map_free_div(bmap, 1) < 0)
    return isl_basic_map_free(bmap);

  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

/* Eliminate the specified n dimensions starting at first from the
 * constraints, without removing the dimensions from the space.
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
 */
__isl_give isl_map *isl_map_eliminate(__isl_take isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (n == 0)
    return map;

  if (isl_map_check_range(map, type, first, n) < 0)
    return isl_map_free(map);

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  for (i = 0; 11.6ki < map->n; ++i26.3k) {
    map->p[i] = isl_basic_map_eliminate(map->p[i], type, first, n);
    if (!map->p[i])
      goto error;
  }
  return map;
error:
  isl_map_free(map);
  return NULL;
}

/* Eliminate the specified n dimensions starting at first from the
 * constraints, without removing the dimensions from the space.
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
 */
__isl_give isl_set *isl_set_eliminate(__isl_take isl_set *set,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return set_from_map(isl_map_eliminate(set_to_map(set), type, first, n));
}

/* Eliminate the specified n dimensions starting at first from the
 * constraints, without removing the dimensions from the space.
 * If the set is rational, the dimensions are eliminated using Fourier-Motzkin.
 */
__isl_give isl_set *isl_set_eliminate_dims(__isl_take isl_set *set,
  unsigned first, unsigned n)
{
  return isl_set_eliminate(set, isl_dim_set, first, n);
}

__isl_give isl_basic_map *isl_basic_map_remove_divs(
  __isl_take isl_basic_map *bmap)
{
  if (!bmap)
    return NULL;
  bmap = isl_basic_map_eliminate_vars(bmap,
          isl_space_dim(bmap->dim, isl_dim_all), bmap->n_div);
  if (!bmap)
    return NULL;
  bmap->n_div = 0;
  return isl_basic_map_finalize(bmap);
}

__isl_give isl_basic_set *isl_basic_set_remove_divs(
  __isl_take isl_basic_set *bset)
{
  return bset_from_bmap(isl_basic_map_remove_divs(bset_to_bmap(bset)));
}

__isl_give isl_map *isl_map_remove_divs(__isl_take isl_map *map)
{
  int i;

  if (!map)
    return NULL;
  if (map->n == 0)
    return map;

  map = isl_map_cow(map);
  if (!map)
    return NULL;
  
  for (i = 0; 1.21ki < map->n; ++i2.05k) {
    map->p[i] = isl_basic_map_remove_divs(map->p[i]);
    if (!map->p[i])
      goto error;
  }
  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_set *isl_set_remove_divs(__isl_take isl_set *set)
{
  return isl_map_remove_divs(set);
}

__isl_give isl_basic_map *isl_basic_map_remove_dims(
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
  unsigned first, unsigned n)
{
  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
    return isl_basic_map_free(bmap);
  if (n == 0 && !isl_space_is_named_or_nested(bmap->dim, type)2.60k)
    return bmap;
  bmap = isl_basic_map_eliminate_vars(bmap,
      isl_basic_map_offset(bmap, type) - 1 + first, n);
  if (!bmap)
    return bmap;
  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_EMPTY) && type == isl_dim_div31)
    return bmap;
  bmap = isl_basic_map_drop(bmap, type, first, n);
  return bmap;
}

/* Return true if the definition of the given div (recursively) involves
 * any of the given variables.
 */
static isl_bool div_involves_vars(__isl_keep isl_basic_map *bmap, int div,
  unsigned first, unsigned n)
{
  int i;
  unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);

  if (isl_int_is_zero(bmap->div[div][0]))
    return isl_bool_false421;
  if (isl_seq_first_non_zero(bmap->div[div] + 1 + first, n) >= 0)
    return isl_bool_true;

  for (i = bmap->n_div - 1; 1.28ki >= 0; --i1.49k) {
    isl_bool involves;

    if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
      continue;
    involves = div_involves_vars(bmap, i, first, n);
    if (involves < 0 || involves)
      return involves;
  }

  return isl_bool_false;
}

/* Try and add a lower and/or upper bound on "div" to "bmap"
 * based on inequality "i".
 * "total" is the total number of variables (excluding the divs).
 * "v" is a temporary object that can be used during the calculations.
 * If "lb" is set, then a lower bound should be constructed.
 * If "ub" is set, then an upper bound should be constructed.
 *
 * The calling function has already checked that the inequality does not
 * reference "div", but we still need to check that the inequality is
 * of the right form.  We'll consider the case where we want to construct
 * a lower bound.  The construction of upper bounds is similar.
 *
 * Let "div" be of the form
 *
 *  q = floor((a + f(x))/d)
 *
 * We essentially check if constraint "i" is of the form
 *
 *  b + f(x) >= 0
 *
 * so that we can use it to derive a lower bound on "div".
 * However, we allow a slightly more general form
 *
 *  b + g(x) >= 0
 *
 * with the condition that the coefficients of g(x) - f(x) are all
 * divisible by d.
 * Rewriting this constraint as
 *
 *  0 >= -b - g(x)
 *
 * adding a + f(x) to both sides and dividing by d, we obtain
 *
 *  (a + f(x))/d >= (a-b)/d + (f(x)-g(x))/d
 *
 * Taking the floor on both sides, we obtain
 *
 *  q >= floor((a-b)/d) + (f(x)-g(x))/d
 *
 * or
 *
 *  (g(x)-f(x))/d + ceil((b-a)/d) + q >= 0
 *
 * In the case of an upper bound, we construct the constraint
 *
 *  (g(x)+f(x))/d + floor((b+a)/d) - q >= 0
 *
 */
static __isl_give isl_basic_map *insert_bounds_on_div_from_ineq(
  __isl_take isl_basic_map *bmap, int div, int i,
  unsigned total, isl_int v, int lb, int ub)
{
  int j;

  for (j = 0; (lb || ub68) && j < total + bmap->n_div222; ++j189) {
    if (lb) {
      isl_int_sub(v, bmap->ineq[i][1 + j],
          bmap->div[div][1 + 1 + j]);
      lb = isl_int_is_divisible_by(v, bmap->div[div][0]);
    }
    if (ub) {
      isl_int_add(v, bmap->ineq[i][1 + j],
          bmap->div[div][1 + 1 + j]);
      ub = isl_int_is_divisible_by(v, bmap->div[div][0]);
    }
  }
  if (!lb && !ub47)
    return bmap;

  bmap = isl_basic_map_cow(bmap);
  bmap = isl_basic_map_extend_constraints(bmap, 0, lb + ub);
  if (lb) {
    int k = isl_basic_map_alloc_inequality(bmap);
    if (k < 0)
      goto error;
    for (j = 0; 21j < 1 + total + bmap->n_div; ++j94) {
      isl_int_sub(bmap->ineq[k][j], bmap->ineq[i][j],
          bmap->div[div][1 + j]);
      isl_int_cdiv_q(bmap->ineq[k][j],
          bmap->ineq[k][j], bmap->div[div][0]);
    }
    isl_int_set_si(bmap->ineq[k][1 + total + div], 1);
  }
  if (ub) {
    int k = isl_basic_map_alloc_inequality(bmap);
    if (k < 0)
      goto error;
    for (j = 0; 18j < 1 + total + bmap->n_div; ++j81) {
      isl_int_add(bmap->ineq[k][j], bmap->ineq[i][j],
          bmap->div[div][1 + j]);
      isl_int_fdiv_q(bmap->ineq[k][j],
          bmap->ineq[k][j], bmap->div[div][0]);
    }
    isl_int_set_si(bmap->ineq[k][1 + total + div], -1);
  }

  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

/* This function is called right before "div" is eliminated from "bmap"
 * using Fourier-Motzkin.
 * Look through the constraints of "bmap" for constraints on the argument
 * of the integer division and use them to construct constraints on the
 * integer division itself.  These constraints can then be combined
 * during the Fourier-Motzkin elimination.
 * Note that it is only useful to introduce lower bounds on "div"
 * if "bmap" already contains upper bounds on "div" as the newly
 * introduce lower bounds can then be combined with the pre-existing
 * upper bounds.  Similarly for upper bounds.
 * We therefore first check if "bmap" contains any lower and/or upper bounds
 * on "div".
 *
 * It is interesting to note that the introduction of these constraints
 * can indeed lead to more accurate results, even when compared to
 * deriving constraints on the argument of "div" from constraints on "div".
 * Consider, for example, the set
 *
 *  { [i,j,k] : 3 + i + 2j >= 0 and 2 * [(i+2j)/4] <= k }
 *
 * The second constraint can be rewritten as
 *
 *  2 * [(-i-2j+3)/4] + k >= 0
 *
 * from which we can derive
 *
 *  -i - 2j + 3 >= -2k
 *
 * or
 *
 *  i + 2j <= 3 + 2k
 *
 * Combined with the first constraint, we obtain
 *
 *  -3 <= 3 + 2k  or  k >= -3
 *
 * If, on the other hand we derive a constraint on [(i+2j)/4] from
 * the first constraint, we obtain
 *
 *  [(i + 2j)/4] >= [-3/4] = -1
 *
 * Combining this constraint with the second constraint, we obtain
 *
 *  k >= -2
 */
static __isl_give isl_basic_map *insert_bounds_on_div(
  __isl_take isl_basic_map *bmap, int div)
{
  int i;
  int check_lb, check_ub;
  isl_int v;
  unsigned total;

  if (!bmap)
    return NULL;

  if (isl_int_is_zero(bmap->div[div][0]))
    return bmap0;

  total = isl_space_dim(bmap->dim, isl_dim_all);

  check_lb = 0;
  check_ub = 0;
  for (i = 0; (!check_lb || !check_ub27) && i < bmap->n_ineq420; ++i345) {
    int s = isl_int_sgn(bmap->ineq[i][1 + total + div]);
    if (s > 0)
      check_ub = 1;
    if (s < 0)
      check_lb = 1;
  }

  if (!check_lb && !check_ub75)
    return bmap;

  isl_int_init(v);

  for (i = 0; bmap && i < bmap->n_ineq; ++i158) {
    if (!isl_int_is_zero(bmap->ineq[i][1 + total + div]))
      continue90;

    bmap = insert_bounds_on_div_from_ineq(bmap, div, i, total, v,
              check_lb, check_ub);
  }

  isl_int_clear(v);

  return bmap;
}

/* Remove all divs (recursively) involving any of the given dimensions
 * in their definitions.
 */
__isl_give isl_basic_map *isl_basic_map_remove_divs_involving_dims(
  __isl_take isl_basic_map *bmap,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
    return isl_basic_map_free(bmap);
  first += isl_basic_map_offset(bmap, type);

  for (i = bmap->n_div - 1; i >= 0; --i1.79k) {
    isl_bool involves;

    involves = div_involves_vars(bmap, i, first, n);
    if (involves < 0)
      return isl_basic_map_free(bmap);
    if (!involves)
      continue;
    bmap = insert_bounds_on_div(bmap, i);
    bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
    if (!bmap)
      return NULL;
    i = bmap->n_div;
  }

  return bmap;
}

__isl_give isl_basic_set *isl_basic_set_remove_divs_involving_dims(
  __isl_take isl_basic_set *bset,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return isl_basic_map_remove_divs_involving_dims(bset, type, first, n);
}

__isl_give isl_map *isl_map_remove_divs_involving_dims(__isl_take isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (!map)
    return NULL;
  if (map->n == 0)
    return map;

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  for (i = 0; 8.41ki < map->n; ++i37.5k) {
    map->p[i] = isl_basic_map_remove_divs_involving_dims(map->p[i],
                type, first, n);
    if (!map->p[i])
      goto error;
  }
  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_set *isl_set_remove_divs_involving_dims(__isl_take isl_set *set,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return set_from_map(isl_map_remove_divs_involving_dims(set_to_map(set),
                    type, first, n));
}

/* Does the description of "bmap" depend on the specified dimensions?
 * We also check whether the dimensions appear in any of the div definitions.
 * In principle there is no need for this check.  If the dimensions appear
 * in a div definition, they also appear in the defining constraints of that
 * div.
 */
isl_bool isl_basic_map_involves_dims(__isl_keep isl_basic_map *bmap,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
    return isl_bool_error;

  first += isl_basic_map_offset(bmap, type);
  for (i = 0; i < bmap->n_eq; ++i106k)
    if (isl_seq_first_non_zero(bmap->eq[i] + first, n) >= 0)
      return isl_bool_true;
  for (i = 0; 48.2ki < bmap->n_ineq; ++i129k)
    if (isl_seq_first_non_zero(bmap->ineq[i] + first, n) >= 0)
      return isl_bool_true;
  for (i = 0; 39.6ki < bmap->n_div39.6k; ++i89) {
    if (isl_int_is_zero(bmap->div[i][0]))
      continue0;
    if (isl_seq_first_non_zero(bmap->div[i] + 1 + first, n) >= 0)
      return isl_bool_true;
  }

  return isl_bool_false;
}

isl_bool isl_map_involves_dims(__isl_keep isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (isl_map_check_range(map, type, first, n) < 0)
    return isl_bool_error;

  for (i = 0; 5.10ki < map->n; ++i5.06k) {
    isl_bool involves = isl_basic_map_involves_dims(map->p[i],
                  type, first, n);
    if (involves < 0 || involves)
      return involves;
  }

  return isl_bool_false4.92k;
}

isl_bool isl_basic_set_involves_dims(__isl_keep isl_basic_set *bset,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return isl_basic_map_involves_dims(bset, type, first, n);
}

isl_bool isl_set_involves_dims(__isl_keep isl_set *set,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return isl_map_involves_dims(set, type, first, n);
}

/* Drop all constraints in bmap that involve any of the dimensions
 * first to first+n-1.
 */
static __isl_give isl_basic_map *isl_basic_map_drop_constraints_involving(
  __isl_take isl_basic_map *bmap, unsigned first, unsigned n)
{
  int i;

  if (n == 0)
    return bmap;

  bmap = isl_basic_map_cow(bmap);

  if (!bmap)
    return NULL;

  for (i = bmap->n_eq - 1; 771ki >= 0; --i5.51k) {
    if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) == -1)
      continue;
    isl_basic_map_drop_equality(bmap, i);
  }

  for (i = bmap->n_ineq - 1; i >= 0; --i12.7M) {
    if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) == -1)
      continue;
    isl_basic_map_drop_inequality(bmap, i);
  }

  bmap = isl_basic_map_add_known_div_constraints(bmap);
  return bmap;
}

/* Drop all constraints in bset that involve any of the dimensions
 * first to first+n-1.
 */
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving(
  __isl_take isl_basic_set *bset, unsigned first, unsigned n)
{
  return isl_basic_map_drop_constraints_involving(bset, first, n);
}

/* Drop all constraints in bmap that do not involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_basic_map *isl_basic_map_drop_constraints_not_involving_dims(
  __isl_take isl_basic_map *bmap,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (n == 0) {
    isl_space *space = isl_basic_map_get_space(bmap);
    isl_basic_map_free(bmap);
    return isl_basic_map_universe(space);
  }
  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;

  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
    return isl_basic_map_free(bmap);

  first += isl_basic_map_offset(bmap, type) - 1;

  for (i = bmap->n_eq - 1; i >= 0; --i167) {
    if (isl_seq_first_non_zero(bmap->eq[i] + 1 + first, n) != -1)
      continue;
    isl_basic_map_drop_equality(bmap, i);
  }

  for (i = bmap->n_ineq - 1; i >= 0; --i2.66k) {
    if (isl_seq_first_non_zero(bmap->ineq[i] + 1 + first, n) != -1)
      continue;
    isl_basic_map_drop_inequality(bmap, i);
  }

  bmap = isl_basic_map_add_known_div_constraints(bmap);
  return bmap;
}

/* Drop all constraints in bset that do not involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_basic_set *isl_basic_set_drop_constraints_not_involving_dims(
  __isl_take isl_basic_set *bset,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return isl_basic_map_drop_constraints_not_involving_dims(bset,
                  type, first, n);
}

/* Drop all constraints in bmap that involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_basic_map *isl_basic_map_drop_constraints_involving_dims(
  __isl_take isl_basic_map *bmap,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  if (!bmap)
    return NULL;
  if (n == 0)
    return bmap;

  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
    return isl_basic_map_free(bmap);

  bmap = isl_basic_map_remove_divs_involving_dims(bmap, type, first, n);
  first += isl_basic_map_offset(bmap, type) - 1;
  return isl_basic_map_drop_constraints_involving(bmap, first, n);
}

/* Drop all constraints in bset that involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_basic_set *isl_basic_set_drop_constraints_involving_dims(
  __isl_take isl_basic_set *bset,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return isl_basic_map_drop_constraints_involving_dims(bset,
                  type, first, n);
}

/* Drop constraints from "map" by applying "drop" to each basic map.
 */
static __isl_give isl_map *drop_constraints(__isl_take isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n,
  __isl_give isl_basic_map *(*drop)(__isl_take isl_basic_map *bmap,
    enum isl_dim_type type, unsigned first, unsigned n))
{
  int i;

  if (isl_map_check_range(map, type, first, n) < 0)
    return isl_map_free(map);

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  for (i = 0; 155i < map->n; ++i494) {
    map->p[i] = drop(map->p[i], type, first, n);
    if (!map->p[i])
      return isl_map_free(map);
  }

  if (map->n > 1)
    ISL_F_CLR(map, ISL_MAP_DISJOINT);

  return map;
}

/* Drop all constraints in map that involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_map *isl_map_drop_constraints_involving_dims(
  __isl_take isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  if (n == 0)
    return map;
  return drop_constraints(map, type, first, n,
        &isl_basic_map_drop_constraints_involving_dims);
}

/* Drop all constraints in "map" that do not involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_map *isl_map_drop_constraints_not_involving_dims(
  __isl_take isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  if (n == 0) {
    isl_space *space = isl_map_get_space(map);
    isl_map_free(map);
    return isl_map_universe(space);
  }
  return drop_constraints(map, type, first, n,
          &isl_basic_map_drop_constraints_not_involving_dims);
}

/* Drop all constraints in set that involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_set *isl_set_drop_constraints_involving_dims(
  __isl_take isl_set *set,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return isl_map_drop_constraints_involving_dims(set, type, first, n);
}

/* Drop all constraints in "set" that do not involve any of the dimensions
 * first to first + n - 1 of the given type.
 */
__isl_give isl_set *isl_set_drop_constraints_not_involving_dims(
  __isl_take isl_set *set,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return isl_map_drop_constraints_not_involving_dims(set, type, first, n);
}

/* Does local variable "div" of "bmap" have a complete explicit representation?
 * Having a complete explicit representation requires not only
 * an explicit representation, but also that all local variables
 * that appear in this explicit representation in turn have
 * a complete explicit representation.
 */
isl_bool isl_basic_map_div_is_known(__isl_keep isl_basic_map *bmap, int div)
{
  int i;
  unsigned div_offset = isl_basic_map_offset(bmap, isl_dim_div);
  isl_bool marked;

  marked = isl_basic_map_div_is_marked_unknown(bmap, div);
  if (marked < 0 || marked)
    return isl_bool_not(marked);

  for (i = bmap->n_div - 1; 80.2ki >= 0; --i140k) {
    isl_bool known;

    if (isl_int_is_zero(bmap->div[div][1 + div_offset + i]))
      continue138k;
    known = isl_basic_map_div_is_known(bmap, i);
    if (known < 0 || !known)
      return known;
  }

  return isl_bool_true;
}

/* Remove all divs that are unknown or defined in terms of unknown divs.
 */
__isl_give isl_basic_map *isl_basic_map_remove_unknown_divs(
  __isl_take isl_basic_map *bmap)
{
  int i;

  if (!bmap)
    return NULL;

  for (i = bmap->n_div - 1; 318ki >= 0; --i1.64k) {
    if (isl_basic_map_div_is_known(bmap, i))
      continue;
    bmap = isl_basic_map_remove_dims(bmap, isl_dim_div, i, 1);
    if (!bmap)
      return NULL;
    i = bmap->n_div;
  }

  return bmap;
}

/* Remove all divs that are unknown or defined in terms of unknown divs.
 */
__isl_give isl_basic_set *isl_basic_set_remove_unknown_divs(
  __isl_take isl_basic_set *bset)
{
  return isl_basic_map_remove_unknown_divs(bset);
}

__isl_give isl_map *isl_map_remove_unknown_divs(__isl_take isl_map *map)
{
  int i;

  if (!map)
    return NULL;
  if (map->n == 0)
    return map;

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  for (i = 0; 183ki < map->n; ++i312k) {
    map->p[i] = isl_basic_map_remove_unknown_divs(map->p[i]);
    if (!map->p[i])
      goto error;
  }
  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_set *isl_set_remove_unknown_divs(__isl_take isl_set *set)
{
  return set_from_map(isl_map_remove_unknown_divs(set_to_map(set)));
}

__isl_give isl_basic_set *isl_basic_set_remove_dims(
  __isl_take isl_basic_set *bset,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  isl_basic_map *bmap = bset_to_bmap(bset);
  bmap = isl_basic_map_remove_dims(bmap, type, first, n);
  return bset_from_bmap(bmap);
}

__isl_give isl_map *isl_map_remove_dims(__isl_take isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (n == 0)
    return map;

  map = isl_map_cow(map);
  if (isl_map_check_range(map, type, first, n) < 0)
    return isl_map_free(map);
  
  for (i = 0; 583i < map->n; ++i733) {
    map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
      isl_basic_map_offset(map->p[i], type) - 1 + first, n);
    if (!map->p[i])
      goto error;
  }
  map = isl_map_drop(map, type, first, n);
  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_set *isl_set_remove_dims(__isl_take isl_set *bset,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  return set_from_map(isl_map_remove_dims(set_to_map(bset),
            type, first, n));
}

/* Project out n inputs starting at first using Fourier-Motzkin */
struct isl_map *isl_map_remove_inputs(struct isl_map *map,
  unsigned first, unsigned n)
{
  return isl_map_remove_dims(map, isl_dim_in, first, n);
}

static void dump_term(struct isl_basic_map *bmap,
      isl_int c, int pos, FILE *out)
{
  const char *name;
  unsigned in = isl_basic_map_dim(bmap, isl_dim_in);
  unsigned dim = in + isl_basic_map_dim(bmap, isl_dim_out);
  unsigned nparam = isl_basic_map_dim(bmap, isl_dim_param);
  if (!pos)
    isl_int_print(out, c, 0);
  else {
    if (!isl_int_is_one(c))
      isl_int_print(out, c, 0);
    if (pos < 1 + nparam) {
      name = isl_space_get_dim_name(bmap->dim,
            isl_dim_param, pos - 1);
      if (name)
        fprintf(out, "%s", name);
      else
        fprintf(out, "p%d", pos - 1);
    } else if (pos < 1 + nparam + in)
      fprintf(out, "i%d", pos - 1 - nparam);
    else if (pos < 1 + nparam + dim)
      fprintf(out, "o%d", pos - 1 - nparam - in);
    else
      fprintf(out, "e%d", pos - 1 - nparam - dim);
  }
}

static void dump_constraint_sign(struct isl_basic_map *bmap, isl_int *c,
        int sign, FILE *out)
{
  int i;
  int first;
  unsigned len = 1 + isl_basic_map_total_dim(bmap);
  isl_int v;

  isl_int_init(v);
  for (i = 0, first = 1; i < len; ++i) {
    if (isl_int_sgn(c[i]) * sign <= 0)
      continue;
    if (!first)
      fprintf(out, " + ");
    first = 0;
    isl_int_abs(v, c[i]);
    dump_term(bmap, v, i, out);
  }
  isl_int_clear(v);
  if (first)
    fprintf(out, "0");
}

static void dump_constraint(struct isl_basic_map *bmap, isl_int *c,
        const char *op, FILE *out, int indent)
{
  int i;

  fprintf(out, "%*s", indent, "");

  dump_constraint_sign(bmap, c, 1, out);
  fprintf(out, " %s ", op);
  dump_constraint_sign(bmap, c, -1, out);

  fprintf(out, "\n");

  for (i = bmap->n_div; i < bmap->extra; ++i) {
    if (isl_int_is_zero(c[1+isl_space_dim(bmap->dim, isl_dim_all)+i]))
      continue;
    fprintf(out, "%*s", indent, "");
    fprintf(out, "ERROR: unused div coefficient not zero\n");
    abort();
  }
}

static void dump_constraints(struct isl_basic_map *bmap,
        isl_int **c, unsigned n,
        const char *op, FILE *out, int indent)
{
  int i;

  for (i = 0; i < n; ++i)
    dump_constraint(bmap, c[i], op, out, indent);
}

static void dump_affine(struct isl_basic_map *bmap, isl_int *exp, FILE *out)
{
  int j;
  int first = 1;
  unsigned total = isl_basic_map_total_dim(bmap);

  for (j = 0; j < 1 + total; ++j) {
    if (isl_int_is_zero(exp[j]))
      continue;
    if (!first && isl_int_is_pos(exp[j]))
      fprintf(out, "+");
    dump_term(bmap, exp[j], j, out);
    first = 0;
  }
}

static void dump(struct isl_basic_map *bmap, FILE *out, int indent)
{
  int i;

  dump_constraints(bmap, bmap->eq, bmap->n_eq, "=", out, indent);
  dump_constraints(bmap, bmap->ineq, bmap->n_ineq, ">=", out, indent);

  for (i = 0; i < bmap->n_div; ++i) {
    fprintf(out, "%*s", indent, "");
    fprintf(out, "e%d = [(", i);
    dump_affine(bmap, bmap->div[i]+1, out);
    fprintf(out, ")/");
    isl_int_print(out, bmap->div[i][0], 0);
    fprintf(out, "]\n");
  }
}

void isl_basic_set_print_internal(struct isl_basic_set *bset,
  FILE *out, int indent)
{
  if (!bset) {
    fprintf(out, "null basic set\n");
    return;
  }

  fprintf(out, "%*s", indent, "");
  fprintf(out, "ref: %d, nparam: %d, dim: %d, extra: %d, flags: %x\n",
      bset->ref, bset->dim->nparam, bset->dim->n_out,
      bset->extra, bset->flags);
  dump(bset_to_bmap(bset), out, indent);
}

void isl_basic_map_print_internal(struct isl_basic_map *bmap,
  FILE *out, int indent)
{
  if (!bmap) {
    fprintf(out, "null basic map\n");
    return;
  }

  fprintf(out, "%*s", indent, "");
  fprintf(out, "ref: %d, nparam: %d, in: %d, out: %d, extra: %d, "
      "flags: %x, n_name: %d\n",
    bmap->ref,
    bmap->dim->nparam, bmap->dim->n_in, bmap->dim->n_out,
    bmap->extra, bmap->flags, bmap->dim->n_id);
  dump(bmap, out, indent);
}

int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos)
{
  unsigned total;
  if (!bmap)
    return -1;
  total = isl_basic_map_total_dim(bmap);
  isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
  isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
  isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  return 0;
}

__isl_give isl_set *isl_set_alloc_space(__isl_take isl_space *space, int n,
  unsigned flags)
{
  if (!space)
    return NULL;
  if (isl_space_dim(space, isl_dim_in) != 0)
    isl_die0(isl_space_get_ctx(space), isl_error_invalid,
      "set cannot have input dimensions", goto error);
  return isl_map_alloc_space(space, n, flags);
error:
  isl_space_free(space);
  return NULL;
}

/* Make sure "map" has room for at least "n" more basic maps.
 */
__isl_give isl_map *isl_map_grow(__isl_take isl_map *map, int n)
{
  int i;
  struct isl_map *grown = NULL;

  if (!map)
    return NULL;
  isl_assert(map->ctx, n >= 0, goto error);
  if (map->n + n <= map->size)
    return map;
  grown = isl_map_alloc_space(isl_map_get_space(map), map->n + n, map->flags);
  if (!grown)
    goto error;
  for (i = 0; 315i < map->n; ++i400) {
    grown->p[i] = isl_basic_map_copy(map->p[i]);
    if (!grown->p[i])
      goto error;
    grown->n++;
  }
  isl_map_free(map);
  return grown;
error:
  isl_map_free(grown);
  isl_map_free(map);
  return NULL;
}

/* Make sure "set" has room for at least "n" more basic sets.
 */
struct isl_set *isl_set_grow(struct isl_set *set, int n)
{
  return set_from_map(isl_map_grow(set_to_map(set), n));
}

__isl_give isl_set *isl_set_from_basic_set(__isl_take isl_basic_set *bset)
{
  return isl_map_from_basic_map(bset);
}

__isl_give isl_map *isl_map_from_basic_map(__isl_take isl_basic_map *bmap)
{
  struct isl_map *map;

  if (!bmap)
    return NULL;

  map = isl_map_alloc_space(isl_space_copy(bmap->dim), 1, ISL_MAP_DISJOINT);
  return isl_map_add_basic_map(map, bmap);
}

__isl_give isl_set *isl_set_add_basic_set(__isl_take isl_set *set,
            __isl_take isl_basic_set *bset)
{
  return set_from_map(isl_map_add_basic_map(set_to_map(set),
            bset_to_bmap(bset)));
}

__isl_null isl_set *isl_set_free(__isl_take isl_set *set)
{
  return isl_map_free(set);
}

void isl_set_print_internal(struct isl_set *set, FILE *out, int indent)
{
  int i;

  if (!set) {
    fprintf(out, "null set\n");
    return;
  }

  fprintf(out, "%*s", indent, "");
  fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
      set->ref, set->n, set->dim->nparam, set->dim->n_out,
      set->flags);
  for (i = 0; i < set->n; ++i) {
    fprintf(out, "%*s", indent, "");
    fprintf(out, "basic set %d:\n", i);
    isl_basic_set_print_internal(set->p[i], out, indent+4);
  }
}

void isl_map_print_internal(struct isl_map *map, FILE *out, int indent)
{
  int i;

  if (!map) {
    fprintf(out, "null map\n");
    return;
  }

  fprintf(out, "%*s", indent, "");
  fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, "
         "flags: %x, n_name: %d\n",
      map->ref, map->n, map->dim->nparam, map->dim->n_in,
      map->dim->n_out, map->flags, map->dim->n_id);
  for (i = 0; i < map->n; ++i) {
    fprintf(out, "%*s", indent, "");
    fprintf(out, "basic map %d:\n", i);
    isl_basic_map_print_internal(map->p[i], out, indent+4);
  }
}

__isl_give isl_basic_map *isl_basic_map_intersect_domain(
  __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *bset)
{
  struct isl_basic_map *bmap_domain;

  if (isl_basic_map_check_equal_params(bmap, bset_to_bmap(bset)) < 0)
    goto error;

  if (isl_space_dim(bset->dim, isl_dim_set) != 0)
    isl_assert(bset->ctx,
        isl_basic_map_compatible_domain(bmap, bset), goto error);

  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    goto error;
  bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
      bset->n_div, bset->n_eq, bset->n_ineq);
  bmap_domain = isl_basic_map_from_domain(bset);
  bmap = add_constraints(bmap, bmap_domain, 0, 0);

  bmap = isl_basic_map_simplify(bmap);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  isl_basic_set_free(bset);
  return NULL;
}

/* Check that the space of "bset" is the same as that of the range of "bmap".
 */
static isl_stat isl_basic_map_check_compatible_range(
  __isl_keep isl_basic_map *bmap, __isl_keep isl_basic_set *bset)
{
  isl_bool ok;

  ok = isl_basic_map_compatible_range(bmap, bset);
  if (ok < 0)
    return isl_stat_error;
  if (!ok)
    isl_die0(isl_basic_set_get_ctx(bset), isl_error_invalid,
      "incompatible spaces", return isl_stat_error);

  return isl_stat_ok;
}

__isl_give isl_basic_map *isl_basic_map_intersect_range(
  __isl_take isl_basic_map *bmap, __isl_take isl_basic_set *bset)
{
  struct isl_basic_map *bmap_range;

  if (isl_basic_map_check_equal_params(bmap, bset_to_bmap(bset)) < 0)
    goto error;

  if (isl_space_dim(bset->dim, isl_dim_set) != 0 &&
      isl_basic_map_check_compatible_range(bmap, bset) < 06.73k)
    goto error;

  if (isl_basic_set_plain_is_universe(bset)) {
    isl_basic_set_free(bset);
    return bmap;
  }

  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    goto error;
  bmap = isl_basic_map_extend_space(bmap, isl_space_copy(bmap->dim),
      bset->n_div, bset->n_eq, bset->n_ineq);
  bmap_range = bset_to_bmap(bset);
  bmap = add_constraints(bmap, bmap_range, 0, 0);

  bmap = isl_basic_map_simplify(bmap);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  isl_basic_set_free(bset);
  return NULL;
}

isl_bool isl_basic_map_contains(__isl_keep isl_basic_map *bmap,
  __isl_keep isl_vec *vec)
{
  int i;
  unsigned total;
  isl_int s;

  if (!bmap || !vec)
    return isl_bool_error;

  total = 1 + isl_basic_map_total_dim(bmap);
  if (total != vec->size)
    return isl_bool_false;

  isl_int_init(s);

  for (i = 0; i < bmap->n_eq; ++i2.67M) {
    isl_seq_inner_product(vec->el, bmap->eq[i], total, &s);
    if (!isl_int_is_zero(s)) {
      isl_int_clear(s);
      return isl_bool_false;
    }
  }

  for (i = 0; 2.22Mi < bmap->n_ineq; ++i11.1M) {
    isl_seq_inner_product(vec->el, bmap->ineq[i], total, &s);
    if (isl_int_is_neg(s)) {
      isl_int_clear(s);
      return isl_bool_false;
    }
  }

  isl_int_clear1.35M(s);

  return isl_bool_true;
}

isl_bool isl_basic_set_contains(__isl_keep isl_basic_set *bset,
  __isl_keep isl_vec *vec)
{
  return isl_basic_map_contains(bset_to_bmap(bset), vec);
}

__isl_give isl_basic_map *isl_basic_map_intersect(
  __isl_take isl_basic_map *bmap1, __isl_take isl_basic_map *bmap2)
{
  struct isl_vec *sample = NULL;

  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
    goto error;
  if (isl_space_dim(bmap1->dim, isl_dim_all) ==
        isl_space_dim(bmap1->dim, isl_dim_param) &&
      isl_space_dim(bmap2->dim, isl_dim_all) !=
        isl_space_dim(bmap2->dim, isl_dim_param))
    return isl_basic_map_intersect(bmap2, bmap1);

  if (isl_space_dim(bmap2->dim, isl_dim_all) !=
          isl_space_dim(bmap2->dim, isl_dim_param))
    isl_assert(bmap1->ctx,
          isl_space_is_equal(bmap1->dim, bmap2->dim), goto error);

  if (isl_basic_map_plain_is_empty(bmap1)) {
    isl_basic_map_free(bmap2);
    return bmap1;
  }
  if (isl_basic_map_plain_is_empty(bmap2)) {
    isl_basic_map_free(bmap1);
    return bmap2;
  }

  if (bmap1->sample &&
      isl_basic_map_contains(bmap1, bmap1->sample) > 0189k &&
      isl_basic_map_contains(bmap2, bmap1->sample) > 0155k)
    sample = isl_vec_copy(bmap1->sample);
  else if (bmap2->sample &&
      isl_basic_map_contains(bmap1, bmap2->sample) > 0141k &&
      isl_basic_map_contains(bmap2, bmap2->sample) > 031.9k)
    sample = isl_vec_copy(bmap2->sample);

  bmap1 = isl_basic_map_cow(bmap1);
  if (!bmap1)
    goto error;
  bmap1 = isl_basic_map_extend_space(bmap1, isl_space_copy(bmap1->dim),
      bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
  bmap1 = add_constraints(bmap1, bmap2, 0, 0);

  if (!bmap1)
    isl_vec_free(sample);
  else if (sample) {
    isl_vec_free(bmap1->sample);
    bmap1->sample = sample;
  }

  bmap1 = isl_basic_map_simplify(bmap1);
  return isl_basic_map_finalize(bmap1);
error:
  if (sample)
    isl_vec_free(sample);
  isl_basic_map_free(bmap1);
  isl_basic_map_free(bmap2);
  return NULL;
}

struct isl_basic_set *isl_basic_set_intersect(
    struct isl_basic_set *bset1, struct isl_basic_set *bset2)
{
  return bset_from_bmap(isl_basic_map_intersect(bset_to_bmap(bset1),
              bset_to_bmap(bset2)));
}

__isl_give isl_basic_set *isl_basic_set_intersect_params(
  __isl_take isl_basic_set *bset1, __isl_take isl_basic_set *bset2)
{
  return isl_basic_set_intersect(bset1, bset2);
}

/* Special case of isl_map_intersect, where both map1 and map2
 * are convex, without any divs and such that either map1 or map2
 * contains a single constraint.  This constraint is then simply
 * added to the other map.
 */
static __isl_give isl_map *map_intersect_add_constraint(
  __isl_take isl_map *map1, __isl_take isl_map *map2)
{
  isl_assert(map1->ctx, map1->n == 1, goto error);
  isl_assert(map2->ctx, map1->n == 1, goto error);
  isl_assert(map1->ctx, map1->p[0]->n_div == 0, goto error);
  isl_assert(map2->ctx, map1->p[0]->n_div == 0, goto error);

  if (map2->p[0]->n_eq + map2->p[0]->n_ineq != 1)
    return isl_map_intersect(map2, map1);

  map1 = isl_map_cow(map1);
  if (!map1)
    goto error;
  if (isl_map_plain_is_empty(map1)) {
    isl_map_free(map2);
    return map1;
  }
  map1->p[0] = isl_basic_map_cow(map1->p[0]);
  if (map2->p[0]->n_eq == 1)
    map1->p[0] = isl_basic_map_add_eq(map1->p[0], map2->p[0]->eq[0]);
  else
    map1->p[0] = isl_basic_map_add_ineq(map1->p[0],
              map2->p[0]->ineq[0]);

  map1->p[0] = isl_basic_map_simplify(map1->p[0]);
  map1->p[0] = isl_basic_map_finalize(map1->p[0]);
  if (!map1->p[0])
    goto error;

  if (isl_basic_map_plain_is_empty(map1->p[0])) {
    isl_basic_map_free(map1->p[0]);
    map1->n = 0;
  }

  isl_map_free(map2);

  map1 = isl_map_unmark_normalized(map1);
  return map1;
error:
  isl_map_free(map1);
  isl_map_free(map2);
  return NULL;
}

/* map2 may be either a parameter domain or a map living in the same
 * space as map1.
 */
static __isl_give isl_map *map_intersect_internal(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  unsigned flags = 0;
  isl_bool equal;
  isl_map *result;
  int i, j;

  if (!map1 || !map2)
    goto error;

  if ((isl_map_plain_is_empty(map1) ||
       isl_map_plain_is_universe(map2)407k) &&
      isl_space_is_equal(map1->dim, map2->dim)225k) {
    isl_map_free(map2);
    return map1;
  }
  if ((isl_map_plain_is_empty(map2) ||
       isl_map_plain_is_universe(map1)207k) &&
      isl_space_is_equal(map1->dim, map2->dim)114k) {
    isl_map_free(map1);
    return map2;
  }

  if (map1->n == 1 && map2->n == 1106k &&
      map1->p[0]->n_div == 098.7k && map2->p[0]->n_div == 095.6k &&
      isl_space_is_equal(map1->dim, map2->dim)94.7k &&
      (66.7kmap1->p[0]->n_eq + map1->p[0]->n_ineq == 166.7k ||
       map2->p[0]->n_eq + map2->p[0]->n_ineq == 155.1k))
    return map_intersect_add_constraint(map1, map2);

  equal = isl_map_plain_is_equal(map1, map2);
  if (equal < 0)
    goto error;
  if (equal) {
    isl_map_free(map2);
    return map1;
  }

  if (isl_space_dim(map2->dim, isl_dim_all) !=
        isl_space_dim(map2->dim, isl_dim_param))
    isl_assert(map1->ctx,
          isl_space_is_equal(map1->dim, map2->dim), goto error);

  if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT) &&
      ISL_F_ISSET53.3k(map2, ISL_MAP_DISJOINT))
    ISL_FL_SET48.8k(flags, ISL_MAP_DISJOINT);

  result = isl_map_alloc_space(isl_space_copy(map1->dim),
        map1->n * map2->n, flags);
  if (!result)
    goto error;
  for (i = 0; 72.3ki < map1->n; ++i134k)
    for (j = 0; 134kj < map2->n; ++j213k) {
      struct isl_basic_map *part;
      part = isl_basic_map_intersect(
            isl_basic_map_copy(map1->p[i]),
            isl_basic_map_copy(map2->p[j]));
      if (isl_basic_map_is_empty(part) < 0)
        part = isl_basic_map_free(part);
      result = isl_map_add_basic_map(result, part);
      if (!result)
        goto error;
    }
  isl_map_free(map1);
  isl_map_free(map2);
  return result;
error:
  isl_map_free(map1);
  isl_map_free(map2);
  return NULL;
}

static __isl_give isl_map *map_intersect(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  if (!map1 || !map2)
    goto error;
  if (!isl_space_is_equal(map1->dim, map2->dim))
    isl_die0(isl_map_get_ctx(map1), isl_error_invalid,
      "spaces don't match", goto error);
  return map_intersect_internal(map1, map2);
error:
  isl_map_free(map1);
  isl_map_free(map2);
  return NULL;
}

__isl_give isl_map *isl_map_intersect(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  return isl_map_align_params_map_map_and(map1, map2, &map_intersect);
}

struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
{
  return set_from_map(isl_map_intersect(set_to_map(set1),
                set_to_map(set2)));
}

/* map_intersect_internal accepts intersections
 * with parameter domains, so we can just call that function.
 */
static __isl_give isl_map *map_intersect_params(__isl_take isl_map *map,
    __isl_take isl_set *params)
{
  return map_intersect_internal(map, params);
}

__isl_give isl_map *isl_map_intersect_params(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  return isl_map_align_params_map_map_and(map1, map2, &map_intersect_params);
}

__isl_give isl_set *isl_set_intersect_params(__isl_take isl_set *set,
    __isl_take isl_set *params)
{
  return isl_map_intersect_params(set, params);
}

__isl_give isl_basic_map *isl_basic_map_reverse(__isl_take isl_basic_map *bmap)
{
  isl_space *space;
  unsigned pos, n1, n2;

  if (!bmap)
    return NULL;
  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;
  space = isl_space_reverse(isl_space_copy(bmap->dim));
  pos = isl_basic_map_offset(bmap, isl_dim_in);
  n1 = isl_basic_map_dim(bmap, isl_dim_in);
  n2 = isl_basic_map_dim(bmap, isl_dim_out);
  bmap = isl_basic_map_swap_vars(bmap, pos, n1, n2);
  return isl_basic_map_reset_space(bmap, space);
}

static __isl_give isl_basic_map *basic_map_space_reset(
  __isl_take isl_basic_map *bmap, enum isl_dim_type type)
{
  isl_space *space;

  if (!bmap)
    return NULL;
  if (!isl_space_is_named_or_nested(bmap->dim, type))
    return bmap;

  space = isl_basic_map_get_space(bmap);
  space = isl_space_reset(space, type);
  bmap = isl_basic_map_reset_space(bmap, space);
  return bmap;
}

__isl_give isl_basic_map *isl_basic_map_insert_dims(
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
  unsigned pos, unsigned n)
{
  isl_bool rational;
  isl_space *res_space;
  struct isl_basic_map *res;
  struct isl_dim_map *dim_map;
  unsigned total, off;
  enum isl_dim_type t;

  if (n == 0)
    return basic_map_space_reset(bmap, type);

  res_space = isl_space_insert_dims(isl_basic_map_get_space(bmap),
          type, pos, n);
  if (!res_space)
    return isl_basic_map_free(bmap);

  total = isl_basic_map_total_dim(bmap) + n;
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
  off = 0;
  for (t = isl_dim_param; t <= isl_dim_out; ++t230k) {
    if (t != type) {
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
    } else {
      unsigned size = isl_basic_map_dim(bmap, t);
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
            0, pos, off);
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
            pos, size - pos, off + pos + n);
    }
    off += isl_space_dim(res_space, t);
  }
  isl_dim_map_div(dim_map, bmap, off);

  res = isl_basic_map_alloc_space(res_space,
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
  rational = isl_basic_map_is_rational(bmap);
  if (rational < 0)
    res = isl_basic_map_free(res);
  if (rational)
    res = isl_basic_map_set_rational(res);
  if (isl_basic_map_plain_is_empty(bmap)) {
    isl_basic_map_free(bmap);
    free(dim_map);
    return isl_basic_map_set_to_empty(res);
  }
  res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
  return isl_basic_map_finalize(res);
}

__isl_give isl_basic_set *isl_basic_set_insert_dims(
  __isl_take isl_basic_set *bset,
  enum isl_dim_type type, unsigned pos, unsigned n)
{
  return isl_basic_map_insert_dims(bset, type, pos, n);
}

__isl_give isl_basic_map *isl_basic_map_add_dims(__isl_take isl_basic_map *bmap,
    enum isl_dim_type type, unsigned n)
{
  if (!bmap)
    return NULL;
  return isl_basic_map_insert_dims(bmap, type,
          isl_basic_map_dim(bmap, type), n);
}

__isl_give isl_basic_set *isl_basic_set_add_dims(__isl_take isl_basic_set *bset,
    enum isl_dim_type type, unsigned n)
{
  if (!bset)
    return NULL;
  isl_assert(bset->ctx, type != isl_dim_in, goto error);
  return isl_basic_map_add_dims(bset, type, n);
error:
  isl_basic_set_free(bset);
  return NULL;
}

static __isl_give isl_map *map_space_reset(__isl_take isl_map *map,
  enum isl_dim_type type)
{
  isl_space *space;

  if (!map || !isl_space_is_named_or_nested(map->dim, type))
    return map;

  space = isl_map_get_space(map);
  space = isl_space_reset(space, type);
  map = isl_map_reset_space(map, space);
  return map;
}

__isl_give isl_map *isl_map_insert_dims(__isl_take isl_map *map,
    enum isl_dim_type type, unsigned pos, unsigned n)
{
  int i;

  if (n == 0)
    return map_space_reset(map, type);

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  map->dim = isl_space_insert_dims(map->dim, type, pos, n);
  if (!map->dim)
    goto error;

  for (i = 0; 32.5ki < map->n; ++i34.0k) {
    map->p[i] = isl_basic_map_insert_dims(map->p[i], type, pos, n);
    if (!map->p[i])
      goto error;
  }

  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_set *isl_set_insert_dims(__isl_take isl_set *set,
    enum isl_dim_type type, unsigned pos, unsigned n)
{
  return isl_map_insert_dims(set, type, pos, n);
}

__isl_give isl_map *isl_map_add_dims(__isl_take isl_map *map,
    enum isl_dim_type type, unsigned n)
{
  if (!map)
    return NULL;
  return isl_map_insert_dims(map, type, isl_map_dim(map, type), n);
}

__isl_give isl_set *isl_set_add_dims(__isl_take isl_set *set,
    enum isl_dim_type type, unsigned n)
{
  if (!set)
    return NULL;
  isl_assert(set->ctx, type != isl_dim_in, goto error);
  return set_from_map(isl_map_add_dims(set_to_map(set), type, n));
error:
  isl_set_free(set);
  return NULL;
}

__isl_give isl_basic_map *isl_basic_map_move_dims(
  __isl_take isl_basic_map *bmap,
  enum isl_dim_type dst_type, unsigned dst_pos,
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
{
  struct isl_dim_map *dim_map;
  struct isl_basic_map *res;
  enum isl_dim_type t;
  unsigned total, off;

  if (!bmap)
    return NULL;
  if (n == 0) {
    bmap = isl_basic_map_reset(bmap, src_type);
    bmap = isl_basic_map_reset(bmap, dst_type);
    return bmap;
  }

  if (isl_basic_map_check_range(bmap, src_type, src_pos, n) < 0)
    return isl_basic_map_free(bmap);

  if (dst_type == src_type && dst_pos == src_pos0)
    return bmap;

  isl_assert(bmap->ctx, dst_type != src_type, goto error);

  if (pos(bmap->dim, dst_type) + dst_pos ==
      pos(bmap->dim, src_type) + src_pos +
              ((src_type < dst_type) ? n123 : 0498)) {
    bmap = isl_basic_map_cow(bmap);
    if (!bmap)
      return NULL;

    bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos,
            src_type, src_pos, n);
    if (!bmap->dim)
      goto error;

    bmap = isl_basic_map_finalize(bmap);

    return bmap;
  }

  total = isl_basic_map_total_dim(bmap);
  dim_map = isl_dim_map_alloc(bmap->ctx, total);

  off = 0;
  for (t = isl_dim_param; t <= isl_dim_out; ++t342) {
    unsigned size = isl_space_dim(bmap->dim, t);
    if (t == dst_type) {
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
              0, dst_pos, off);
      off += dst_pos;
      isl_dim_map_dim_range(dim_map, bmap->dim, src_type,
              src_pos, n, off);
      off += n;
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
              dst_pos, size - dst_pos, off);
      off += size - dst_pos;
    } else if (t == src_type) {
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
              0, src_pos, off);
      off += src_pos;
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
          src_pos + n, size - src_pos - n, off);
      off += size - src_pos - n;
    } else {
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
      off += size;
    }
  }
  isl_dim_map_div(dim_map, bmap, off);

  res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap),
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
  bmap = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
  if (!bmap)
    goto error;

  bmap->dim = isl_space_move_dims(bmap->dim, dst_type, dst_pos,
          src_type, src_pos, n);
  if (!bmap->dim)
    goto error;

  ISL_F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
  bmap = isl_basic_map_gauss(bmap, NULL);
  bmap = isl_basic_map_finalize(bmap);

  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_set *isl_basic_set_move_dims(__isl_take isl_basic_set *bset,
  enum isl_dim_type dst_type, unsigned dst_pos,
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
{
  isl_basic_map *bmap = bset_to_bmap(bset);
  bmap = isl_basic_map_move_dims(bmap, dst_type, dst_pos,
          src_type, src_pos, n);
  return bset_from_bmap(bmap);
}

__isl_give isl_set *isl_set_move_dims(__isl_take isl_set *set,
  enum isl_dim_type dst_type, unsigned dst_pos,
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
{
  if (!set)
    return NULL;
  isl_assert(set->ctx, dst_type != isl_dim_in, goto error);
  return set_from_map(isl_map_move_dims(set_to_map(set),
            dst_type, dst_pos, src_type, src_pos, n));
error:
  isl_set_free(set);
  return NULL;
}

__isl_give isl_map *isl_map_move_dims(__isl_take isl_map *map,
  enum isl_dim_type dst_type, unsigned dst_pos,
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
{
  int i;

  if (n == 0) {
    map = isl_map_reset(map, src_type);
    map = isl_map_reset(map, dst_type);
    return map;
  }

  if (isl_map_check_range(map, src_type, src_pos, n))
    return isl_map_free(map);

  if (dst_type == src_type && dst_pos == src_pos0)
    return map;

  isl_assert(map->ctx, dst_type != src_type, goto error);

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  map->dim = isl_space_move_dims(map->dim, dst_type, dst_pos, src_type, src_pos, n);
  if (!map->dim)
    goto error;

  for (i = 0; 158i < map->n; ++i180) {
    map->p[i] = isl_basic_map_move_dims(map->p[i],
            dst_type, dst_pos,
            src_type, src_pos, n);
    if (!map->p[i])
      goto error;
  }

  return map;
error:
  isl_map_free(map);
  return NULL;
}

/* Move the specified dimensions to the last columns right before
 * the divs.  Don't change the dimension specification of bmap.
 * That's the responsibility of the caller.
 */
static __isl_give isl_basic_map *move_last(__isl_take isl_basic_map *bmap,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  struct isl_dim_map *dim_map;
  struct isl_basic_map *res;
  enum isl_dim_type t;
  unsigned total, off;

  if (!bmap)
    return NULL;
  if (pos(bmap->dim, type) + first + n ==
        1 + isl_space_dim(bmap->dim, isl_dim_all))
    return bmap;

  total = isl_basic_map_total_dim(bmap);
  dim_map = isl_dim_map_alloc(bmap->ctx, total);

  off = 0;
  for (t = isl_dim_param; t <= isl_dim_out; ++t67.4k) {
    unsigned size = isl_space_dim(bmap->dim, t);
    if (t == type) {
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
              0, first, off);
      off += first;
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
              first, n, total - bmap->n_div - n);
      isl_dim_map_dim_range(dim_map, bmap->dim, t,
              first + n, size - (first + n), off);
      off += size - (first + n);
    } else {
      isl_dim_map_dim(dim_map, bmap->dim, t, off);
      off += size;
    }
  }
  isl_dim_map_div(dim_map, bmap, off + n);

  res = isl_basic_map_alloc_space(isl_basic_map_get_space(bmap),
      bmap->n_div, bmap->n_eq, bmap->n_ineq);
  res = isl_basic_map_add_constraints_dim_map(res, bmap, dim_map);
  return res;
}

/* Insert "n" rows in the divs of "bmap".
 *
 * The number of columns is not changed, which means that the last
 * dimensions of "bmap" are being reintepreted as the new divs.
 * The space of "bmap" is not adjusted, however, which means
 * that "bmap" is left in an inconsistent state.  Removing "n" dimensions
 * from the space of "bmap" is the responsibility of the caller.
 */
static __isl_give isl_basic_map *insert_div_rows(__isl_take isl_basic_map *bmap,
  int n)
{
  int i;
  size_t row_size;
  isl_int **new_div;
  isl_int *old;

  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;

  row_size = 1 + isl_space_dim(bmap->dim, isl_dim_all) + bmap->extra;
  old = bmap->block2.data;
  bmap->block2 = isl_blk_extend(bmap->ctx, bmap->block2,
          (bmap->extra + n) * (1 + row_size));
  if (!bmap->block2.data)
    return isl_basic_map_free(bmap);
  new_div = isl_alloc_array(bmap->ctx, isl_int *, bmap->extra + n);
  if (!new_div)
    return isl_basic_map_free(bmap);
  for (i = 0; 182ki < n; ++i373k) {
    new_div[i] = bmap->block2.data +
        (bmap->extra + i) * (1 + row_size);
    isl_seq_clr(new_div[i], 1 + row_size);
  }
  for (i = 0; i < bmap->extra; ++i11.5k)
    new_div[n + i] = bmap->block2.data + (bmap->div[i] - old);
  free(bmap->div);
  bmap->div = new_div;
  bmap->n_div += n;
  bmap->extra += n;

  return bmap;
}

/* Drop constraints from "bmap" that only involve the variables
 * of "type" in the range [first, first + n] that are not related
 * to any of the variables outside that interval.
 * These constraints cannot influence the values for the variables
 * outside the interval, except in case they cause "bmap" to be empty.
 * Only drop the constraints if "bmap" is known to be non-empty.
 */
static __isl_give isl_basic_map *drop_irrelevant_constraints(
  __isl_take isl_basic_map *bmap, enum isl_dim_type type,
  unsigned first, unsigned n)
{
  int i;
  int *groups;
  unsigned dim, n_div;
  isl_bool non_empty;

  non_empty = isl_basic_map_plain_is_non_empty(bmap);
  if (non_empty < 0)
    return isl_basic_map_free(bmap);
  if (!non_empty)
    return bmap;

  dim = isl_basic_map_dim(bmap, isl_dim_all);
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
  groups = isl_calloc_array(isl_basic_map_get_ctx(bmap), int, dim);
  if (!groups)
    return isl_basic_map_free(bmap);
  first += isl_basic_map_offset(bmap, type) - 1;
  for (i = 0; i < first; ++i266k)
    groups[i] = -1;
  for (i = first + n; i < dim - n_div; ++i21.8k)
    groups[i] = -1;

  bmap = isl_basic_map_drop_unrelated_constraints(bmap, groups);

  return bmap;
}

/* Turn the n dimensions of type type, starting at first
 * into existentially quantified variables.
 *
 * If a subset of the projected out variables are unrelated
 * to any of the variables that remain, then the constraints
 * involving this subset are simply dropped first.
 */
__isl_give isl_basic_map *isl_basic_map_project_out(
    __isl_take isl_basic_map *bmap,
    enum isl_dim_type type, unsigned first, unsigned n)
{
  isl_bool empty;

  if (n == 0)
    return basic_map_space_reset(bmap, type);
  if (type == isl_dim_div)
    isl_die0(isl_basic_map_get_ctx(bmap), isl_error_invalid,
      "cannot project out existentially quantified variables",
      return isl_basic_map_free(bmap));

  empty = isl_basic_map_plain_is_empty(bmap);
  if (empty < 0)
    return isl_basic_map_free(bmap);
  if (empty)
    bmap = isl_basic_map_set_to_empty(bmap);

  bmap = drop_irrelevant_constraints(bmap, type, first, n);
  if (!bmap)
    return NULL;

  if (ISL_F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
    return isl_basic_map_remove_dims(bmap, type, first, n)39;

  if (isl_basic_map_check_range(bmap, type, first, n) < 0)
    return isl_basic_map_free(bmap);

  bmap = move_last(bmap, type, first, n);
  bmap = isl_basic_map_cow(bmap);
  bmap = insert_div_rows(bmap, n);
  if (!bmap)
    return NULL;

  bmap->dim = isl_space_drop_dims(bmap->dim, type, first, n);
  if (!bmap->dim)
    goto error;
  bmap = isl_basic_map_simplify(bmap);
  bmap = isl_basic_map_drop_redundant_divs(bmap);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

/* Turn the n dimensions of type type, starting at first
 * into existentially quantified variables.
 */
struct isl_basic_set *isl_basic_set_project_out(struct isl_basic_set *bset,
    enum isl_dim_type type, unsigned first, unsigned n)
{
  return bset_from_bmap(isl_basic_map_project_out(bset_to_bmap(bset),
              type, first, n));
}

/* Turn the n dimensions of type type, starting at first
 * into existentially quantified variables.
 */
__isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
    enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;

  if (n == 0)
    return map_space_reset(map, type);

  if (isl_map_check_range(map, type, first, n) < 0)
    return isl_map_free(map);

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  map->dim = isl_space_drop_dims(map->dim, type, first, n);
  if (!map->dim)
    goto error;

  for (i = 0; 66.6ki < map->n; ++i44.2k) {
    map->p[i] = isl_basic_map_project_out(map->p[i], type, first, n);
    if (!map->p[i])
      goto error;
  }

  return map;
error:
  isl_map_free(map);
  return NULL;
}

/* Turn all the dimensions of type "type", except the "n" starting at "first"
 * into existentially quantified variables.
 */
__isl_give isl_map *isl_map_project_onto(__isl_take isl_map *map,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  unsigned dim;

  if (isl_map_check_range(map, type, first, n) < 0)
    return isl_map_free(map);
  dim = isl_map_dim(map, type);
  map = isl_map_project_out(map, type, first + n, dim - (first + n));
  map = isl_map_project_out(map, type, 0, first);
  return map;
}

/* Turn the n dimensions of type type, starting at first
 * into existentially quantified variables.
 */
__isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
    enum isl_dim_type type, unsigned first, unsigned n)
{
  return set_from_map(isl_map_project_out(set_to_map(set),
            type, first, n));
}

/* Return a map that projects the elements in "set" onto their
 * "n" set dimensions starting at "first".
 * "type" should be equal to isl_dim_set.
 */
__isl_give isl_map *isl_set_project_onto_map(__isl_take isl_set *set,
  enum isl_dim_type type, unsigned first, unsigned n)
{
  int i;
  int dim;
  isl_map *map;

  if (!set)
    return NULL;
  if (type != isl_dim_set)
    isl_die0(isl_set_get_ctx(set), isl_error_invalid,
      "only set dimensions can be projected out", goto error);
  dim = isl_set_dim(set, isl_dim_set);
  if (first + n > dim || first + n < first)
    isl_die0(isl_set_get_ctx(set), isl_error_invalid,
      "index out of bounds", goto error);

  map = isl_map_from_domain(set);
  map = isl_map_add_dims(map, isl_dim_out, n);
  for (i = 0; i < n; ++i363)
    map = isl_map_equate(map, isl_dim_in, first + i,
          isl_dim_out, i);
  return map;
error:
  isl_set_free(set);
  return NULL;
}

static struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
{
  int i, j;

  for (i = 0; i < n; ++i198k) {
    j = isl_basic_map_alloc_div(bmap);
    if (j < 0)
      goto error;
    isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
  }
  return bmap;
error:
  isl_basic_map_free(bmap);
  return NULL;
}

struct isl_basic_map *isl_basic_map_apply_range(
    struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
{
  isl_space *dim_result = NULL;
  struct isl_basic_map *bmap;
  unsigned n_in, n_out, n, nparam, total, pos;
  struct isl_dim_map *dim_map1, *dim_map2;

  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
    goto error;
  if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_out,
            bmap2->dim, isl_dim_in))
    isl_die0(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
      "spaces don't match", goto error);

  dim_result = isl_space_join(isl_space_copy(bmap1->dim),
          isl_space_copy(bmap2->dim));

  n_in = isl_basic_map_dim(bmap1, isl_dim_in);
  n_out = isl_basic_map_dim(bmap2, isl_dim_out);
  n = isl_basic_map_dim(bmap1, isl_dim_out);
  nparam = isl_basic_map_dim(bmap1, isl_dim_param);

  total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
  dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
  dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
  isl_dim_map_div(dim_map1, bmap1, pos += n_out);
  isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);

  bmap = isl_basic_map_alloc_space(dim_result,
      bmap1->n_div + bmap2->n_div + n,
      bmap1->n_eq + bmap2->n_eq,
      bmap1->n_ineq + bmap2->n_ineq);
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
  bmap = add_divs(bmap, n);
  bmap = isl_basic_map_simplify(bmap);
  bmap = isl_basic_map_drop_redundant_divs(bmap);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap1);
  isl_basic_map_free(bmap2);
  return NULL;
}

struct isl_basic_set *isl_basic_set_apply(
    struct isl_basic_set *bset, struct isl_basic_map *bmap)
{
  if (!bset || !bmap)
    goto error;

  isl_assert(bset->ctx, isl_basic_map_compatible_domain(bmap, bset),
        goto error);

  return bset_from_bmap(isl_basic_map_apply_range(bset_to_bmap(bset),
              bmap));
error:
  isl_basic_set_free(bset);
  isl_basic_map_free(bmap);
  return NULL;
}

struct isl_basic_map *isl_basic_map_apply_domain(
    struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
{
  if (isl_basic_map_check_equal_params(bmap1, bmap2) < 0)
    goto error;
  if (!isl_space_tuple_is_equal(bmap1->dim, isl_dim_in,
          bmap2->dim, isl_dim_in))
    isl_die(isl_basic_map_get_ctx(bmap1), isl_error_invalid,
      "spaces don't match", goto error);

  bmap1 = isl_basic_map_reverse(bmap1);
  bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
  return isl_basic_map_reverse(bmap1);
error:
  isl_basic_map_free(bmap1);
  isl_basic_map_free(bmap2);
  return NULL;
}

/* Given two basic maps A -> f(A) and B -> g(B), construct a basic map
 * A \cap B -> f(A) + f(B)
 */
__isl_give isl_basic_map *isl_basic_map_sum(__isl_take isl_basic_map *bmap1,
  __isl_take isl_basic_map *bmap2)
{
  unsigned n_in, n_out, nparam, total, pos;
  struct isl_basic_map *bmap = NULL;
  struct isl_dim_map *dim_map1, *dim_map2;
  int i;

  if (!bmap1 || !bmap2)
    goto error;

  isl_assert(bmap1->ctx, isl_space_is_equal(bmap1->dim, bmap2->dim),
    goto error);

  nparam = isl_basic_map_dim(bmap1, isl_dim_param);
  n_in = isl_basic_map_dim(bmap1, isl_dim_in);
  n_out = isl_basic_map_dim(bmap1, isl_dim_out);

  total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + 2 * n_out;
  dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
  dim_map2 = isl_dim_map_alloc(bmap2->ctx, total);
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos);
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
  isl_dim_map_div(dim_map1, bmap1, pos += n_in + n_out);
  isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
  isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
  isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_out);

  bmap = isl_basic_map_alloc_space(isl_space_copy(bmap1->dim),
      bmap1->n_div + bmap2->n_div + 2 * n_out,
      bmap1->n_eq + bmap2->n_eq + n_out,
      bmap1->n_ineq + bmap2->n_ineq);
  for (i = 0; i < n_out; ++i24) {
    int j = isl_basic_map_alloc_equality(bmap);
    if (j < 0)
      goto error;
    isl_seq_clr(bmap->eq[j], 1+total);
    isl_int_set_si(bmap->eq[j][1+nparam+n_in+i], -1);
    isl_int_set_si(bmap->eq[j][1+pos+i], 1);
    isl_int_set_si(bmap->eq[j][1+pos-n_out+i], 1);
  }
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap1, dim_map1);
  bmap = isl_basic_map_add_constraints_dim_map(bmap, bmap2, dim_map2);
  bmap = add_divs(bmap, 2 * n_out);

  bmap = isl_basic_map_simplify(bmap);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  isl_basic_map_free(bmap1);
  isl_basic_map_free(bmap2);
  return NULL;
}

/* Given two maps A -> f(A) and B -> g(B), construct a map
 * A \cap B -> f(A) + f(B)
 */
__isl_give isl_map *isl_map_sum(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  struct isl_map *result;
  int i, j;

  if (!map1 || !map2)
    goto error;

  isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error);

  result = isl_map_alloc_space(isl_space_copy(map1->dim),
        map1->n * map2->n, 0);
  if (!result)
    goto error;
  for (i = 0; 24i < map1->n; ++i24)
    for (j = 0; 24j < map2->n; ++j24) {
      struct isl_basic_map *part;
      part = isl_basic_map_sum(
            isl_basic_map_copy(map1->p[i]),
            isl_basic_map_copy(map2->p[j]));
      if (isl_basic_map_is_empty(part))
        isl_basic_map_free(part);
      else
        result = isl_map_add_basic_map(result, part);
      if (!result)
        goto error;
    }
  isl_map_free(map1);
  isl_map_free(map2);
  return result;
error:
  isl_map_free(map1);
  isl_map_free(map2);
  return NULL;
}

__isl_give isl_set *isl_set_sum(__isl_take isl_set *set1,
  __isl_take isl_set *set2)
{
  return set_from_map(isl_map_sum(set_to_map(set1), set_to_map(set2)));
}

/* Given a basic map A -> f(A), construct A -> -f(A).
 */
__isl_give isl_basic_map *isl_basic_map_neg(__isl_take isl_basic_map *bmap)
{
  int i, j;
  unsigned off, n;

  bmap = isl_basic_map_cow(bmap);
  if (!bmap)
    return NULL;

  n = isl_basic_map_dim(bmap, isl_dim_out);
  off = isl_basic_map_offset(bmap, isl_dim_out);
  for (i = 0; i < bmap->n_eq; ++i1)
    for (j = 0; 1j < n; ++j1)
      isl_int_neg(bmap->eq[i][off+j], bmap->eq[i][off+j]);
  for (i = 0; i < bmap->n_ineq; ++i2)
    for (j = 0; 2j < n; ++j2)
      isl_int_neg(bmap->ineq[i][off+j], bmap->ineq[i][off+j]);
  for (i = 0; i < bmap->n_div; ++i0)
    for (j = 0; j < n; ++j)
      isl_int_neg(bmap->div[i][1+off+j], bmap->div[i][1+off+j]);
  bmap = isl_basic_map_gauss(bmap, NULL);
  return isl_basic_map_finalize(bmap);
}

__isl_give isl_basic_set *isl_basic_set_neg(__isl_take isl_basic_set *bset)
{
  return isl_basic_map_neg(bset);
}

/* Given a map A -> f(A), construct A -> -f(A).
 */
__isl_give isl_map *isl_map_neg(__isl_take isl_map *map)
{
  int i;

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  for (i = 0; 1i < map->n; ++i1) {
    map->p[i] = isl_basic_map_neg(map->p[i]);
    if (!map->p[i])
      goto error;
  }

  return map;
error:
  isl_map_free(map);
  return NULL;
}

__isl_give isl_set *isl_set_neg(__isl_take isl_set *set)
{
  return set_from_map(isl_map_neg(set_to_map(set)));
}

/* Given a basic map A -> f(A) and an integer d, construct a basic map
 * A -> floor(f(A)/d).
 */
__isl_give isl_basic_map *isl_basic_map_floordiv(__isl_take isl_basic_map *bmap,
    isl_int d)
{
  unsigned n_in, n_out, nparam, total, pos;
  struct isl_basic_map *result = NULL;
  struct isl_dim_map *dim_map;
  int i;

  if (!bmap)
    return NULL;

  nparam = isl_basic_map_dim(bmap, isl_dim_param);
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
  n_out = isl_basic_map_dim(bmap, isl_dim_out);

  total = nparam + n_in + n_out + bmap->n_div + n_out;
  dim_map = isl_dim_map_alloc(bmap->ctx, total);
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_param, pos = 0);
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_in, pos += nparam);
  isl_dim_map_div(dim_map, bmap, pos += n_in + n_out);
  isl_dim_map_dim(dim_map, bmap->dim, isl_dim_out, pos += bmap->n_div);

  result = isl_basic_map_alloc_space(isl_space_copy(bmap->dim),
      bmap->n_div + n_out,
      bmap->n_eq, bmap->n_ineq + 2 * n_out);
  result = isl_basic_map_add_constraints_dim_map(result, bmap, dim_map);
  result = add_divs(result, n_out);
  for (i = 0; i < n_out; ++i3.05k) {
    int j;
    j = isl_basic_map_alloc_inequality(result);
    if (j < 0)
      goto error;
    isl_seq_clr(result->ineq[j], 1+total);
    isl_int_neg(result->ineq[j][1+nparam+n_in+i], d);
    isl_int_set_si(result->ineq[j][1+pos+i], 1);
    j = isl_basic_map_alloc_inequality(result);
    if (j < 0)
      goto error;
    isl_seq_clr(result->ineq[j], 1+total);
    isl_int_set(result->ineq[j][1+nparam+n_in+i], d);
    isl_int_set_si(result->ineq[j][1+pos+i], -1);
    isl_int_sub_ui(result->ineq[j][0], d, 1);
  }

  result = isl_basic_map_simplify(result);
  return isl_basic_map_finalize(result);
error:
  isl_basic_map_free(result);
  return NULL;
}

/* Given a map A -> f(A) and an integer d, construct a map
 * A -> floor(f(A)/d).
 */
__isl_give isl_map *isl_map_floordiv(__isl_take isl_map *map, isl_int d)
{
  int i;

  map = isl_map_cow(map);
  if (!map)
    return NULL;

  ISL_F_CLR(map, ISL_MAP_DISJOINT);
  for (i = 0; i < map->n; ++i3.03k) {
    map->p[i] = isl_basic_map_floordiv(map->p[i], d);
    if (!map->p[i])
      goto error;
  }
  map = isl_map_unmark_normalized(map);

  return map;
error:
  isl_map_free(map);
  return NULL;
}

/* Given a map A -> f(A) and an integer d, construct a map
 * A -> floor(f(A)/d).
 */
__isl_give isl_map *isl_map_floordiv_val(__isl_take isl_map *map,
  __isl_take isl_val *d)
{
  if (!map || !d)
    goto error;
  if (!isl_val_is_int(d))
    isl_die0(isl_val_get_ctx(d), isl_error_invalid,
      "expecting integer denominator", goto error);
  map = isl_map_floordiv(map, d->n);
  isl_val_free(d);
  return map;
error:
  isl_map_free(map);
  isl_val_free(d);
  return NULL;
}

static __isl_give isl_basic_map *var_equal(__isl_take isl_basic_map *bmap,
  unsigned pos)
{
  int i;
  unsigned nparam;
  unsigned n_in;

  i = isl_basic_map_alloc_equality(bmap);
  if (i < 0)
    goto error;
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
  isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
  isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
  isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

/* Add a constraint to "bmap" expressing i_pos < o_pos
 */
static __isl_give isl_basic_map *var_less(__isl_take isl_basic_map *bmap,
  unsigned pos)
{
  int i;
  unsigned nparam;
  unsigned n_in;

  i = isl_basic_map_alloc_inequality(bmap);
  if (i < 0)
    goto error;
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
  isl_int_set_si(bmap->ineq[i][0], -1);
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

/* Add a constraint to "bmap" expressing i_pos <= o_pos
 */
static __isl_give isl_basic_map *var_less_or_equal(
  __isl_take isl_basic_map *bmap, unsigned pos)
{
  int i;
  unsigned nparam;
  unsigned n_in;

  i = isl_basic_map_alloc_inequality(bmap);
  if (i < 0)
    goto error;
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

/* Add a constraint to "bmap" expressing i_pos > o_pos
 */
static __isl_give isl_basic_map *var_more(__isl_take isl_basic_map *bmap,
  unsigned pos)
{
  int i;
  unsigned nparam;
  unsigned n_in;

  i = isl_basic_map_alloc_inequality(bmap);
  if (i < 0)
    goto error;
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
  isl_int_set_si(bmap->ineq[i][0], -1);
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

/* Add a constraint to "bmap" expressing i_pos >= o_pos
 */
static __isl_give isl_basic_map *var_more_or_equal(
  __isl_take isl_basic_map *bmap, unsigned pos)
{
  int i;
  unsigned nparam;
  unsigned n_in;

  i = isl_basic_map_alloc_inequality(bmap);
  if (i < 0)
    goto error;
  nparam = isl_basic_map_dim(bmap, isl_dim_param);
  n_in = isl_basic_map_dim(bmap, isl_dim_in);
  isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
  isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
  isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
  return isl_basic_map_finalize(bmap);
error:
  isl_basic_map_free(bmap);
  return NULL;
}

__isl_give isl_basic_map *isl_basic_map_equal(
  __isl_take isl_space *dim, unsigned n_equal)
{
  int i;
  struct isl_basic_map *bmap;
  bmap = isl_basic_map_alloc_space(dim, 0, n_equal, 0);
  if (!bmap)
    return NULL;
  for (i = 0; 2.84ki < n_equal && bmap2.25k; ++i2.25k)
    bmap = var_equal(bmap, i);
  return isl_basic_map_finalize(bmap);
}

/* Return a relation on of dimension "dim" expressing i_[0..pos] << o_[0..pos]
 */
__isl_give isl_basic_map *isl_basic_map_less_at(__isl_take isl_space *dim,
  unsigned pos)
{
  int i;
  struct isl_basic_map *bmap;
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
  if (!bmap)
    return NULL;
  for (i = 0; 1.49ki < pos && bmap840; ++i840)
    bmap = var_equal(bmap, i);
  if (bmap)
    bmap = var_less(bmap, pos);
  return isl_basic_map_finalize(bmap);
}

/* Return a relation on "dim" expressing i_[0..pos] <<= o_[0..pos]
 */
__isl_give isl_basic_map *isl_basic_map_less_or_equal_at(
  __isl_take isl_space *dim, unsigned pos)
{
  int i;
  isl_basic_map *bmap;

  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
  for (i = 0; i < pos; ++i1.09k)
    bmap = var_equal(bmap, i);
  bmap = var_less_or_equal(bmap, pos);
  return isl_basic_map_finalize(bmap);
}

/* Return a relation on "dim" expressing i_pos > o_pos
 */
__isl_give isl_basic_map *isl_basic_map_more_at(__isl_take isl_space *dim,
  unsigned pos)
{
  int i;
  struct isl_basic_map *bmap;
  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
  if (!bmap)
    return NULL;
  for (i = 0; 16.9ki < pos && bmap7.76k; ++i7.76k)
    bmap = var_equal(bmap, i);
  if (bmap)
    bmap = var_more(bmap, pos);
  return isl_basic_map_finalize(bmap);
}

/* Return a relation on "dim" expressing i_[0..pos] >>= o_[0..pos]
 */
__isl_give isl_basic_map *isl_basic_map_more_or_equal_at(
  __isl_take isl_space *dim, unsigned pos)
{
  int i;
  isl_basic_map *bmap;

  bmap = isl_basic_map_alloc_space(dim, 0, pos, 1);
  for (i = 0; i < pos; ++i2.56k)
    bmap = var_equal(bmap, i);
  bmap = var_more_or_equal(bmap, pos);
  return isl_basic_map_finalize(bmap);
}

static __isl_give isl_map *map_lex_lte_first(__isl_take isl_space *dims,
  unsigned n, int equal)
{
  struct isl_map *map;
  int i;

  if (n == 0 && equal22)
    return isl_map_universe(dims);

  map = isl_map_alloc_space(isl_space_copy(dims), n, ISL_MAP_DISJOINT);

  for (i = 0; i + 1 < n; ++i1.27k)
    map = isl_map_add_basic_map(map,
          isl_basic_map_less_at(isl_space_copy(dims), i));
  if (n > 0) {
    if (equal)
      map = isl_map_add_basic_map(map,
            isl_basic_map_less_or_equal_at(dims, n - 1));
    else
      map = isl_map_add_basic_map(map,
            isl_basic_map_less_at(dims, n - 1));
  } else
    isl_space_free(dims);

  return map;
}

static __isl_give isl_map *map_lex_lte(__isl_take isl_space *dims, int equal)
{
  if (!dims)
    return NULL;
  return map_lex_lte_first(dims, dims->n_out, equal);
}

__isl_give isl_map *isl_map_lex_lt_first(__isl_take isl_space *dim, unsigned n)
{
  return map_lex_lte_first(dim, n, 0);
}

__isl_give isl_map *isl_map_lex_le_first(__isl_take isl_space *dim, unsigned n)
{
  return map_lex_lte_first(dim, n, 1);
}

__isl_give isl_map *isl_map_lex_lt(__isl_take isl_space *set_dim)
{
  return map_lex_lte(isl_space_map_from_set(set_dim), 0);
}

__isl_give isl_map *isl_map_lex_le(__isl_take isl_space *set_dim)
{
  return map_lex_lte(isl_space_map_from_set(set_dim), 1);
}

static __isl_give isl_map *map_lex_gte_first(__isl_take isl_space *dims,
  unsigned n, int equal)
{
  struct isl_map *map;
  int i;

  if (n == 0 && equal0)
    return isl_map_universe(dims);

  map = isl_map_alloc_space(isl_space_copy(dims), n, ISL_MAP_DISJOINT);

  for (i = 0; i + 1 < n; ++i2.87k)
    map = isl_map_add_basic_map(map,
          isl_basic_map_more_at(isl_space_copy(dims), i));
  if (n > 0) {
    if (equal)
      map = isl_map_add_basic_map(map,
            isl_basic_map_more_or_equal_at(dims, n - 1));
    else
      map = isl_map_add_basic_map(map,
            isl_basic_map_more_at(dims, n - 1));
  } else
    isl_space_free(dims);

  return map;
}

static __isl_give isl_map *map_lex_gte(__isl_take isl_space *dims, int equal)
{
  if (!dims)
    return NULL;
  return map_lex_gte_first(dims, dims->n_out, equal);
}

__isl_give isl_map *isl_map_lex_gt_first(__isl_take isl_space *dim, unsigned n)
{
  return map_lex_gte_first(dim, n, 0);
}

__isl_give isl_map *isl_map_lex_ge_first(__isl_take isl_space *dim, unsigned n)
{
  return map_lex_gte_first(dim, n, 1);
}

__isl_give isl_map *isl_map_lex_gt(__isl_take isl_space *set_dim)
{
  return map_lex_gte(isl_space_map_from_set(set_dim), 0);
}

__isl_give isl_map *isl_map_lex_ge(__isl_take isl_space *set_dim)
{
  return map_lex_gte(isl_space_map_from_set(set_dim), 1);
}

__isl_give isl_map *isl_set_lex_le_set(__isl_take isl_set *set1,
  __isl_take isl_set *set2)
{
  isl_map *map;
  map = isl_map_lex_le(isl_set_get_space(set1));
  map = isl_map_intersect_domain(map, set1);
  map = isl_map_intersect_range(map, set2);
  return map;
}

__isl_give isl_map *isl_set_lex_lt_set(__isl_take isl_set *set1,
  __isl_take isl_set *set2)
{
  isl_map *map;
  map = isl_map_lex_lt(isl_set_get_space(set1));
  map = isl_map_intersect_domain(map, set1);
  map = isl_map_intersect_range(map, set2);
  return map;
}

__isl_give isl_map *isl_set_lex_ge_set(__isl_take isl_set *set1,
  __isl_take isl_set *set2)
{
  isl_map *map;
  map = isl_map_lex_ge(isl_set_get_space(set1));
  map = isl_map_intersect_domain(map, set1);
  map = isl_map_intersect_range(map, set2);
  return map;
}

__isl_give isl_map *isl_set_lex_gt_set(__isl_take isl_set *set1,
  __isl_take isl_set *set2)
{
  isl_map *map;
  map = isl_map_lex_gt(isl_set_get_space(set1));
  map = isl_map_intersect_domain(map, set1);
  map = isl_map_intersect_range(map, set2);
  return map;
}

__isl_give isl_map *isl_map_lex_le_map(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  isl_map *map;
  map = isl_map_lex_le(isl_space_range(isl_map_get_space(map1)));
  map = isl_map_apply_domain(map, isl_map_reverse(map1));
  map = isl_map_apply_range(map, isl_map_reverse(map2));
  return map;
}

__isl_give isl_map *isl_map_lex_lt_map(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  isl_map *map;
  map = isl_map_lex_lt(isl_space_range(isl_map_get_space(map1)));
  map = isl_map_apply_domain(map, isl_map_reverse(map1));
  map = isl_map_apply_range(map, isl_map_reverse(map2));
  return map;
}

__isl_give isl_map *isl_map_lex_ge_map(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  isl_map *map;
  map = isl_map_lex_ge(isl_space_range(isl_map_get_space(map1)));
  map = isl_map_apply_domain(map, isl_map_reverse(map1));
  map = isl_map_apply_range(map, isl_map_reverse(map2));
  return map;
}

__isl_give isl_map *isl_map_lex_gt_map(__isl_take isl_map *map1,
  __isl_take isl_map *map2)
{
  isl_map *map;
  map = isl_map_lex_gt(isl_space_range(isl_map_get_space(map1)));
  map = isl_map_apply_domain(map, isl_map_reverse(map1));
  map = isl_map_apply_range(map, isl_map_reverse(map2));
  return map;
}

/* For a div d = floor(f/m), add the constraint
 *
 *    f - m d >= 0
 */
static isl_stat add_upper_div_constraint(__isl_keep isl_basic_map *bmap,
  unsigned pos, isl_int *div)
{
  int i;
  unsigned total = isl_basic_map_total_dim(bmap);

  i = isl_basic_map_alloc_inequality(bmap);
  if (i < 0)
    return isl_stat_error;
  isl_seq_cpy(bmap->ineq[i], div + 1, 1 + total);
  isl_int_neg(bmap->ineq[i][1 + pos], div[0]);

  return isl_stat_ok;
}

/* For a div d = floor(f/m), add the constraint
 *
 *    -(f-(m-1)) + m d >= 0
 */
static isl_stat add_lower_div_constraint(__isl_keep isl_basic_map *bmap,
  unsigned pos, isl_int *div)
{
  int i;
  unsigned total = isl_basic_map_total_dim(bmap);

  i = isl_basic_map_alloc_inequality(bmap);
  if (i < 0)
    return isl_stat_error;
  isl_seq_neg(bmap->ineq[i], div + 1, 1 + total);
  isl_int_set(bmap->ineq[i][1 + pos], div[0]);
  isl_int_add(bmap->ineq[i][0], bmap->ineq[i][0], bmap->ineq[i][1 + pos]);
  isl_int_sub_ui(bmap->ineq[i][0], bmap->ineq[i][0], 1);

  return isl_stat_ok;
}

/* For a div d = floor(f/m), add the constraints
 *
 *    f - m d >= 0
 *    -(f-(m-1)) + m d >= 0
 *
 * Note that the second constraint is the negation of
 *
 *    f - m d >= m
 */
int isl_basic_map_add_div_constraints_var(__isl_keep isl_basic_map *bmap,
  unsigned pos, isl_int *div)
{
  if (add_upper_div_constraint(bmap, pos, div) < 0)
    return -1;
  if (add_lower_div_constraint(bmap, pos, div) < 0)
    return -1;
  return 0;
}

int isl_basic_set_add_div_constraints_var(__isl_keep isl_basic_set *bset,
  unsigned pos, isl_int *div)
{
  return isl_basic_map_add_div_constraints_var(bset_to_bmap(bset),
              pos, div);
}

int isl_basic_map_add_div_constraints(struct isl_basic_map *bmap, unsigned div)
{
  unsigned total = isl_basic_map_total_dim(bmap);
  unsigned div_pos = total - bmap->n_div + div;

  return isl_basic_map_add_div_constraints_var(bmap, div_pos,
              bmap->div[div]);
}

/* For each known div d = floor(f/m), add the constraints
 *
 *    f - m d >= 0
 *    -(f-(m-1)) + m d >= 0
 *
 * Remove duplicate constraints in case of some these div constraints
 * already appear in "bmap".
 */
__isl_give isl_basic_map *isl_basic_map_add_known_div_constraints(
  __isl_take isl_basic_map *bmap)
{
  unsigned n_div;

  if (!bmap)
    return NULL;
  n_div = isl_basic_map_dim(bmap, isl_dim_div);
  if (n_div == 0)
    return bmap;

  bmap = add_known_div_constraints(bmap);
  bmap = isl_basic_map_remove_duplicate_constraints(bmap, NULL, 0);
  bmap = isl_basic_map_finalize(bmap);
  return bmap;
}

/* Add the div constraint of sign "sign" for div "div" of "bmap".
 *
 * In particular, if this div is of the form d = floor(f/m),
 * then add the constraint
 *
 *    f - m d >= 0
 *
 * if sign < 0 or the constraint
 *
 *    -(f-(m-1)) + m d >= 0
 *
 * if sign > 0.
 */
int isl_basic_map_add_div_constraint(__isl_keep isl_basic_map *bmap,
  unsigned div, int sign)
{
  unsigned total;
5329

Coverage Report

Created: 2019-07-24 05:18