isl_local.c

   1 /*
   2  * Copyright 2014      Ecole Normale Superieure
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege,
   7  * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
   8  */
   9
  10 #include <isl_mat_private.h>
  11 #include <isl_seq.h>
  12
  13 /* Given a matrix "div" representing local variables,
  14  * is the variable at position "pos" marked as not having
  15  * an explicit representation?
  16  * Note that even if this variable is not marked in this way and therefore
  17  * does have an explicit representation, this representation may still
  18  * depend (indirectly) on other local variables that do not
  19  * have an explicit representation.
  20  */
  21 isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_mat *div, int pos)
  22 {
  23         if (!div)
  24                 return isl_bool_error;
  25         if (pos < 0 || pos >= div->n_row)
  26                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
  27                         "position out of bounds", return isl_bool_error);
  28         return isl_int_is_zero(div->row[pos][0]);
  29 }
  30
  31 /* Given a matrix "div" representing local variables,
  32  * does the variable at position "pos" have a complete explicit representation?
  33  * Having a complete explicit representation requires not only
  34  * an explicit representation, but also that all local variables
  35  * that appear in this explicit representation in turn have
  36  * a complete explicit representation.
  37  */
  38 isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos)
  39 {
  40         isl_bool marked;
  41         int i, n, off;
  42
  43         if (!div)
  44                 return isl_bool_error;
  45         if (pos < 0 || pos >= div->n_row)
  46                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
  47                         "position out of bounds", return isl_bool_error);
  48
  49         marked = isl_local_div_is_marked_unknown(div, pos);
  50         if (marked < 0 || marked)
  51                 return isl_bool_not(marked);
  52
  53         n = isl_mat_rows(div);
  54         off = isl_mat_cols(div) - n;
  55
  56         for (i = n - 1; i >= 0; --i) {
  57                 isl_bool known;
  58
  59                 if (isl_int_is_zero(div->row[pos][off + i]))
  60                         continue;
  61                 known = isl_local_div_is_known(div, i);
  62                 if (known < 0 || !known)
  63                         return known;
  64         }
  65
  66         return isl_bool_true;
  67 }
  68
  69 /* Compare two matrices representing local variables, defined over
  70  * the same space.
  71  *
  72  * Return -1 if "div1" is "smaller" than "div2", 1 if "div1" is "greater"
  73  * than "div2" and 0 if they are equal.
  74  *
  75  * The order is fairly arbitrary.  We do "prefer" divs that only involve
  76  * earlier dimensions in the sense that we consider matrices where
  77  * the first differing div involves earlier dimensions to be smaller.
  78  */
  79 int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2)
  80 {
  81         int i;
  82         int cmp;
  83         isl_bool unknown1, unknown2;
  84         int last1, last2;
  85         int n_col;
  86
  87         if (div1 == div2)
  88                 return 0;
  89         if (!div1)
  90                 return -1;
  91         if (!div2)
  92                 return 1;
  93
  94         if (div1->n_row != div2->n_row)
  95                 return div1->n_row - div2->n_row;
  96
  97         n_col = isl_mat_cols(div1);
  98         for (i = 0; i < div1->n_row; ++i) {
  99                 unknown1 = isl_local_div_is_marked_unknown(div1, i);
 100                 unknown2 = isl_local_div_is_marked_unknown(div2, i);
 101                 if (unknown1 && unknown2)
 102                         continue;
 103                 if (unknown1)
 104                         return 1;
 105                 if (unknown2)
 106                         return -1;
 107                 last1 = isl_seq_last_non_zero(div1->row[i] + 1, n_col - 1);
 108                 last2 = isl_seq_last_non_zero(div2->row[i] + 1, n_col - 1);
 109                 if (last1 != last2)
 110                         return last1 - last2;
 111                 cmp = isl_seq_cmp(div1->row[i], div2->row[i], n_col);
 112                 if (cmp != 0)
 113                         return cmp;
 114         }
 115
 116         return 0;
 117 }