isl_local.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2014      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  11  */
  12
  13 #include <isl_mat_private.h>
  14 #include <isl_seq.h>
  15 #include <isl_local.h>
  16
  17 /* Return the isl_ctx to which "local" belongs.
  18  */
  19 isl_ctx *isl_local_get_ctx(__isl_keep isl_local *local)
  20 {
  21         if (!local)
  22                 return NULL;
  23
  24         return isl_mat_get_ctx(local);
  25 }
  26
  27 /* Return the number of local variables (isl_dim_div),
  28  * the number of other variables (isl_dim_set) or
  29  * the total number of variables (isl_dim_all) in "local".
  30  *
  31  * Other types do not have any meaning for an isl_local object.
  32  */
  33 int isl_local_dim(__isl_keep isl_local *local, enum isl_dim_type type)
  34 {
  35         isl_mat *mat = local;
  36
  37         if (!local)
  38                 return 0;
  39         if (type == isl_dim_div)
  40                 return isl_mat_rows(mat);
  41         if (type == isl_dim_all)
  42                 return isl_mat_cols(mat) - 2;
  43         if (type == isl_dim_set)
  44                 return isl_local_dim(local, isl_dim_all) -
  45                         isl_local_dim(local, isl_dim_div);
  46         isl_die(isl_local_get_ctx(local), isl_error_unsupported,
  47                 "unsupported dimension type", return 0);
  48 }
  49
  50 /* Check that "pos" is a valid position for a variable in "local".
  51  */
  52 static isl_stat isl_local_check_pos(__isl_keep isl_local *local, int pos)
  53 {
  54         if (!local)
  55                 return isl_stat_error;
  56         if (pos < 0 || pos >= isl_local_dim(local, isl_dim_div))
  57                 isl_die(isl_local_get_ctx(local), isl_error_invalid,
  58                         "position out of bounds", return isl_stat_error);
  59         return isl_stat_ok;
  60 }
  61
  62 /* Given local variables "local",
  63  * is the variable at position "pos" marked as not having
  64  * an explicit representation?
  65  * Note that even if this variable is not marked in this way and therefore
  66  * does have an explicit representation, this representation may still
  67  * depend (indirectly) on other local variables that do not
  68  * have an explicit representation.
  69  */
  70 isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_local *local, int pos)
  71 {
  72         isl_mat *mat = local;
  73
  74         if (isl_local_check_pos(local, pos) < 0)
  75                 return isl_bool_error;
  76         return isl_int_is_zero(mat->row[pos][0]);
  77 }
  78
  79 /* Given local variables "local",
  80  * does the variable at position "pos" have a complete explicit representation?
  81  * Having a complete explicit representation requires not only
  82  * an explicit representation, but also that all local variables
  83  * that appear in this explicit representation in turn have
  84  * a complete explicit representation.
  85  */
  86 isl_bool isl_local_div_is_known(__isl_keep isl_local *local, int pos)
  87 {
  88         isl_bool marked;
  89         int i, n, off;
  90         isl_mat *mat = local;
  91
  92         if (isl_local_check_pos(local, pos) < 0)
  93                 return isl_bool_error;
  94
  95         marked = isl_local_div_is_marked_unknown(local, pos);
  96         if (marked < 0 || marked)
  97                 return isl_bool_not(marked);
  98
  99         n = isl_local_dim(local, isl_dim_div);
 100         off = isl_mat_cols(mat) - n;
 101
 102         for (i = n - 1; i >= 0; --i) {
 103                 isl_bool known;
 104
 105                 if (isl_int_is_zero(mat->row[pos][off + i]))
 106                         continue;
 107                 known = isl_local_div_is_known(local, i);
 108                 if (known < 0 || !known)
 109                         return known;
 110         }
 111
 112         return isl_bool_true;
 113 }
 114
 115 /* Does "local" have an explicit representation for all local variables?
 116  */
 117 isl_bool isl_local_divs_known(__isl_keep isl_local *local)
 118 {
 119         int i, n;
 120
 121         if (!local)
 122                 return isl_bool_error;
 123
 124         n = isl_local_dim(local, isl_dim_div);
 125         for (i = 0; i < n; ++i) {
 126                 isl_bool unknown = isl_local_div_is_marked_unknown(local, i);
 127                 if (unknown < 0 || unknown)
 128                         return isl_bool_not(unknown);
 129         }
 130
 131         return isl_bool_true;
 132 }
 133
 134 /* Compare two sets of local variables, defined over
 135  * the same space.
 136  *
 137  * Return -1 if "local1" is "smaller" than "local2", 1 if "local1" is "greater"
 138  * than "local2" and 0 if they are equal.
 139  *
 140  * The order is fairly arbitrary.  We do "prefer" divs that only involve
 141  * earlier dimensions in the sense that we consider matrices where
 142  * the first differing div involves earlier dimensions to be smaller.
 143  */
 144 int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2)
 145 {
 146         int i;
 147         int cmp;
 148         isl_bool unknown1, unknown2;
 149         int last1, last2;
 150         int n_col;
 151         isl_mat *mat1 = local1;
 152         isl_mat *mat2 = local2;
 153
 154         if (local1 == local2)
 155                 return 0;
 156         if (!local1)
 157                 return -1;
 158         if (!local2)
 159                 return 1;
 160
 161         if (mat1->n_row != mat2->n_row)
 162                 return mat1->n_row - mat2->n_row;
 163
 164         n_col = isl_mat_cols(mat1);
 165         for (i = 0; i < mat1->n_row; ++i) {
 166                 unknown1 = isl_local_div_is_marked_unknown(local1, i);
 167                 unknown2 = isl_local_div_is_marked_unknown(local2, i);
 168                 if (unknown1 && unknown2)
 169                         continue;
 170                 if (unknown1)
 171                         return 1;
 172                 if (unknown2)
 173                         return -1;
 174                 last1 = isl_seq_last_non_zero(mat1->row[i] + 1, n_col - 1);
 175                 last2 = isl_seq_last_non_zero(mat2->row[i] + 1, n_col - 1);
 176                 if (last1 != last2)
 177                         return last1 - last2;
 178                 cmp = isl_seq_cmp(mat1->row[i], mat2->row[i], n_col);
 179                 if (cmp != 0)
 180                         return cmp;
 181         }
 182
 183         return 0;
 184 }