size.cc

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