size.cc

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