basis_reduction_tab.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   8  */
   9
  10 #include <assert.h>
  11 #include <isl_map_private.h>
  12 #include <isl_seq.h>
  13 #include "isl_tab.h"
  14 #include <isl_config.h>
  15
  16 struct tab_lp {
  17         struct isl_ctx  *ctx;
  18         struct isl_vec  *row;
  19         struct isl_tab  *tab;
  20         struct isl_tab_undo     **stack;
  21         isl_int         *obj;
  22         isl_int          opt;
  23         isl_int          opt_denom;
  24         isl_int          tmp;
  25         isl_int          tmp2;
  26         int              neq;
  27         unsigned         dim;
  28         /* number of constraints in initial product tableau */
  29         int              con_offset;
  30         /* objective function has fixed or no integer value */
  31         int              is_fixed;
  32 };
  33
  34 static struct tab_lp *init_lp(struct isl_tab *tab);
  35 static void set_lp_obj(struct tab_lp *lp, isl_int *row, int dim);
  36 static int solve_lp(struct tab_lp *lp);
  37 static void get_obj_val(struct tab_lp* lp, mpq_t *F);
  38 static void delete_lp(struct tab_lp *lp);
  39 static int add_lp_row(struct tab_lp *lp, isl_int *row, int dim);
  40 static void get_alpha(struct tab_lp* lp, int row, mpq_t *alpha);
  41 static int del_lp_row(struct tab_lp *lp) WARN_UNUSED;
  42 static int cut_lp_to_hyperplane(struct tab_lp *lp, isl_int *row);
  43
  44 #define GBR_LP                              struct tab_lp
  45 #define GBR_type                            mpq_t
  46 #define GBR_init(v)                         mpq_init(v)
  47 #define GBR_clear(v)                        mpq_clear(v)
  48 #define GBR_set(a,b)                        mpq_set(a,b)
  49 #define GBR_set_ui(a,b)                     mpq_set_ui(a,b,1)
  50 #define GBR_mul(a,b,c)                      mpq_mul(a,b,c)
  51 #define GBR_lt(a,b)                         (mpq_cmp(a,b) < 0)
  52 #define GBR_is_zero(a)                      (mpq_sgn(a) == 0)
  53 #define GBR_floor(a,b)                      mpz_fdiv_q(a,mpq_numref(b),mpq_denref(b))
  54 #define GBR_ceil(a,b)                       mpz_cdiv_q(a,mpq_numref(b),mpq_denref(b))
  55 #define GBR_lp_init(P)                      init_lp(P)
  56 #define GBR_lp_set_obj(lp, obj, dim)        set_lp_obj(lp, obj, dim)
  57 #define GBR_lp_solve(lp)                    solve_lp(lp)
  58 #define GBR_lp_get_obj_val(lp, F)           get_obj_val(lp, F)
  59 #define GBR_lp_delete(lp)                   delete_lp(lp)
  60 #define GBR_lp_next_row(lp)                 lp->neq
  61 #define GBR_lp_add_row(lp, row, dim)        add_lp_row(lp, row, dim)
  62 #define GBR_lp_get_alpha(lp, row, alpha)    get_alpha(lp, row, alpha)
  63 #define GBR_lp_del_row(lp)                  del_lp_row(lp)
  64 #define GBR_lp_is_fixed(lp)                 (lp)->is_fixed
  65 #define GBR_lp_cut(lp, obj)                 cut_lp_to_hyperplane(lp, obj)
  66 #include "basis_reduction_templ.c"
  67
  68 /* Set up a tableau for the Cartesian product of bset with itself.
  69  * This could be optimized by first setting up a tableau for bset
  70  * and then performing the Cartesian product on the tableau.
  71  */
  72 static struct isl_tab *gbr_tab(struct isl_tab *tab, struct isl_vec *row)
  73 {
  74         unsigned dim;
  75         struct isl_tab *prod;
  76
  77         if (!tab || !row)
  78                 return NULL;
  79
  80         dim = tab->n_var;
  81         prod = isl_tab_product(tab, tab);
  82         if (isl_tab_extend_cons(prod, 3 * dim + 1) < 0) {
  83                 isl_tab_free(prod);
  84                 return NULL;
  85         }
  86         return prod;
  87 }
  88
  89 static struct tab_lp *init_lp(struct isl_tab *tab)
  90 {
  91         struct tab_lp *lp = NULL;
  92
  93         if (!tab)
  94                 return NULL;
  95
  96         lp = isl_calloc_type(tab->mat->ctx, struct tab_lp);
  97         if (!lp)
  98                 return NULL;
  99
 100         isl_int_init(lp->opt);
 101         isl_int_init(lp->opt_denom);
 102         isl_int_init(lp->tmp);
 103         isl_int_init(lp->tmp2);
 104
 105         lp->dim = tab->n_var;
 106
 107         lp->ctx = tab->mat->ctx;
 108         isl_ctx_ref(lp->ctx);
 109
 110         lp->stack = isl_alloc_array(lp->ctx, struct isl_tab_undo *, lp->dim);
 111
 112         lp->row = isl_vec_alloc(lp->ctx, 1 + 2 * lp->dim);
 113         if (!lp->row)
 114                 goto error;
 115         lp->tab = gbr_tab(tab, lp->row);
 116         if (!lp->tab)
 117                 goto error;
 118         lp->con_offset = lp->tab->n_con;
 119         lp->obj = NULL;
 120         lp->neq = 0;
 121
 122         return lp;
 123 error:
 124         delete_lp(lp);
 125         return NULL;
 126 }
 127
 128 static void set_lp_obj(struct tab_lp *lp, isl_int *row, int dim)
 129 {
 130         lp->obj = row;
 131 }
 132
 133 static int solve_lp(struct tab_lp *lp)
 134 {
 135         enum isl_lp_result res;
 136         unsigned flags = 0;
 137
 138         lp->is_fixed = 0;
 139
 140         isl_int_set_si(lp->row->el[0], 0);
 141         isl_seq_cpy(lp->row->el + 1, lp->obj, lp->dim);
 142         isl_seq_neg(lp->row->el + 1 + lp->dim, lp->obj, lp->dim);
 143         if (lp->neq)
 144                 flags = ISL_TAB_SAVE_DUAL;
 145         res = isl_tab_min(lp->tab, lp->row->el, lp->ctx->one,
 146                           &lp->opt, &lp->opt_denom, flags);
 147         isl_int_mul_ui(lp->opt_denom, lp->opt_denom, 2);
 148         if (isl_int_abs_lt(lp->opt, lp->opt_denom)) {
 149                 struct isl_vec *sample = isl_tab_get_sample_value(lp->tab);
 150                 if (!sample)
 151                         return -1;
 152                 isl_seq_inner_product(lp->obj, sample->el + 1, lp->dim, &lp->tmp);
 153                 isl_seq_inner_product(lp->obj, sample->el + 1 + lp->dim, lp->dim, &lp->tmp2);
 154                 isl_int_cdiv_q(lp->tmp, lp->tmp, sample->el[0]);
 155                 isl_int_fdiv_q(lp->tmp2, lp->tmp2, sample->el[0]);
 156                 if (isl_int_ge(lp->tmp, lp->tmp2))
 157                         lp->is_fixed = 1;
 158                 isl_vec_free(sample);
 159         }
 160         isl_int_divexact_ui(lp->opt_denom, lp->opt_denom, 2);
 161         if (res != isl_lp_ok)
 162                 return -1;
 163         return 0;
 164 }
 165
 166 /* The current objective function has a fixed (or no) integer value.
 167  * Cut the tableau to the hyperplane that fixes this value in
 168  * both halves of the tableau.
 169  * Return 1 if the resulting tableau is empty.
 170  */
 171 static int cut_lp_to_hyperplane(struct tab_lp *lp, isl_int *row)
 172 {
 173         enum isl_lp_result res;
 174
 175         isl_int_set_si(lp->row->el[0], 0);
 176         isl_seq_cpy(lp->row->el + 1, row, lp->dim);
 177         isl_seq_clr(lp->row->el + 1 + lp->dim, lp->dim);
 178         res = isl_tab_min(lp->tab, lp->row->el, lp->ctx->one,
 179                           &lp->tmp, NULL, 0);
 180         if (res != isl_lp_ok)
 181                 return -1;
 182
 183         isl_int_neg(lp->row->el[0], lp->tmp);
 184         if (isl_tab_add_eq(lp->tab, lp->row->el) < 0)
 185                 return -1;
 186
 187         isl_seq_cpy(lp->row->el + 1 + lp->dim, row, lp->dim);
 188         isl_seq_clr(lp->row->el + 1, lp->dim);
 189         if (isl_tab_add_eq(lp->tab, lp->row->el) < 0)
 190                 return -1;
 191
 192         lp->con_offset += 2;
 193
 194         return lp->tab->empty;
 195 }
 196
 197 static void get_obj_val(struct tab_lp* lp, mpq_t *F)
 198 {
 199         isl_int_neg(mpq_numref(*F), lp->opt);
 200         isl_int_set(mpq_denref(*F), lp->opt_denom);
 201 }
 202
 203 static void delete_lp(struct tab_lp *lp)
 204 {
 205         if (!lp)
 206                 return;
 207
 208         isl_int_clear(lp->opt);
 209         isl_int_clear(lp->opt_denom);
 210         isl_int_clear(lp->tmp);
 211         isl_int_clear(lp->tmp2);
 212         isl_vec_free(lp->row);
 213         free(lp->stack);
 214         isl_tab_free(lp->tab);
 215         isl_ctx_deref(lp->ctx);
 216         free(lp);
 217 }
 218
 219 static int add_lp_row(struct tab_lp *lp, isl_int *row, int dim)
 220 {
 221         lp->stack[lp->neq] = isl_tab_snap(lp->tab);
 222
 223         isl_int_set_si(lp->row->el[0], 0);
 224         isl_seq_cpy(lp->row->el + 1, row, lp->dim);
 225         isl_seq_neg(lp->row->el + 1 + lp->dim, row, lp->dim);
 226
 227         if (isl_tab_add_valid_eq(lp->tab, lp->row->el) < 0)
 228                 return -1;
 229
 230         return lp->neq++;
 231 }
 232
 233 static void get_alpha(struct tab_lp* lp, int row, mpq_t *alpha)
 234 {
 235         row += lp->con_offset;
 236         isl_int_neg(mpq_numref(*alpha), lp->tab->dual->el[1 + row]);
 237         isl_int_set(mpq_denref(*alpha), lp->tab->dual->el[0]);
 238 }
 239
 240 static int del_lp_row(struct tab_lp *lp)
 241 {
 242         lp->neq--;
 243         return isl_tab_rollback(lp->tab, lp->stack[lp->neq]);
 244 }