isl_util.c

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