size.cc

   1 #include <iostream>
   2 #include <sstream>
   3 #include <stdlib.h>
   4 #include <unistd.h>
   5 #include <isl/set.h>
   6 #include <isl/map.h>
   7 #include <barvinok/isl.h>
   8 #include "size.h"
   9 #include "size_bernstein.h"
  10 #include "size_simulate.h"
  11 #include "size_options.h"
  12 #include "config.h"
  13
  14 namespace size {
  15
  16 using std::cerr;
  17 using std::endl;
  18 using std::ostream;
  19
  20 #ifndef USE_SIZE_SIMULATE
  21 int selfloop_size_simulate(__isl_take isl_map *dep, __isl_take isl_set *read)
  22 {
  23         isl_map_free(dep);
  24         isl_set_free(read);
  25         return -1;
  26 }
  27 #endif
  28
  29 static bool is_rectangular_dependence(__isl_keep isl_map *dep)
  30 {
  31         int ok;
  32         isl_set *dom;
  33
  34         ok = isl_map_is_translation(dep);
  35         assert(ok >= 0);
  36         if (!ok)
  37                 return false;
  38
  39         dom = isl_map_domain(isl_map_copy(dep));
  40         ok = isl_set_is_box(dom);
  41         isl_set_free(dom);
  42         assert(ok >= 0);
  43
  44         return ok;
  45 }
  46
  47 /* Compute the number of tokens in the FIFO at the reference point(s) ref.
  48  * That is, the number of dependences that have started but not finished
  49  * before any point in ref.  Note that the same read iteration may
  50  * depend on several write iterations, so we cannot simply count the
  51  * number of writes and reads and take the differences, as the total
  52  * number of reads may be smaller than the total number of writes.
  53  * Instead, we set up two mappings between the reference point
  54  * and the dependences, one where the write happens before the
  55  * reference point and one where the read happens before the reference
  56  * point.  We then take the set difference and then count the number
  57  * of elements in this difference.
  58  */
  59 isl_pw_qpolynomial *selfloop_tokens_in_fifo(__isl_take isl_map *dep,
  60         __isl_take isl_set *ref)
  61 {
  62         int d;
  63         isl_set *dep_set;
  64         isl_map *read_before_ref;
  65         isl_map *write_before_ref;
  66
  67         dep = isl_map_make_disjoint(dep);
  68         ref = isl_set_make_disjoint(ref);
  69
  70         d = isl_map_dim(dep, isl_dim_in);
  71         dep = isl_map_move_dims(dep, isl_dim_in, d, isl_dim_out, 0, d);
  72         dep_set = isl_map_domain(dep);
  73
  74         read_before_ref = isl_map_lex_gt(isl_set_get_space(ref));
  75         read_before_ref = isl_map_intersect_domain(read_before_ref, ref);
  76         write_before_ref = isl_map_copy(read_before_ref);
  77
  78         read_before_ref = isl_map_insert_dims(read_before_ref, isl_dim_out, 0, d);
  79         write_before_ref = isl_map_add_dims(write_before_ref, isl_dim_out, d);
  80
  81         read_before_ref = isl_map_intersect_range(read_before_ref,
  82                                                 isl_set_copy(dep_set));
  83         write_before_ref = isl_map_intersect_range(write_before_ref, dep_set);
  84
  85         write_before_ref = isl_map_subtract(write_before_ref, read_before_ref);
  86
  87         return isl_map_card(write_before_ref);
  88 }
  89
  90 /* Compute the maximum of the difference in number of writes and number
  91  * of reads before any read.  The difference is equal to the number
  92  * of token in the FIFO and the maximum is the buffer size of the FIFO.
  93  * The procedure assumes that the dependence is non-parametric and
  94  * may actually iterate over all reads to compute the maximum.
  95  */
  96 static int selfloop_size_full(__isl_take isl_map *dep,
  97         __isl_take isl_set *ref)
  98 {
  99         isl_pw_qpolynomial *qp_diff;
 100         isl_val *v;
 101         int size;
 102
 103         qp_diff = selfloop_tokens_in_fifo(dep, ref);
 104
 105         v = isl_pw_qpolynomial_max(qp_diff);
 106         assert(isl_val_is_int(v));
 107
 108         size = isl_val_get_num_si(v);
 109
 110         isl_val_free(v);
 111
 112         return size;
 113 }
 114
 115 enumerator::operator pdg::enumerator *() const
 116 {
 117     switch (type) {
 118     case fixed:
 119         return new pdg::enumerator(v);
 120     case qp:
 121     case fold: {
 122         isl_printer *printer;
 123         char *str;
 124         string *s;
 125         printer = isl_printer_to_str(pdg->get_isl_ctx());
 126         printer = isl_printer_set_output_format(printer, ISL_FORMAT_C);
 127         if (type == qp)
 128                 printer = isl_printer_print_pw_qpolynomial(printer, pwqp);
 129         else
 130                 printer = isl_printer_print_pw_qpolynomial_fold(printer, pwf);
 131         str = isl_printer_get_str(printer);
 132         s = new string(str);
 133         isl_printer_free(printer);
 134         free(str);
 135         return new pdg::enumerator(s);
 136     }
 137     default:
 138         assert(0);
 139     }
 140 }
 141
 142 integer *enumerator::evaluate() const
 143 {
 144     switch (type) {
 145     case fixed:
 146         return new integer(v);
 147     case qp:
 148     case fold: {
 149         isl_space *dim;
 150         isl_point *pnt;
 151         isl_val *n;
 152         int v;
 153
 154         dim = isl_space_params_alloc(pdg->get_isl_ctx(), pdg->params.size());
 155         isl_dim_set_parameter_names(dim, pdg->params);
 156         pnt = isl_point_zero(dim);
 157         for (int i = 0; i < pdg->params.size(); ++i) {
 158                 int n = pdg->params[i]->value->v;
 159                 pnt = isl_point_add_ui(pnt, isl_dim_param, i, n);
 160         }
 161         if (type == enumerator::qp)
 162                 n = isl_pw_qpolynomial_eval(
 163                         isl_pw_qpolynomial_copy(pwqp), pnt);
 164         else
 165                 n = isl_pw_qpolynomial_fold_eval(
 166                         isl_pw_qpolynomial_fold_copy(pwf), pnt);
 167         n = isl_val_floor(n);
 168         v = isl_val_get_num_si(n);
 169         isl_val_free(n);
 170         return new integer(v);
 171     }
 172     default:
 173         assert(0);
 174     }
 175     return NULL;
 176 }
 177
 178 size::enumerator *selfloop_size(pdg::PDG *pdg, __isl_take isl_map *dep,
 179                                size_options *options)
 180 {
 181     int nparam = isl_map_dim(dep, isl_dim_param);
 182     isl_set *read;
 183
 184     assert(isl_map_dim(dep, isl_dim_in) == isl_map_dim(dep, isl_dim_out));
 185
 186     read = isl_map_range(isl_map_copy(dep));
 187
 188     bool rect = !nparam && is_rectangular_dependence(dep);
 189
 190     size::enumerator *e = NULL;
 191     if (!nparam && options->flags != SIZE_BERNSTEIN) {
 192         int maxsize;
 193         if (options->flags == SIZE_SIMULATE) {
 194             maxsize = selfloop_size_simulate(dep, read);
 195         } else if (!rect)
 196             maxsize = selfloop_size_full(dep, read);
 197         else {
 198             isl_set *ref = isl_set_lexmin(read);
 199             maxsize = selfloop_size_full(dep, ref);
 200         }
 201         e = new enumerator(maxsize);
 202     } else {
 203         e = selfloop_size_bernstein(pdg, dep, read);
 204     }
 205
 206     return e;
 207 }
 208
 209 }