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 guarded_qp(__isl_take isl_qpolynomial *qp, void *user)
  81 {
  82         struct isl_bound *bound = (struct isl_bound *)user;
  83         int r;
  84
  85         r = isl_qpolynomial_as_polynomial_on_domain(qp, bound->bset,
  86                                                     &guarded_poly_bound, user);
  87         isl_qpolynomial_free(qp);
  88         return r;
  89 }
  90
  91 static int basic_guarded_fold(__isl_take isl_basic_set *bset, void *user)
  92 {
  93         struct isl_bound *bound = (struct isl_bound *)user;
  94         int r;
  95
  96         bound->bset = bset;
  97         r = isl_qpolynomial_fold_foreach_qpolynomial(bound->fold,
  98                                                         &guarded_qp, user);
  99         isl_basic_set_free(bset);
 100         return r;
 101 }
 102
 103 static int guarded_fold(__isl_take isl_set *set,
 104         __isl_take isl_qpolynomial_fold *fold, void *user)
 105 {
 106         struct isl_bound *bound = (struct isl_bound *)user;
 107
 108         if (!set || !fold)
 109                 goto error;
 110
 111         set = isl_set_make_disjoint(set);
 112
 113         bound->fold = fold;
 114         bound->type = isl_qpolynomial_fold_get_type(fold);
 115
 116         if (isl_set_foreach_basic_set(set, &basic_guarded_fold, bound) < 0)
 117                 goto error;
 118
 119         isl_set_free(set);
 120         isl_qpolynomial_fold_free(fold);
 121
 122         return 0;
 123 error:
 124         isl_set_free(set);
 125         isl_qpolynomial_fold_free(fold);
 126         return -1;
 127 }
 128
 129 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_bound(
 130         __isl_take isl_pw_qpolynomial_fold *pwf, int *tight)
 131 {
 132         isl_dim *dim;
 133         unsigned nvar;
 134         struct isl_bound bound;
 135         int covers;
 136
 137         if (!pwf)
 138                 return NULL;
 139
 140         dim = isl_pw_qpolynomial_fold_get_dim(pwf);
 141         nvar = isl_dim_size(dim, isl_dim_set);
 142
 143         if (isl_pw_qpolynomial_fold_is_zero(pwf)) {
 144                 isl_pw_qpolynomial_fold_free(pwf);
 145                 dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 146                 if (tight)
 147                         *tight = 1;
 148                 return isl_pw_qpolynomial_fold_zero(dim);
 149         }
 150
 151         if (nvar == 0) {
 152                 isl_dim_free(dim);
 153                 if (tight)
 154                         *tight = 1;
 155                 return pwf;
 156         }
 157
 158         dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 159
 160         bound.pwf = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 161         bound.pwf_tight = isl_pw_qpolynomial_fold_zero(isl_dim_copy(dim));
 162         bound.check_tight = !!tight;
 163
 164         if (isl_pw_qpolynomial_fold_foreach_lifted_piece(pwf,
 165                                                         guarded_fold, &bound) < 0)
 166                 goto error;
 167
 168         covers = isl_pw_qpolynomial_fold_covers(bound.pwf_tight, bound.pwf);
 169         if (covers < 0)
 170                 goto error;
 171
 172         if (tight)
 173                 *tight = covers;
 174
 175         isl_dim_free(dim);
 176         isl_pw_qpolynomial_fold_free(pwf);
 177
 178         if (covers) {
 179                 isl_pw_qpolynomial_fold_free(bound.pwf);
 180                 return bound.pwf_tight;
 181         }
 182
 183         bound.pwf = isl_pw_qpolynomial_fold_add(bound.pwf, bound.pwf_tight);
 184
 185         return bound.pwf;
 186 error:
 187         isl_pw_qpolynomial_fold_free(bound.pwf_tight);
 188         isl_pw_qpolynomial_fold_free(bound.pwf);
 189         isl_pw_qpolynomial_fold_free(pwf);
 190         isl_dim_free(dim);
 191         return NULL;
 192 }
 193
 194 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
 195         __isl_take isl_pw_qpolynomial *pwqp, enum isl_fold type, int *tight)
 196 {
 197         isl_pw_qpolynomial_fold *pwf;
 198
 199         pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(type, pwqp);
 200         return isl_pw_qpolynomial_fold_bound(pwf, tight);
 201 }