mem_bound.cc

   1 #include <vector>
   2 #include <isl/set.h>
   3 #include <isl/map.h>
   4 #include <isl/constraint.h>
   5 #include <isl/polynomial.h>
   6 #include <barvinok/isl.h>
   7 #include <isa/yaml.h>
   8 #include <isa/pdg.h>
   9 #include "da.h"
  10 #include "translation.h"
  11 #include "mem_options.h"
  12
  13 using std::vector;
  14 using pdg::PDG;
  15 using namespace da;
  16 using std::cout;
  17 using std::cerr;
  18 using std::endl;
  19
  20 /* Compute the number of array elements that are read but not
  21  * (previously) written.  These are assumed to be the input.
  22  */
  23 static __isl_give isl_pw_qpolynomial *compute_input_size(PDG *pdg,
  24         struct options *options)
  25 {
  26         unsigned nparam = pdg->params.size();
  27         isl_space *dim;
  28         isl_pw_qpolynomial *inputsize;
  29
  30         dim = isl_space_set_alloc(pdg->get_isl_ctx(), nparam, 0);
  31         isl_dim_set_parameter_names(dim, pdg->params);
  32         inputsize = isl_pw_qpolynomial_zero(dim);
  33
  34         if (!options->with_input)
  35                 return inputsize;
  36
  37         for (int i = 0; i < pdg->dependences.size(); ++i) {
  38                 isl_map *map;
  39                 isl_pw_qpolynomial *size;
  40                 pdg::dependence *dep = pdg->dependences[i];
  41
  42                 if (dep->type != pdg::dependence::uninitialized)
  43                         continue;
  44
  45                 map = dep->relation->get_isl_map(pdg->get_isl_ctx());
  46                 size = isl_map_card(map);
  47                 inputsize = isl_pw_qpolynomial_add(inputsize, size);
  48         }
  49
  50         return inputsize;
  51 }
  52
  53 /* Compute the number of elements in domain for a fixed value
  54  * of the "fixed_loops" outer loop iterators and return this value
  55  * as a function of these loop iterators and the parameters.
  56  */
  57 static __isl_give isl_pw_qpolynomial *compute_accesses_at(
  58         __isl_take isl_set *domain, int fixed_loops)
  59 {
  60         isl_map *map;
  61         map = isl_map_from_range(domain);
  62         map = isl_map_move_dims(map, isl_dim_in, 0, isl_dim_out, 0, fixed_loops);
  63         return isl_map_card(map);
  64 }
  65
  66 static __isl_give isl_map *less_than(__isl_take isl_space *dim,
  67         enum isl_dim_type type1, unsigned pos1,
  68         enum isl_dim_type type2, unsigned pos2)
  69 {
  70         isl_int v;
  71         struct isl_constraint *c;
  72         struct isl_basic_map *bmap;
  73
  74         isl_int_init(v);
  75
  76         bmap = isl_basic_map_universe(isl_space_copy(dim));
  77         c = isl_inequality_alloc(isl_local_space_from_space(dim));
  78         isl_int_set_si(v, 1);
  79         isl_constraint_set_coefficient(c, type2, pos2, v);
  80         isl_int_set_si(v, -1);
  81         isl_constraint_set_coefficient(c, type1, pos1, v);
  82         isl_constraint_set_constant(c, v);
  83         bmap = isl_basic_map_add_constraint(bmap, c);
  84
  85         isl_int_clear(v);
  86
  87         return isl_map_from_basic_map(bmap);
  88 }
  89
  90 /* Compute the number of elements in domain for a fixed value
  91  * of the "level" outer loop iterators and for all values of the
  92  * loop iterator at level "level" smaller than a fixed value
  93  * and return this value as a function of these (level+1) loop iterators
  94  * and the parameters.
  95  */
  96 static __isl_give isl_pw_qpolynomial *compute_accesses_before(
  97         __isl_take isl_set *domain, int level)
  98 {
  99         isl_map *map;
 100         map = isl_map_from_range(domain);
 101         map = isl_map_move_dims(map, isl_dim_in, 0, isl_dim_out, 0, level);
 102         map = isl_map_add_dims(map, isl_dim_in, 1);
 103         map = isl_map_intersect(map,
 104                 less_than(isl_map_get_space(map), isl_dim_out, 0,
 105                                                 isl_dim_in, level));
 106         return isl_map_card(map);
 107 }
 108
 109 static int cmp_prefix_stat_dims(pdg::node *node, int *stat_dims, int d)
 110 {
 111     for (int j = 0; j < d; ++j)
 112         if (node->prefix[2*j] != stat_dims[j])
 113             return node->prefix[2*j] - stat_dims[j];
 114
 115     return 0;
 116 }
 117
 118 /*
 119  * Returns true if dependence is independent of first n_loops loops.
 120  */
 121 static int is_loop_independent(isl_ctx *ctx,
 122         pdg::IslMap *relation, int n_loops)
 123 {
 124         isl_map *rel;
 125         isl_map *test;
 126         assert(relation->input() >= n_loops);
 127         assert(relation->output() >= n_loops);
 128         int indep;
 129
 130         rel = relation->get_isl_map(ctx);
 131         test = isl_map_universe(isl_map_get_space(rel));
 132         for (int i = 0; i < n_loops; ++i)
 133                 test = isl_map_equate(test, isl_dim_in, i, isl_dim_out, i);
 134         indep = isl_map_is_subset(rel, test);
 135         isl_map_free(rel);
 136         isl_map_free(test);
 137
 138         return indep;
 139 }
 140
 141 struct contribution {
 142     unsigned    is_read : 1;
 143     unsigned    is_written : 1;
 144 };
 145
 146 /*
 147  * Determines the net contribution of "dep" within statements
 148  * with statement level dimensions prefixed by stat_dims
 149  * and within a fixed iteration of the first n_loop loops.
 150  */
 151 static struct contribution net_contribution(isl_ctx *ctx, pdg::dependence *dep,
 152                                             int *stat_dims, int d, int n_loop,
 153                                             struct options *options)
 154 {
 155     struct contribution c;
 156     c.is_read = 0;
 157     c.is_written = 0;
 158
 159     if (dep->type == pdg::dependence::uninitialized) {
 160         if (options->with_input &&
 161                 cmp_prefix_stat_dims(dep->to, stat_dims, d) == 0)
 162             c.is_read = 1;
 163     } else {
 164         int is_written = cmp_prefix_stat_dims(dep->from, stat_dims, d) == 0;
 165         int is_read = cmp_prefix_stat_dims(dep->to, stat_dims, d) == 0;
 166         int is_local = is_written && is_read &&
 167                                 is_loop_independent(ctx, dep->relation, n_loop);
 168         if (!is_local) {
 169             c.is_read = is_read;
 170             c.is_written = is_written;
 171         }
 172     }
 173
 174     return c;
 175 }
 176
 177 struct access {
 178     isl_set     *read;
 179     isl_set     *write;
 180 };
 181
 182 /*
 183  * Compute increment in statement/loop identified by stat_dims
 184  */
 185 static __isl_give isl_pw_qpolynomial *compute_live_increment(PDG *pdg,
 186         int *stat_dims, int d, struct access *accesses, struct options *options)
 187 {
 188     unsigned nparam = pdg->params.size();
 189     isl_space *dim;
 190     isl_pw_qpolynomial *sum;
 191
 192     dim = isl_space_set_alloc(pdg->get_isl_ctx(), nparam, d - 1);
 193     isl_dim_set_parameter_names(dim, pdg->params);
 194     sum = isl_pw_qpolynomial_zero(dim);
 195     for (int i = 0; i < pdg->dependences.size(); ++i) {
 196         pdg::dependence *dep = pdg->dependences[i];
 197         struct contribution c;
 198
 199         c = net_contribution(pdg->get_isl_ctx(),
 200                                 dep, stat_dims, d, d-1, options);
 201
 202         if (c.is_written) {
 203             isl_pw_qpolynomial *inc;
 204             inc = compute_accesses_at(isl_set_copy(accesses[i].write), d - 1);
 205             sum = isl_pw_qpolynomial_add(sum, inc);
 206         }
 207         if (c.is_read) {
 208             isl_pw_qpolynomial *dec;
 209             dec = compute_accesses_at(isl_set_copy(accesses[i].read), d - 1);
 210             sum = isl_pw_qpolynomial_sub(sum, dec);
 211         }
 212     }
 213     return sum;
 214 }
 215
 216 /*
 217  * Compute increment in previous iterations of loop at given level.
 218  */
 219 static __isl_give isl_pw_qpolynomial *compute_live_increment_in_loop(PDG *pdg,
 220         int *stat_dims, int level, struct access *accesses,
 221         struct options *options)
 222 {
 223     unsigned nparam = pdg->params.size();
 224     isl_space *dim;
 225     isl_pw_qpolynomial *sum;
 226
 227     dim = isl_space_set_alloc(pdg->get_isl_ctx(), nparam, level + 1);
 228     isl_dim_set_parameter_names(dim, pdg->params);
 229     sum = isl_pw_qpolynomial_zero(dim);
 230     for (int i = 0; i < pdg->dependences.size(); ++i) {
 231         pdg::dependence *dep = pdg->dependences[i];
 232         struct contribution c;
 233
 234         c = net_contribution(pdg->get_isl_ctx(),
 235                                 dep, stat_dims, level+1, level+1, options);
 236
 237         if (c.is_written) {
 238             isl_pw_qpolynomial *inc;
 239             inc = compute_accesses_before(isl_set_copy(accesses[i].write), level);
 240             sum = isl_pw_qpolynomial_add(sum, inc);
 241         }
 242         if (c.is_read) {
 243             isl_pw_qpolynomial *dec;
 244             dec = compute_accesses_before(isl_set_copy(accesses[i].read), level);
 245             sum = isl_pw_qpolynomial_sub(sum, dec);
 246         }
 247     }
 248     return sum;
 249 }
 250
 251 struct tree;
 252
 253 struct tree {
 254     int d;
 255     int *stat_dims;
 256     vector<struct tree*> children;
 257     isl_set             *domain;
 258 };
 259
 260 /*
 261  * Compute bound on number of live array elements in the
 262  * given (sub)tree.
 263  *
 264  * live_before: number of live elements before the loop/statement
 265  *              in terms of the outer loop iterators
 266  */
 267 static __isl_give isl_pw_qpolynomial_fold *compute_bound(PDG *pdg,
 268                                         __isl_take isl_pw_qpolynomial *live,
 269                                         struct tree *tree,
 270                                         struct access *accesses,
 271                                         struct options *options)
 272 {
 273     /* If we are in a leaf, we actually compute the bound. */
 274     if (tree->children.size() == 0) {
 275         isl_set *domain;
 276         isl_pw_qpolynomial_fold *bound;
 277
 278         domain = isl_set_copy(tree->domain);
 279         live = isl_pw_qpolynomial_intersect_domain(live, domain);
 280         bound = isl_pw_qpolynomial_bound(live, isl_fold_max, NULL);
 281
 282         return bound;
 283     }
 284
 285     isl_pw_qpolynomial_fold *pwf;
 286
 287     /* If we are not in the outer dummy loop, add contribution of
 288      * previous iterations.
 289      */
 290     if (tree->d > 0) {
 291         isl_space *dim;
 292         isl_pw_qpolynomial *inc;
 293
 294         live = isl_pw_qpolynomial_add_dims(live, isl_dim_set, 1);
 295         inc = compute_live_increment_in_loop(pdg, tree->stat_dims, tree->d-1,
 296                                             accesses, options);
 297         live = isl_pw_qpolynomial_add(live, inc);
 298     }
 299
 300     pwf = compute_bound(pdg, isl_pw_qpolynomial_copy(live),
 301                         tree->children[0], accesses, options);
 302     for (int i = 1; i < tree->children.size(); ++i) {
 303         isl_pw_qpolynomial_fold *pwf_i;
 304         isl_pw_qpolynomial *inc;
 305         struct tree *child = tree->children[i-1];
 306         inc = compute_live_increment(pdg, child->stat_dims, child->d,
 307                                     accesses, options);
 308         live = isl_pw_qpolynomial_add(live, inc);
 309         pwf_i = compute_bound(pdg, isl_pw_qpolynomial_copy(live),
 310                                 tree->children[i], accesses, options);
 311         pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
 312     }
 313     isl_pw_qpolynomial_free(live);
 314     return pwf;
 315 }
 316
 317 /*
 318  * Construct a tree for all statements whose statement dimensions
 319  * start with the d first elements of stat_dims.
 320  * The first one of those statemens is statement n.
 321  */
 322 static struct tree *compute_tree(PDG *pdg, int *stat_dims, int d, int n)
 323 {
 324     struct tree *tree = new struct tree;
 325     tree->domain = NULL;
 326     tree->d = d;
 327     tree->stat_dims = new int[d];
 328     for (int i = 0; i < d; ++i)
 329         tree->stat_dims[i] = stat_dims[i];
 330
 331     if (pdg->nodes[n]->prefix.size() == 2*d-1) {
 332         tree->domain = pdg->nodes[n]->source->get_isl_set(pdg->get_isl_ctx());
 333         return tree;
 334     }
 335
 336     for (int i = n; i < pdg->nodes.size(); ++i) {
 337         if (cmp_prefix_stat_dims(pdg->nodes[i], stat_dims, d) > 0)
 338             break;
 339
 340         stat_dims[d] = pdg->nodes[i]->prefix[2*d];
 341
 342         struct tree *child = compute_tree(pdg, stat_dims, d+1, i);
 343         tree->children.push_back(child);
 344
 345         /* Skip over nodes with the same prefix at current level */
 346         for (; i+1 < pdg->nodes.size(); ++i)
 347             if (cmp_prefix_stat_dims(pdg->nodes[i+1], stat_dims, d+1) != 0)
 348                 break;
 349     }
 350     return tree;
 351 }
 352
 353 static struct tree *compute_tree(PDG *pdg)
 354 {
 355     int n_stat_dims = normalize_prefix(pdg);
 356     int stat_dims[n_stat_dims];
 357
 358     return compute_tree(pdg, stat_dims, 0, 0);
 359 }
 360
 361 static void free_tree(struct tree *tree)
 362 {
 363     for (int i = 0; i < tree->children.size(); ++i)
 364         free_tree(tree->children[i]);
 365     delete [] tree->stat_dims;
 366     isl_set_free(tree->domain);
 367     delete tree;
 368 }
 369
 370 static void compute_bound(PDG *pdg, struct options *options)
 371 {
 372     struct tree *tree = compute_tree(pdg);
 373
 374     struct access accesses[pdg->dependences.size()];
 375     for (int i = 0; i < pdg->dependences.size(); ++i) {
 376         pdg::dependence *dep = pdg->dependences[i];
 377         isl_map *rel = dep->relation->get_isl_map(pdg->get_isl_ctx());
 378
 379         accesses[i].write = isl_map_domain(isl_map_copy(rel));
 380         accesses[i].read = isl_map_range(rel);
 381     }
 382
 383     isl_pw_qpolynomial *inputsize;
 384     inputsize = compute_input_size(pdg, options);
 385
 386     isl_pw_qpolynomial_fold *pwf;
 387     pwf = compute_bound(pdg, inputsize, tree, accesses, options);
 388     free_tree(tree);
 389     isl_set *context = pdg->get_context_isl_set();
 390     pwf = isl_pw_qpolynomial_fold_gist(pwf, context);
 391
 392     isl_printer *printer;
 393     printer = isl_printer_to_file(pdg->get_isl_ctx(), stdout);
 394     printer = isl_printer_set_output_format(printer, ISL_FORMAT_C);
 395     printer = isl_printer_print_pw_qpolynomial_fold(printer, pwf);
 396     printer = isl_printer_end_line(printer);
 397     isl_printer_free(printer);
 398
 399     isl_pw_qpolynomial_fold_free(pwf);
 400
 401     for (int i = 0; i < pdg->dependences.size(); ++i) {
 402         isl_set_free(accesses[i].write);
 403         isl_set_free(accesses[i].read);
 404     }
 405 }
 406
 407 int main(int argc, char * argv[])
 408 {
 409     PDG *pdg;
 410     isl_ctx *ctx = isl_ctx_alloc();
 411     struct options *options = options_new_with_defaults();
 412
 413     argc = options_parse(options, argc, argv, ISL_ARG_ALL);
 414
 415
 416     pdg = PDG::Load(stdin, ctx);
 417     int nparam = pdg->params.size();
 418
 419     for (int i = 0; i < pdg->arrays.size(); ++i)
 420         find_deps(pdg, pdg->arrays[i], data_reuse);
 421
 422     compute_bound(pdg, options);
 423
 424     pdg->free();
 425     delete pdg;
 426     options_free(options);
 427     isl_ctx_free(ctx);
 428
 429     return 0;
 430 }