isl_bound.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <isl_bound.h>
  12 #include <isl_range.h>
  13 #include <isl_polynomial_private.h>
  14
  15 static int compressed_guarded_poly_bound(__isl_take isl_basic_set *bset,
  16         __isl_take isl_qpolynomial *poly, void *user)
  17 {
  18         struct isl_bound *bound = (struct isl_bound *)user;
  19         return isl_qpolynomial_bound_on_domain_range(bset, poly, bound);
  20 }
  21
  22 static int guarded_poly_bound(__isl_take isl_basic_set *bset,
  23         __isl_take isl_qpolynomial *poly, void *user)
  24 {
  25         struct isl_bound *bound = (struct isl_bound *)user;
  26         isl_pw_qpolynomial_fold *top_pwf;
  27         isl_pw_qpolynomial_fold *top_pwf_tight;
  28         isl_dim *dim;
  29         isl_morph *morph;
  30         unsigned orig_nvar, final_nvar;
  31         int r;
  32
  33         bset = isl_basic_set_detect_equalities(bset);
  34
  35         if (!bset)
  36                 goto error;
  37
  38         if (bset->n_eq == 0)
  39                 return compressed_guarded_poly_bound(bset, poly, user);
  40
  41         orig_nvar = isl_basic_set_dim(bset, isl_dim_set);
  42
  43         morph = isl_basic_set_full_compression(bset);
  44
  45         bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
  46         poly = isl_qpolynomial_morph(poly, isl_morph_copy(morph));
  47
  48         final_nvar = isl_basic_set_dim(bset, isl_dim_set);
  49
  50         dim = isl_morph_get_ran_dim(morph);
  51         dim = isl_dim_drop(dim, isl_dim_set, 0, isl_dim_size(dim, isl_dim_set));
  52
  53         top_pwf = bound->pwf;
  54         top_pwf_tight = bound->pwf_tight;
  55
  56         bound->pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
  57         bound->pwf_tight = isl_pw_qpolynomial_fold_zero(dim);
  58
  59         r = compressed_guarded_poly_bound(bset, poly, user);
  60
  61         morph = isl_morph_remove_dom_dims(morph, isl_dim_set, 0, orig_nvar);
  62         morph = isl_morph_remove_ran_dims(morph, isl_dim_set, 0, final_nvar);
  63         morph = isl_morph_inverse(morph);
  64
  65         bound->pwf = isl_pw_qpolynomial_fold_morph(bound->pwf,
  66                                                         isl_morph_copy(morph));
  67         bound->pwf_tight = isl_pw_qpolynomial_fold_morph(bound->pwf_tight, morph);
  68
  69         bound->pwf = isl_pw_qpolynomial_fold_add(top_pwf, bound->pwf);
  70         bound->pwf_tight = isl_pw_qpolynomial_fold_add(top_pwf_tight,
  71                                                         bound->pwf_tight);
  72
  73         return r;
  74 error:
  75         isl_basic_set_free(bset);
  76         isl_qpolynomial_free(poly);
  77         return -1;
  78 }
  79
  80 static int basic_guarded_bound(__isl_take isl_basic_set *bset, void *user)
  81 {
  82         struct isl_bound *bound = (struct isl_bound *)user;
  83         int r;
  84
  85         r = isl_qpolynomial_as_polynomial_on_domain(bound->qp, bset,
  86                                                     &guarded_poly_bound, user);
  87         isl_basic_set_free(bset);
  88         return r;
  89 }
  90
  91 static int guarded_bound(__isl_take isl_set *set,
  92         __isl_take isl_qpolynomial *qp, void *user)
  93 {
  94         struct isl_bound *bound = (struct isl_bound *)user;
  95
  96         if (!set || !qp)
  97                 goto error;
  98
  99         set = isl_set_make_disjoint(set);
 100
 101         bound->qp = qp;
 102
 103         if (isl_set_foreach_basic_set(set, &basic_guarded_bound, bound) < 0)
 104                 goto error;
 105
 106         isl_set_free(set);
 107         isl_qpolynomial_free(qp);
 108
 109         return 0;
 110 error:
 111         isl_set_free(set);
 112         isl_qpolynomial_free(qp);
 113         return -1;
 114 }
 115
 116 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 117         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
 118 {
 119         isl_dim *dim;
 120         unsigned nvar;
 121         struct isl_bound bound;
 122         int covers;
 123
 124         if (!pwqp)
 125                 return NULL;
 126
 127         dim = isl_pw_qpolynomial_get_dim(pwqp);
 128         nvar = isl_dim_size(dim, isl_dim_set);
 129
 130         if (isl_pw_qpolynomial_is_zero(pwqp)) {
 131                 isl_pw_qpolynomial_free(pwqp);
 132                 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 133                 if (tight)
 134                         *tight = 1;
 135                 return isl_pw_qpolynomial_fold_zero(dim);
 136         }
 137
 138         if (nvar == 0) {
 139                 isl_dim_free(dim);
 140                 if (tight)
 141                         *tight = 1;
 142                 return isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 143         }
 144
 145         dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 146
 147         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 148         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 149         bound.type = type;
 150         bound.check_tight = !!tight;
 151
 152         if (isl_pw_qpolynomial_foreach_lifted_piece(pwqp, guarded_bound, &bound))
 153                 goto error;
 154
 155         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
 156         if (covers < 0)
 157                 goto error;
 158
 159         if (tight)
 160                 *tight = covers;
 161
 162         isl_dim_free(dim);
 163         isl_pw_qpolynomial_free(pwqp);
 164
 165         if (covers) {
 166                 isl_pw_qpolynomial_fold_free(bound.pwf);
 167                 return bound.pwf_tight;
 168         }
 169
 170         bound.pwf = isl_pw_qpolynomial_fold_add(bound.pwf, bound.pwf_tight);
 171
 172         return bound.pwf;
 173 error:
 174         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 175         isl_pw_qpolynomial_fold_free(bound.pwf);
 176         isl_dim_free(dim);
 177         isl_pw_qpolynomial_free(pwqp);
 178         return NULL;
 179 }