isl_factorization.c

   1 /*
   2  * Copyright 2005-2007 Universiteit Leiden
   3  * Copyright 2008-2009 Katholieke Universiteit Leuven
   4  * Copyright 2010      INRIA Saclay
   5  *
   6  * Use of this software is governed by the GNU LGPLv2.1 license
   7  *
   8  * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
   9  * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
  10  * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
  11  * B-3001 Leuven, Belgium
  12  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  13  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  14  */
  15
  16 #include <isl_factorization.h>
  17 #include <isl_dim_private.h>
  18
  19 static __isl_give isl_factorizer *isl_factorizer_alloc(
  20         __isl_take isl_morph *morph, int n_group)
  21 {
  22         isl_factorizer *f = NULL;
  23         int *len = NULL;
  24
  25         if (!morph)
  26                 return NULL;
  27
  28         if (n_group > 0) {
  29                 len = isl_alloc_array(morph->dom->ctx, int, n_group);
  30                 if (!len)
  31                         goto error;
  32         }
  33
  34         f = isl_alloc_type(morph->dom->ctx, struct isl_factorizer);
  35         if (!f)
  36                 goto error;
  37
  38         f->morph = morph;
  39         f->n_group = n_group;
  40         f->len = len;
  41
  42         return f;
  43 error:
  44         free(len);
  45         isl_morph_free(morph);
  46         return NULL;
  47 }
  48
  49 void isl_factorizer_free(__isl_take isl_factorizer *f)
  50 {
  51         if (!f)
  52                 return;
  53
  54         isl_morph_free(f->morph);
  55         free(f->len);
  56         free(f);
  57 }
  58
  59 void isl_factorizer_dump(__isl_take isl_factorizer *f, FILE *out)
  60 {
  61         int i;
  62
  63         if (!f)
  64                 return;
  65
  66         isl_morph_dump(f->morph, out);
  67         fprintf(out, "[");
  68         for (i = 0; i < f->n_group; ++i) {
  69                 if (i)
  70                         fprintf(out, ", ");
  71                 fprintf(out, "%d", f->len[i]);
  72         }
  73         fprintf(out, "]\n");
  74 }
  75
  76 __isl_give isl_factorizer *isl_factorizer_identity(__isl_keep isl_basic_set *bset)
  77 {
  78         return isl_factorizer_alloc(isl_morph_identity(bset), 0);
  79 }
  80
  81 __isl_give isl_factorizer *isl_factorizer_groups(__isl_keep isl_basic_set *bset,
  82         __isl_take isl_mat *Q, __isl_take isl_mat *U, int n, int *len)
  83 {
  84         int i;
  85         unsigned nvar;
  86         unsigned ovar;
  87         isl_dim *dim;
  88         isl_basic_set *dom;
  89         isl_basic_set *ran;
  90         isl_morph *morph;
  91         isl_factorizer *f;
  92         isl_mat *id;
  93
  94         if (!bset || !Q || !U)
  95                 goto error;
  96
  97         ovar = 1 + isl_dim_offset(bset->dim, isl_dim_set);
  98         id = isl_mat_identity(bset->ctx, ovar);
  99         Q = isl_mat_diagonal(isl_mat_copy(id), Q);
 100         U = isl_mat_diagonal(id, U);
 101
 102         nvar = isl_basic_set_dim(bset, isl_dim_set);
 103         dim = isl_basic_set_get_dim(bset);
 104         dom = isl_basic_set_universe(isl_dim_copy(dim));
 105         dim = isl_dim_drop(dim, isl_dim_set, 0, nvar);
 106         dim = isl_dim_add(dim, isl_dim_set, nvar);
 107         ran = isl_basic_set_universe(dim);
 108         morph = isl_morph_alloc(dom, ran, Q, U);
 109         f = isl_factorizer_alloc(morph, n);
 110         if (!f)
 111                 return NULL;
 112         for (i = 0; i < n; ++i)
 113                 f->len[i] = len[i];
 114         return f;
 115 error:
 116         isl_mat_free(Q);
 117         isl_mat_free(U);
 118         return NULL;
 119 }
 120
 121 struct isl_factor_groups {
 122         int *pos;               /* for each column: row position of pivot */
 123         int *group;             /* group to which a column belongs */
 124         int *cnt;               /* number of columns in the group */
 125         int *rowgroup;          /* group to which a constraint belongs */
 126 };
 127
 128 /* Initialize isl_factor_groups structure: find pivot row positions,
 129  * each column initially belongs to its own group and the groups
 130  * of the constraints are still unknown.
 131  */
 132 static int init_groups(struct isl_factor_groups *g, __isl_keep isl_mat *H)
 133 {
 134         int i, j;
 135
 136         if (!H)
 137                 return -1;
 138
 139         g->pos = isl_alloc_array(H->ctx, int, H->n_col);
 140         g->group = isl_alloc_array(H->ctx, int, H->n_col);
 141         g->cnt = isl_alloc_array(H->ctx, int, H->n_col);
 142         g->rowgroup = isl_alloc_array(H->ctx, int, H->n_row);
 143
 144         if (!g->pos || !g->group || !g->cnt || !g->rowgroup)
 145                 return -1;
 146
 147         for (i = 0; i < H->n_row; ++i)
 148                 g->rowgroup[i] = -1;
 149         for (i = 0, j = 0; i < H->n_col; ++i) {
 150                 for ( ; j < H->n_row; ++j)
 151                         if (!isl_int_is_zero(H->row[j][i]))
 152                                 break;
 153                 g->pos[i] = j;
 154         }
 155         for (i = 0; i < H->n_col; ++i) {
 156                 g->group[i] = i;
 157                 g->cnt[i] = 1;
 158         }
 159
 160         return 0;
 161 }
 162
 163 /* Update group[k] to the group column k belongs to.
 164  * When merging two groups, only the group of the current
 165  * group leader is changed.  Here we change the group of
 166  * the other members to also point to the group that the
 167  * old group leader now points to.
 168  */
 169 static void update_group(struct isl_factor_groups *g, int k)
 170 {
 171         int p = g->group[k];
 172         while (g->cnt[p] == 0)
 173                 p = g->group[p];
 174         g->group[k] = p;
 175 }
 176
 177 /* Merge group i with all groups of the subsequent columns
 178  * with non-zero coefficients in row j of H.
 179  * (The previous columns are all zero; otherwise we would have handled
 180  * the row before.)
 181  */
 182 static int update_group_i_with_row_j(struct isl_factor_groups *g, int i, int j,
 183         __isl_keep isl_mat *H)
 184 {
 185         int k;
 186
 187         g->rowgroup[j] = g->group[i];
 188         for (k = i + 1; k < H->n_col && j >= g->pos[k]; ++k) {
 189                 update_group(g, k);
 190                 update_group(g, i);
 191                 if (g->group[k] != g->group[i] &&
 192                     !isl_int_is_zero(H->row[j][k])) {
 193                         isl_assert(H->ctx, g->cnt[g->group[k]] != 0, return -1);
 194                         isl_assert(H->ctx, g->cnt[g->group[i]] != 0, return -1);
 195                         if (g->group[i] < g->group[k]) {
 196                                 g->cnt[g->group[i]] += g->cnt[g->group[k]];
 197                                 g->cnt[g->group[k]] = 0;
 198                                 g->group[g->group[k]] = g->group[i];
 199                         } else {
 200                                 g->cnt[g->group[k]] += g->cnt[g->group[i]];
 201                                 g->cnt[g->group[i]] = 0;
 202                                 g->group[g->group[i]] = g->group[k];
 203                         }
 204                 }
 205         }
 206
 207         return 0;
 208 }
 209
 210 /* Update the group information based on the constraint matrix.
 211  */
 212 static int update_groups(struct isl_factor_groups *g, __isl_keep isl_mat *H)
 213 {
 214         int i, j;
 215
 216         for (i = 0; i < H->n_col && g->cnt[0] < H->n_col; ++i) {
 217                 if (g->pos[i] == H->n_row)
 218                         continue; /* A line direction */
 219                 if (g->rowgroup[g->pos[i]] == -1)
 220                         g->rowgroup[g->pos[i]] = i;
 221                 for (j = g->pos[i] + 1; j < H->n_row; ++j) {
 222                         if (isl_int_is_zero(H->row[j][i]))
 223                                 continue;
 224                         if (g->rowgroup[j] != -1)
 225                                 continue;
 226                         if (update_group_i_with_row_j(g, i, j, H) < 0)
 227                                 return -1;
 228                 }
 229         }
 230
 231         return 0;
 232 }
 233
 234 static void clear_groups(struct isl_factor_groups *g)
 235 {
 236         if (!g)
 237                 return;
 238         free(g->pos);
 239         free(g->group);
 240         free(g->cnt);
 241         free(g->rowgroup);
 242 }
 243
 244 /* Determine if the set variables of the basic set can be factorized and
 245  * return the results in an isl_factorizer.
 246  *
 247  * The algorithm works by first computing the Hermite normal form
 248  * and then grouping columns linked by one or more constraints together,
 249  * where a constraints "links" two or more columns if the constraint
 250  * has nonzero coefficients in the columns.
 251  */
 252 __isl_give isl_factorizer *isl_basic_set_factorizer(
 253         __isl_keep isl_basic_set *bset)
 254 {
 255         int i, j, n, done;
 256         isl_mat *H, *U, *Q;
 257         unsigned nvar;
 258         struct isl_factor_groups g = { 0 };
 259         isl_factorizer *f;
 260
 261         if (!bset)
 262                 return NULL;
 263
 264         isl_assert(bset->ctx, isl_basic_set_dim(bset, isl_dim_div) == 0,
 265                 return NULL);
 266
 267         nvar = isl_basic_set_dim(bset, isl_dim_set);
 268         if (nvar <= 1)
 269                 return isl_factorizer_identity(bset);
 270
 271         H = isl_mat_alloc(bset->ctx, bset->n_eq + bset->n_ineq, nvar);
 272         if (!H)
 273                 return NULL;
 274         isl_mat_sub_copy(bset->ctx, H->row, bset->eq, bset->n_eq,
 275                 0, 1 + isl_dim_offset(bset->dim, isl_dim_set), nvar);
 276         isl_mat_sub_copy(bset->ctx, H->row + bset->n_eq, bset->ineq, bset->n_ineq,
 277                 0, 1 + isl_dim_offset(bset->dim, isl_dim_set), nvar);
 278         H = isl_mat_left_hermite(H, 0, &U, &Q);
 279
 280         if (init_groups(&g, H) < 0)
 281                 goto error;
 282         if (update_groups(&g, H) < 0)
 283                 goto error;
 284
 285         if (g.cnt[0] == nvar) {
 286                 isl_mat_free(H);
 287                 isl_mat_free(U);
 288                 isl_mat_free(Q);
 289                 clear_groups(&g);
 290
 291                 return isl_factorizer_identity(bset);
 292         }
 293
 294         done = 0;
 295         n = 0;
 296         while (done != nvar) {
 297                 int group = g.group[done];
 298                 for (i = 1; i < g.cnt[group]; ++i) {
 299                         if (g.group[done + i] == group)
 300                                 continue;
 301                         for (j = done + g.cnt[group]; j < nvar; ++j)
 302                                 if (g.group[j] == group)
 303                                         break;
 304                         g.group[j] = g.group[done + i];
 305                         Q = isl_mat_swap_rows(Q, done + i, j);
 306                         U = isl_mat_swap_cols(U, done + i, j);
 307                 }
 308                 done += g.cnt[group];
 309                 g.pos[n++] = g.cnt[group];
 310         }
 311
 312         f = isl_factorizer_groups(bset, Q, U, n, g.pos);
 313
 314         isl_mat_free(H);
 315         clear_groups(&g);
 316
 317         return f;
 318 error:
 319         isl_mat_free(H);
 320         isl_mat_free(U);
 321         isl_mat_free(Q);
 322         clear_groups(&g);
 323         return NULL;
 324 }