schedule.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <assert.h>
  12 #include <ctype.h>
  13 #include <string.h>
  14
  15 #include <isl/set.h>
  16 #include <isl/map.h>
  17 #include <isl/constraint.h>
  18
  19 #include "schedule.h"
  20
  21 /* Construct a map that maps a domain of dimensionality "len"
  22  * to another domain of the same dimensionality such that
  23  * coordinate "first" of the range is equal to the sum of the "wave_len"
  24  * coordinates starting at "first" in the domain.
  25  * The remaining coordinates in the range are equal to the corresponding ones
  26  * in the domain.
  27  * "dim" prescribes the parameters.
  28  */
  29 __isl_give isl_map *wavefront(__isl_take isl_dim *dim, int len,
  30         int first, int wave_len)
  31 {
  32     int i;
  33     isl_int v;
  34     isl_basic_map *bmap;
  35     isl_constraint *c;
  36
  37     isl_int_init(v);
  38
  39     dim = isl_dim_add(dim, isl_dim_in, len);
  40     dim = isl_dim_add(dim, isl_dim_out, len);
  41     bmap = isl_basic_map_universe(isl_dim_copy(dim));
  42
  43     for (i = 0; i < len; ++i) {
  44         if (i == first)
  45             continue;
  46
  47         c = isl_equality_alloc(isl_dim_copy(dim));
  48         isl_int_set_si(v, -1);
  49         isl_constraint_set_coefficient(c, isl_dim_in, i, v);
  50         isl_int_set_si(v, 1);
  51         isl_constraint_set_coefficient(c, isl_dim_out, i, v);
  52         bmap = isl_basic_map_add_constraint(bmap, c);
  53     }
  54
  55     c = isl_equality_alloc(isl_dim_copy(dim));
  56     isl_int_set_si(v, -1);
  57     for (i = 0; i < wave_len; ++i)
  58         isl_constraint_set_coefficient(c, isl_dim_in, first + i, v);
  59     isl_int_set_si(v, 1);
  60     isl_constraint_set_coefficient(c, isl_dim_out, first, v);
  61     bmap = isl_basic_map_add_constraint(bmap, c);
  62
  63     isl_dim_free(dim);
  64     isl_int_clear(v);
  65
  66     return isl_map_from_basic_map(bmap);
  67 }
  68
  69 /* Construct a map from a len-dimensional domain to
  70  * a (len-n)-dimensional domain that projects out the n coordinates
  71  * starting at first.
  72  * "dim" prescribes the parameters.
  73  */
  74 __isl_give isl_map *project_out(__isl_take isl_dim *dim,
  75     int len, int first, int n)
  76 {
  77     int i, j;
  78     isl_constraint *c;
  79     isl_basic_map *bmap;
  80     isl_int v;
  81
  82     isl_int_init(v);
  83
  84     dim = isl_dim_add(dim, isl_dim_in, len);
  85     dim = isl_dim_add(dim, isl_dim_out, len - n);
  86     bmap = isl_basic_map_universe(isl_dim_copy(dim));
  87
  88     for (i = 0, j = 0; i < len; ++i) {
  89         if (i >= first && i < first + n)
  90             continue;
  91         c = isl_equality_alloc(isl_dim_copy(dim));
  92         isl_int_set_si(v, -1);
  93         isl_constraint_set_coefficient(c, isl_dim_in, i, v);
  94         isl_int_set_si(v, 1);
  95         isl_constraint_set_coefficient(c, isl_dim_out, j, v);
  96         bmap = isl_basic_map_add_constraint(bmap, c);
  97         ++j;
  98     }
  99     isl_dim_free(dim);
 100
 101     isl_int_clear(v);
 102
 103     return isl_map_from_basic_map(bmap);
 104 }
 105
 106 /* Construct a projection that maps a src_len dimensional domain
 107  * to its first dst_len coordinates.
 108  * "dim" prescribes the parameters.
 109  */
 110 __isl_give isl_map *projection(__isl_take isl_dim *dim,
 111     int src_len, int dst_len)
 112 {
 113     return project_out(dim, src_len, dst_len, src_len - dst_len);
 114 }
 115
 116 /* Extend "set" with unconstrained coordinates to a total length of "dst_len".
 117  */
 118 __isl_give isl_set *extend(__isl_take isl_set *set, int dst_len)
 119 {
 120     int n_set;
 121     isl_dim *dim;
 122     isl_map *map;
 123
 124     dim = isl_set_get_dim(set);
 125     n_set = isl_dim_size(dim, isl_dim_set);
 126     dim = isl_dim_drop(dim, isl_dim_set, 0, n_set);
 127     map = projection(dim, dst_len, n_set);
 128     map = isl_map_reverse(map);
 129
 130     return isl_set_apply(set, map);
 131 }