isl_coalesce.c File Reference

#include "isl_map_private.h"
#include "isl_tab.h"

Go to the source code of this file.

Defines

#define STATUS_ERROR   -1
#define STATUS_REDUNDANT   1
#define STATUS_VALID   2
#define STATUS_SEPARATE   3
#define STATUS_CUT   4
#define STATUS_ADJ_EQ   5
#define STATUS_ADJ_INEQ   6

Functions

static int status_in (struct isl_ctx *ctx, isl_int *ineq, struct isl_tab *tab)
static int * eq_status_in (struct isl_map *map, int i, int j, struct isl_tab **tabs)
static int * ineq_status_in (struct isl_map *map, int i, int j, struct isl_tab **tabs)
static int any (int *con, unsigned len, int status)
static int count (int *con, unsigned len, int status)
static int all (int *con, unsigned len, int status)
static void drop (struct isl_map *map, int i, struct isl_tab **tabs)
static int fuse (struct isl_map *map, int i, int j, struct isl_tab **tabs, int *ineq_i, int *ineq_j)
static int check_facets (struct isl_map *map, int i, int j, struct isl_tab **tabs, int *ineq_i, int *ineq_j)
static int check_adj_ineq (struct isl_map *map, int i, int j, struct isl_tab **tabs, int *ineq_i, int *ineq_j)
static int contains (struct isl_map *map, int i, int *ineq_i, struct isl_tab *tab)
static int check_adj_eq (struct isl_map *map, int i, int j, struct isl_tab **tabs, int *eq_i, int *ineq_i, int *eq_j, int *ineq_j)
static int coalesce_pair (struct isl_map *map, int i, int j, struct isl_tab **tabs)
static struct isl_map * coalesce (struct isl_map *map, struct isl_tab **tabs)
struct isl_map * isl_map_coalesce (struct isl_map *map)
struct isl_set * isl_set_coalesce (struct isl_set *set)

Define Documentation

#define STATUS_ERROR   -1

Definition at line 4 of file isl_coalesce.c.

#define STATUS_REDUNDANT   1

Definition at line 5 of file isl_coalesce.c.

#define STATUS_VALID   2

Definition at line 6 of file isl_coalesce.c.

#define STATUS_SEPARATE   3

Definition at line 7 of file isl_coalesce.c.

#define STATUS_CUT   4

Definition at line 8 of file isl_coalesce.c.

#define STATUS_ADJ_EQ   5

Definition at line 9 of file isl_coalesce.c.

#define STATUS_ADJ_INEQ   6

Definition at line 10 of file isl_coalesce.c.

Function Documentation

static int status_in ( struct isl_ctx *  ctx,
isl_int *  ineq,
struct isl_tab *  tab 
) [static]

Definition at line 12 of file isl_coalesce.c.

00013 {
00014         enum isl_ineq_type type = isl_tab_ineq_type(ctx, tab, ineq);
00015         switch (type) {
00016         case isl_ineq_error:            return STATUS_ERROR;
00017         case isl_ineq_redundant:        return STATUS_VALID;
00018         case isl_ineq_separate:         return STATUS_SEPARATE;
00019         case isl_ineq_cut:              return STATUS_CUT;
00020         case isl_ineq_adj_eq:           return STATUS_ADJ_EQ;
00021         case isl_ineq_adj_ineq:         return STATUS_ADJ_INEQ;
00022         }
00023 }

static int* eq_status_in ( struct isl_map *  map,
int  i,
int  j,
struct isl_tab **  tabs 
) [static]

Definition at line 31 of file isl_coalesce.c.

00033 {
00034         int k, l;
00035         int *eq = isl_calloc_array(map->ctx, int, 2 * map->p[i]->n_eq);
00036         unsigned dim;
00037 
00038         dim = isl_basic_map_total_dim(map->p[i]);
00039         for (k = 0; k < map->p[i]->n_eq; ++k) {
00040                 for (l = 0; l < 2; ++l) {
00041                         isl_seq_neg(map->p[i]->eq[k], map->p[i]->eq[k], 1+dim);
00042                         eq[2 * k + l] = status_in(map->ctx, map->p[i]->eq[k],
00043                                                                     tabs[j]);
00044                         if (eq[2 * k + l] == STATUS_ERROR)
00045                                 goto error;
00046                 }
00047                 if (eq[2 * k] == STATUS_SEPARATE ||
00048                     eq[2 * k + 1] == STATUS_SEPARATE)
00049                         break;
00050         }
00051 
00052         return eq;
00053 error:
00054         free(eq);
00055         return NULL;
00056 }

static int* ineq_status_in ( struct isl_map *  map,
int  i,
int  j,
struct isl_tab **  tabs 
) [static]

Definition at line 61 of file isl_coalesce.c.

00063 {
00064         int k;
00065         unsigned n_eq = map->p[i]->n_eq;
00066         int *ineq = isl_calloc_array(map->ctx, int, map->p[i]->n_ineq);
00067 
00068         for (k = 0; k < map->p[i]->n_ineq; ++k) {
00069                 if (isl_tab_is_redundant(map->ctx, tabs[i], n_eq + k)) {
00070                         ineq[k] = STATUS_REDUNDANT;
00071                         continue;
00072                 }
00073                 ineq[k] = status_in(map->ctx, map->p[i]->ineq[k], tabs[j]);
00074                 if (ineq[k] == STATUS_ERROR)
00075                         goto error;
00076                 if (ineq[k] == STATUS_SEPARATE)
00077                         break;
00078         }
00079 
00080         return ineq;
00081 error:
00082         free(ineq);
00083         return NULL;
00084 }

static int any ( int *  con,
unsigned  len,
int  status 
) [static]

Definition at line 86 of file isl_coalesce.c.

00087 {
00088         int i;
00089 
00090         for (i = 0; i < len ; ++i)
00091                 if (con[i] == status)
00092                         return 1;
00093         return 0;
00094 }

static int count ( int *  con,
unsigned  len,
int  status 
) [static]

Definition at line 96 of file isl_coalesce.c.

00097 {
00098         int i;
00099         int c = 0;
00100 
00101         for (i = 0; i < len ; ++i)
00102                 if (con[i] == status)
00103                         c++;
00104         return c;
00105 }

static int all ( int *  con,
unsigned  len,
int  status 
) [static]

Definition at line 107 of file isl_coalesce.c.

00108 {
00109         int i;
00110 
00111         for (i = 0; i < len ; ++i) {
00112                 if (con[i] == STATUS_REDUNDANT)
00113                         continue;
00114                 if (con[i] != status)
00115                         return 0;
00116         }
00117         return 1;
00118 }

static void drop ( struct isl_map *  map,
int  i,
struct isl_tab **  tabs 
) [static]

Definition at line 120 of file isl_coalesce.c.

00121 {
00122         isl_basic_map_free(map->p[i]);
00123         isl_tab_free(map->ctx, tabs[i]);
00124 
00125         if (i != map->n - 1) {
00126                 map->p[i] = map->p[map->n - 1];
00127                 tabs[i] = tabs[map->n - 1];
00128         }
00129         tabs[map->n - 1] = NULL;
00130         map->n--;
00131 }

static int fuse ( struct isl_map *  map,
int  i,
int  j,
struct isl_tab **  tabs,
int *  ineq_i,
int *  ineq_j 
) [static]

Definition at line 136 of file isl_coalesce.c.

00138 {
00139         int k, l;
00140         struct isl_basic_map *fused = NULL;
00141         struct isl_tab *fused_tab = NULL;
00142         unsigned total = isl_basic_map_total_dim(map->p[i]);
00143 
00144         fused = isl_basic_map_alloc_dim(isl_dim_copy(map->p[i]->dim),
00145                         map->p[i]->n_div,
00146                         map->p[i]->n_eq + map->p[j]->n_eq,
00147                         map->p[i]->n_ineq + map->p[j]->n_ineq);
00148         if (!fused)
00149                 goto error;
00150 
00151         for (k = 0; k < map->p[i]->n_eq; ++k) {
00152                 int l = isl_basic_map_alloc_equality(fused);
00153                 isl_seq_cpy(fused->eq[l], map->p[i]->eq[k], 1 + total);
00154         }
00155 
00156         for (k = 0; k < map->p[j]->n_eq; ++k) {
00157                 int l = isl_basic_map_alloc_equality(fused);
00158                 isl_seq_cpy(fused->eq[l], map->p[j]->eq[k], 1 + total);
00159         }
00160 
00161         for (k = 0; k < map->p[i]->n_ineq; ++k) {
00162                 if (ineq_i[k] != STATUS_VALID)
00163                         continue;
00164                 l = isl_basic_map_alloc_inequality(fused);
00165                 isl_seq_cpy(fused->ineq[l], map->p[i]->ineq[k], 1 + total);
00166         }
00167 
00168         for (k = 0; k < map->p[j]->n_ineq; ++k) {
00169                 if (ineq_j[k] != STATUS_VALID)
00170                         continue;
00171                 l = isl_basic_map_alloc_inequality(fused);
00172                 isl_seq_cpy(fused->ineq[l], map->p[j]->ineq[k], 1 + total);
00173         }
00174 
00175         for (k = 0; k < map->p[i]->n_div; ++k) {
00176                 int l = isl_basic_map_alloc_div(fused);
00177                 isl_seq_cpy(fused->div[l], map->p[i]->div[k], 1 + 1 + total);
00178         }
00179 
00180         fused = isl_basic_map_gauss(fused, NULL);
00181         ISL_F_SET(fused, ISL_BASIC_MAP_FINAL);
00182 
00183         fused_tab = isl_tab_from_basic_map(fused);
00184         fused_tab = isl_tab_detect_redundant(map->ctx, fused_tab);
00185         if (!fused_tab)
00186                 goto error;
00187 
00188         isl_basic_map_free(map->p[i]);
00189         map->p[i] = fused;
00190         isl_tab_free(map->ctx, tabs[i]);
00191         tabs[i] = fused_tab;
00192         drop(map, j, tabs);
00193 
00194         return 1;
00195 error:
00196         isl_basic_map_free(fused);
00197         return -1;
00198 }

static int check_facets ( struct isl_map *  map,
int  i,
int  j,
struct isl_tab **  tabs,
int *  ineq_i,
int *  ineq_j 
) [static]

Definition at line 219 of file isl_coalesce.c.

00221 {
00222         int k, l;
00223         struct isl_tab_undo *snap;
00224         unsigned n_eq = map->p[i]->n_eq;
00225 
00226         snap = isl_tab_snap(map->ctx, tabs[i]);
00227 
00228         for (k = 0; k < map->p[i]->n_ineq; ++k) {
00229                 if (ineq_i[k] != STATUS_CUT)
00230                         continue;
00231                 tabs[i] = isl_tab_select_facet(map->ctx, tabs[i], n_eq + k);
00232                 for (l = 0; l < map->p[j]->n_ineq; ++l) {
00233                         int stat;
00234                         if (ineq_j[l] != STATUS_CUT)
00235                                 continue;
00236                         stat = status_in(map->ctx, map->p[j]->ineq[l], tabs[i]);
00237                         if (stat != STATUS_VALID)
00238                                 break;
00239                 }
00240                 isl_tab_rollback(map->ctx, tabs[i], snap);
00241                 if (l < map->p[j]->n_ineq)
00242                         break;
00243         }
00244 
00245         if (k < map->p[i]->n_ineq)
00246                 /* BAD CUT PAIR */
00247                 return 0;
00248         return fuse(map, i, j, tabs, ineq_i, ineq_j);
00249 }

static int check_adj_ineq ( struct isl_map *  map,
int  i,
int  j,
struct isl_tab **  tabs,
int *  ineq_i,
int *  ineq_j 
) [static]

Definition at line 278 of file isl_coalesce.c.

00280 {
00281         int changed = 0;
00282 
00283         if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT) ||
00284             any(ineq_j, map->p[j]->n_ineq, STATUS_CUT))
00285                 /* ADJ INEQ CUT */
00286                 ;
00287         else if (count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) == 1 &&
00288                  count(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ) == 1)
00289                 changed = fuse(map, i, j, tabs, ineq_i, ineq_j);
00290         /* else ADJ INEQ TOO MANY */
00291 
00292         return changed;
00293 }

static int contains ( struct isl_map *  map,
int  i,
int *  ineq_i,
struct isl_tab *  tab 
) [static]

Definition at line 298 of file isl_coalesce.c.

00300 {
00301         int k, l;
00302         unsigned dim;
00303 
00304         dim = isl_basic_map_total_dim(map->p[i]);
00305         for (k = 0; k < map->p[i]->n_eq; ++k) {
00306                 for (l = 0; l < 2; ++l) {
00307                         int stat;
00308                         isl_seq_neg(map->p[i]->eq[k], map->p[i]->eq[k], 1+dim);
00309                         stat = status_in(map->ctx, map->p[i]->eq[k], tab);
00310                         if (stat != STATUS_VALID)
00311                                 return 0;
00312                 }
00313         }
00314 
00315         for (k = 0; k < map->p[i]->n_ineq; ++k) {
00316                 int stat;
00317                 if (ineq_i[l] == STATUS_REDUNDANT)
00318                         continue;
00319                 stat = status_in(map->ctx, map->p[i]->ineq[k], tab);
00320                 if (stat != STATUS_VALID)
00321                         return 0;
00322         }
00323         return 1;
00324 }

static int check_adj_eq ( struct isl_map *  map,
int  i,
int  j,
struct isl_tab **  tabs,
int *  eq_i,
int *  ineq_i,
int *  eq_j,
int *  ineq_j 
) [static]

Definition at line 349 of file isl_coalesce.c.

00351 {
00352         int changed = 0;
00353         int super;
00354         int k;
00355         struct isl_tab_undo *snap, *snap2;
00356         unsigned n_eq = map->p[i]->n_eq;
00357 
00358         if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) &&
00359             any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ))
00360                 /* ADJ EQ TOO MANY */
00361                 return 0;
00362 
00363         if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ))
00364                 return check_adj_eq(map, j, i, tabs,
00365                                         eq_j, ineq_j, eq_i, ineq_i);
00366 
00367         /* j has an equality adjacent to an inequality in i */
00368 
00369         if (any(ineq_i, map->p[i]->n_ineq, STATUS_CUT))
00370                 /* ADJ EQ CUT */
00371                 return 0;
00372         if (count(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ) != 1 ||
00373             count(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) != 1 ||
00374             any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ) ||
00375             any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) ||
00376             any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ))
00377                 /* ADJ EQ TOO MANY */
00378                 return 0;
00379 
00380         for (k = 0; k < map->p[i]->n_ineq ; ++k)
00381                 if (ineq_i[k] == STATUS_ADJ_EQ)
00382                         break;
00383 
00384         snap = isl_tab_snap(map->ctx, tabs[i]);
00385         tabs[i] = isl_tab_relax(map->ctx, tabs[i], n_eq + k);
00386         snap2 = isl_tab_snap(map->ctx, tabs[i]);
00387         tabs[i] = isl_tab_select_facet(map->ctx, tabs[i], n_eq + k);
00388         super = contains(map, j, ineq_j, tabs[i]);
00389         if (super) {
00390                 isl_tab_rollback(map->ctx, tabs[i], snap2);
00391                 map->p[i] = isl_basic_map_cow(map->p[i]);
00392                 if (!map->p[i])
00393                         return -1;
00394                 isl_int_add_ui(map->p[i]->ineq[k][0], map->p[i]->ineq[k][0], 1);
00395                 ISL_F_SET(map->p[i], ISL_BASIC_MAP_FINAL);
00396                 drop(map, j, tabs);
00397                 changed = 1;
00398         } else
00399                 isl_tab_rollback(map->ctx, tabs[i], snap);
00400 
00401         return changed;
00402 }

static int coalesce_pair ( struct isl_map *  map,
int  i,
int  j,
struct isl_tab **  tabs 
) [static]

Definition at line 455 of file isl_coalesce.c.

00457 {
00458         int changed = 0;
00459         int *eq_i = NULL;
00460         int *eq_j = NULL;
00461         int *ineq_i = NULL;
00462         int *ineq_j = NULL;
00463 
00464         eq_i = eq_status_in(map, i, j, tabs);
00465         if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ERROR))
00466                 goto error;
00467         if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_SEPARATE))
00468                 goto done;
00469 
00470         eq_j = eq_status_in(map, j, i, tabs);
00471         if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_ERROR))
00472                 goto error;
00473         if (any(eq_j, 2 * map->p[j]->n_eq, STATUS_SEPARATE))
00474                 goto done;
00475 
00476         ineq_i = ineq_status_in(map, i, j, tabs);
00477         if (any(ineq_i, map->p[i]->n_ineq, STATUS_ERROR))
00478                 goto error;
00479         if (any(ineq_i, map->p[i]->n_ineq, STATUS_SEPARATE))
00480                 goto done;
00481 
00482         ineq_j = ineq_status_in(map, j, i, tabs);
00483         if (any(ineq_j, map->p[j]->n_ineq, STATUS_ERROR))
00484                 goto error;
00485         if (any(ineq_j, map->p[j]->n_ineq, STATUS_SEPARATE))
00486                 goto done;
00487 
00488         if (all(eq_i, 2 * map->p[i]->n_eq, STATUS_VALID) &&
00489             all(ineq_i, map->p[i]->n_ineq, STATUS_VALID)) {
00490                 drop(map, j, tabs);
00491                 changed = 1;
00492         } else if (all(eq_j, 2 * map->p[j]->n_eq, STATUS_VALID) &&
00493                    all(ineq_j, map->p[j]->n_ineq, STATUS_VALID)) {
00494                 drop(map, i, tabs);
00495                 changed = 1;
00496         } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_CUT) ||
00497                    any(eq_j, 2 * map->p[j]->n_eq, STATUS_CUT)) {
00498                 /* BAD CUT */
00499         } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_EQ) ||
00500                    any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_EQ)) {
00501                 /* ADJ EQ PAIR */
00502         } else if (any(eq_i, 2 * map->p[i]->n_eq, STATUS_ADJ_INEQ) ||
00503                    any(eq_j, 2 * map->p[j]->n_eq, STATUS_ADJ_INEQ)) {
00504                 changed = check_adj_eq(map, i, j, tabs,
00505                                         eq_i, ineq_i, eq_j, ineq_j);
00506         } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_EQ) ||
00507                    any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_EQ)) {
00508                 /* Can't happen */
00509                 /* BAD ADJ INEQ */
00510         } else if (any(ineq_i, map->p[i]->n_ineq, STATUS_ADJ_INEQ) ||
00511                    any(ineq_j, map->p[j]->n_ineq, STATUS_ADJ_INEQ)) {
00512                 changed = check_adj_ineq(map, i, j, tabs, ineq_i, ineq_j);
00513         } else
00514                 changed = check_facets(map, i, j, tabs, ineq_i, ineq_j);
00515 
00516 done:
00517         free(eq_i);
00518         free(eq_j);
00519         free(ineq_i);
00520         free(ineq_j);
00521         return changed;
00522 error:
00523         free(eq_i);
00524         free(eq_j);
00525         free(ineq_i);
00526         free(ineq_j);
00527         return -1;
00528 }

static struct isl_map* coalesce ( struct isl_map *  map,
struct isl_tab **  tabs 
) [static, read]

Definition at line 530 of file isl_coalesce.c.

00531 {
00532         int i, j;
00533 
00534         for (i = 0; i < map->n - 1; ++i)
00535                 for (j = i + 1; j < map->n; ++j) {
00536                         int changed;
00537                         changed = coalesce_pair(map, i, j, tabs);
00538                         if (changed < 0)
00539                                 goto error;
00540                         if (changed)
00541                                 return coalesce(map, tabs);
00542                 }
00543         return map;
00544 error:
00545         isl_map_free(map);
00546         return NULL;
00547 }

struct isl_map* isl_map_coalesce ( struct isl_map *  map  )  [read]

Definition at line 553 of file isl_coalesce.c.

00554 {
00555         int i;
00556         unsigned n;
00557         struct isl_ctx *ctx;
00558         struct isl_tab **tabs = NULL;
00559 
00560         if (!map)
00561                 return NULL;
00562 
00563         if (map->n <= 1)
00564                 return map;
00565 
00566         map = isl_map_align_divs(map);
00567 
00568         tabs = isl_calloc_array(map->ctx, struct isl_tab *, map->n);
00569         if (!tabs)
00570                 goto error;
00571 
00572         n = map->n;
00573         ctx = map->ctx;
00574         for (i = 0; i < map->n; ++i) {
00575                 tabs[i] = isl_tab_from_basic_map(map->p[i]);
00576                 if (!tabs[i])
00577                         goto error;
00578                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT))
00579                         tabs[i] = isl_tab_detect_equalities(map->ctx, tabs[i]);
00580                 if (!ISL_F_ISSET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT))
00581                         tabs[i] = isl_tab_detect_redundant(map->ctx, tabs[i]);
00582         }
00583         for (i = map->n - 1; i >= 0; --i)
00584                 if (tabs[i]->empty)
00585                         drop(map, i, tabs);
00586 
00587         map = coalesce(map, tabs);
00588 
00589         if (map)
00590                 for (i = 0; i < map->n; ++i) {
00591                         map->p[i] = isl_basic_map_update_from_tab(map->p[i],
00592                                                                     tabs[i]);
00593                         map->p[i] = isl_basic_map_finalize(map->p[i]);
00594                         if (!map->p[i])
00595                                 goto error;
00596                         ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_IMPLICIT);
00597                         ISL_F_SET(map->p[i], ISL_BASIC_MAP_NO_REDUNDANT);
00598                 }
00599 
00600         for (i = 0; i < n; ++i)
00601                 isl_tab_free(ctx, tabs[i]);
00602 
00603         free(tabs);
00604 
00605         return map;
00606 error:
00607         if (tabs)
00608                 for (i = 0; i < n; ++i)
00609                         isl_tab_free(ctx, tabs[i]);
00610         free(tabs);
00611         return NULL;
00612 }

struct isl_set* isl_set_coalesce ( struct isl_set *  set  )  [read]

Definition at line 618 of file isl_coalesce.c.

00619 {
00620         (struct isl_set *)isl_map_coalesce((struct isl_map *)set);
00621 }

Generated on Fri Jul 17 16:32:57 2009 for CLooG / ISL by  doxygen 1.5.9