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