isl_util.c

   1 #include "isl_util.h"
   2 #include <isl/set.h>
   3 #include <isl/map.h>
   4
   5 /* For any two pairs of corresponding writes and reads,
   6  * do the writes occur in a different order than the reads ?
   7  * If so, then the dependence is "reordering".
   8  */
   9 int isl_map_is_reordering(struct isl_map *dep)
  10 {
  11         isl_map *read_before;
  12         isl_map *write_after;
  13         int r;
  14
  15         read_before = isl_map_lex_lt(isl_space_range(isl_map_get_space(dep)));
  16         write_after = isl_map_lex_gt(isl_space_domain(isl_map_get_space(dep)));
  17         write_after = isl_map_apply_domain(write_after, isl_map_copy(dep));
  18         write_after = isl_map_apply_range(write_after, isl_map_copy(dep));
  19         write_after = isl_map_intersect(write_after, read_before);
  20
  21         r = !isl_map_is_empty(write_after);
  22
  23         isl_map_free(write_after);
  24
  25         return r;
  26 }
  27
  28 /* For reads from dep1 and dep2 from the same iteration,
  29  * does the corresponding write from dep1 occur before the write from dep2 ?
  30  *
  31  * The answer is no if we can find a write from dep1 that occurs
  32  * after a write from dep2 such that both writes correspond to the same read.
  33  */
  34 int isl_is_inorder_accesses(isl_map *dep1, isl_map *dep2)
  35 {
  36         isl_space *dim;
  37         isl_map *read_same;
  38         isl_map *write_after;
  39         int in_order;
  40
  41         dim = isl_space_map_from_set(isl_space_range(isl_map_get_space(dep1)));
  42         read_same = isl_map_identity(dim);
  43         write_after = isl_map_lex_gt(isl_space_domain(isl_map_get_space(dep1)));
  44         write_after = isl_map_apply_domain(write_after, isl_map_copy(dep1));
  45         write_after = isl_map_apply_range(write_after, isl_map_copy(dep2));
  46         write_after = isl_map_intersect(write_after, read_same);
  47
  48         in_order = isl_map_is_empty(write_after);
  49
  50         isl_map_free(write_after);
  51
  52         return in_order;
  53 }
  54
  55 /* For any pair of corresponding write and read,
  56  * is there any other read in between ?
  57  * If so, then the loop is not "consecutive".
  58  * If two reads occur "simultaneously", we also do not consider
  59  * the loop to be consecutive.
  60  */
  61 int isl_is_consecutive_loop(isl_map *dep)
  62 {
  63         isl_map *write_before;
  64         isl_map *read_after;
  65         int consecutive;
  66
  67         /* Check for simultaneous reads */
  68         if (!isl_is_inorder_accesses(dep, dep))
  69                 return 0;
  70
  71         /* Check for read strictly in between write and read */
  72         write_before = isl_map_lex_lt(isl_space_range(isl_map_get_space(dep)));
  73         read_after = isl_map_lex_gt(isl_space_range(isl_map_get_space(dep)));
  74         write_before = isl_map_intersect_range(write_before,
  75                                 isl_map_range(isl_map_copy(dep)));
  76         write_before = isl_map_apply_domain(write_before, isl_map_copy(dep));
  77         write_before = isl_map_intersect(write_before, read_after);
  78
  79         consecutive = isl_map_is_empty(write_before);
  80
  81         isl_map_free(write_before);
  82
  83         return consecutive;
  84 }
  85
  86 /* For any pair of corresponding write and read of dep2,
  87  * is there any read from dep1 in between ?
  88  * If so, then dep2 is not "consecutive".
  89  * If two reads occur "simultaneously", we also do not consider
  90  * the loop to be consecutive.
  91  */
  92 int isl_is_consecutive_dep(isl_map *dep2, isl_map *dep1)
  93 {
  94         isl_map *write_before;
  95         isl_map *read_after;
  96         int consecutive;
  97
  98         write_before = isl_map_lex_lt(isl_space_range(isl_map_get_space(dep2)));
  99         read_after = isl_map_lex_ge(isl_space_range(isl_map_get_space(dep2)));
 100         write_before = isl_map_intersect_range(write_before,
 101                                 isl_map_range(isl_map_copy(dep1)));
 102         write_before = isl_map_apply_domain(write_before, isl_map_copy(dep2));
 103         write_before = isl_map_intersect(write_before, read_after);
 104
 105         consecutive = isl_map_is_empty(write_before);
 106
 107         isl_map_free(write_before);
 108
 109         return consecutive;
 110 }
 111
 112 /* Check whether there is a pair of distinct reads, one from dep1 and dep2,
 113  * that correspond to the same write.
 114  */
 115 int isl_map_has_multiplicity(struct isl_map *dep)
 116 {
 117         isl_space *dim;
 118         isl_map *read_before;
 119         isl_map *write_same;
 120         int mult;
 121
 122         read_before = isl_map_lex_lt(isl_space_range(isl_map_get_space(dep)));
 123         dim = isl_space_map_from_set(isl_space_domain(isl_map_get_space(dep)));
 124         write_same = isl_map_identity(dim);
 125         write_same = isl_map_apply_domain(write_same, isl_map_copy(dep));
 126         write_same = isl_map_apply_range(write_same, isl_map_copy(dep));
 127         write_same = isl_map_intersect(write_same, read_before);
 128
 129         mult = !isl_map_is_empty(write_same);
 130
 131         isl_map_free(write_same);
 132
 133         return mult;
 134 }