mem_bound.cc

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