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  * does the variable at position "pos" have an explicit representation?
  15  */
  16 isl_bool isl_local_div_is_known(__isl_keep isl_mat *div, int pos)
  17 {
  18         if (!div)
  19                 return isl_bool_error;
  20         if (pos < 0 || pos >= div->n_row)
  21                 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
  22                         "position out of bounds", return isl_bool_error);
  23         return !isl_int_is_zero(div->row[pos][0]);
  24 }
  25
  26 /* Compare two matrices representing local variables, defined over
  27  * the same space.
  28  *
  29  * Return -1 if "div1" is "smaller" than "div2", 1 if "div1" is "greater"
  30  * than "div2" and 0 if they are equal.
  31  *
  32  * The order is fairly arbitrary.  We do "prefer" divs that only involve
  33  * earlier dimensions in the sense that we consider matrices where
  34  * the first differing div involves earlier dimensions to be smaller.
  35  */
  36 int isl_local_cmp(__isl_keep isl_mat *div1, __isl_keep isl_mat *div2)
  37 {
  38         int i;
  39         int cmp;
  40         int known1, known2;
  41         int last1, last2;
  42         int n_col;
  43
  44         if (div1 == div2)
  45                 return 0;
  46         if (!div1)
  47                 return -1;
  48         if (!div2)
  49                 return 1;
  50
  51         if (div1->n_row != div2->n_row)
  52                 return div1->n_row - div2->n_row;
  53
  54         n_col = isl_mat_cols(div1);
  55         for (i = 0; i < div1->n_row; ++i) {
  56                 known1 = isl_local_div_is_known(div1, i);
  57                 known2 = isl_local_div_is_known(div2, i);
  58                 if (!known1 && !known2)
  59                         continue;
  60                 if (!known1)
  61                         return 1;
  62                 if (!known2)
  63                         return -1;
  64                 last1 = isl_seq_last_non_zero(div1->row[i] + 1, n_col - 1);
  65                 last2 = isl_seq_last_non_zero(div2->row[i] + 1, n_col - 1);
  66                 if (last1 != last2)
  67                         return last1 - last2;
  68                 cmp = isl_seq_cmp(div1->row[i], div2->row[i], n_col);
  69                 if (cmp != 0)
  70                         return cmp;
  71         }
  72
  73         return 0;
  74 }