mem.cc

   1 #include <isl/aff.h>
   2 #include <isl/ast_build.h>
   3 #include <barvinok/isl.h>
   4 #include <isa/yaml.h>
   5 #include <isa/pdg.h>
   6 #include "da.h"
   7 #include "mem_options.h"
   8
   9 #define ALLOC(type) (type*)malloc(sizeof(type))
  10
  11 using pdg::PDG;
  12 using namespace da;
  13
  14 static void dump_program(PDG *pdg, int *output, struct options *options);
  15
  16 int main(int argc, char * argv[])
  17 {
  18     PDG *pdg;
  19     isl_ctx *ctx;
  20     struct options *options = options_new_with_defaults();
  21
  22     argc = options_parse(options, argc, argv, ISL_ARG_ALL);
  23
  24     ctx = isl_ctx_alloc_with_options(&options_args, options);
  25
  26     pdg = PDG::Load(stdin, ctx);
  27     int output[pdg->arrays.size()];
  28
  29     for (int i = 0; i < pdg->arrays.size(); ++i) {
  30         int n = pdg->dependences.size();
  31         find_deps(pdg, pdg->arrays[i], data_reuse);
  32         output[i] = n == pdg->dependences.size();
  33     }
  34
  35     dump_program(pdg, output, options);
  36     pdg->free();
  37     delete pdg;
  38     isl_ctx_free(ctx);
  39
  40     return 0;
  41 }
  42
  43 static __isl_give isl_map *schedule(__isl_take isl_set *domain,
  44         pdg::node *node, pdg::access *ac, int dep, int maxdim, int write)
  45 {
  46     int fulldim = node->prefix.size() + 1;
  47     isl_map *schedule;
  48     int dim;
  49
  50     schedule = isl_map_from_domain(domain);
  51     schedule = isl_map_add_dims(schedule, isl_dim_out, 2);
  52     schedule = isl_map_fix_si(schedule, isl_dim_out, 0, ac->nr);
  53     schedule = isl_map_fix_si(schedule, isl_dim_out, 1, dep);
  54     schedule = isl_set_identity(isl_map_wrap(schedule));
  55     schedule = isl_map_flatten_range(schedule);
  56
  57     for (int i = 0; i < node->prefix.size(); ++i) {
  58         if (node->prefix[i] == -1)
  59             continue;
  60         schedule = isl_map_insert_dims(schedule, isl_dim_out, i, 1);
  61         schedule = isl_map_fix_si(schedule, isl_dim_out, i, node->prefix[i]);
  62     }
  63
  64     dim = isl_map_dim(schedule, isl_dim_out);
  65     schedule = isl_map_project_out(schedule, isl_dim_out, dim - 1, 1);
  66     dim--;
  67     schedule = isl_map_add_dims(schedule, isl_dim_out, maxdim - dim);
  68     for (int i = dim; i < maxdim; ++i)
  69         schedule = isl_map_fix_si(schedule, isl_dim_out, i, 0);
  70
  71     if (write)
  72         schedule = isl_map_set_tuple_name(schedule, isl_dim_in, "write");
  73     else
  74         schedule = isl_map_set_tuple_name(schedule, isl_dim_in, "read");
  75
  76     return schedule;
  77 }
  78
  79 /* Compute the number of array elements that are read but not
  80  * (previously) written.  These are assumed to be the input.
  81  */
  82 static __isl_give isl_pw_qpolynomial *compute_input_size(PDG *pdg,
  83         struct options *options)
  84 {
  85         unsigned nparam = pdg->params.size();
  86         isl_space *space;
  87         isl_pw_qpolynomial *inputsize;
  88
  89         space = isl_space_set_alloc(pdg->get_isl_ctx(), nparam, 1);
  90         isl_dim_set_parameter_names(space, pdg->params);
  91         inputsize = isl_pw_qpolynomial_zero(space);
  92
  93         if (!options->with_input)
  94                 return inputsize;
  95
  96         for (int i = 0; i < pdg->dependences.size(); ++i) {
  97                 isl_map *map;
  98                 isl_pw_qpolynomial *size;
  99                 pdg::dependence *dep = pdg->dependences[i];
 100
 101                 if (dep->type != pdg::dependence::uninitialized)
 102                         continue;
 103
 104                 map = dep->relation->get_isl_map(pdg->get_isl_ctx());
 105                 size = isl_set_card(isl_map_range(map));
 106                 inputsize = isl_pw_qpolynomial_add(inputsize, size);
 107         }
 108
 109         return inputsize;
 110 }
 111
 112 static __isl_give isl_printer *print_user(__isl_take isl_printer *p,
 113         __isl_take isl_ast_print_options *print_options,
 114         __isl_keep isl_ast_node *node, void *user)
 115 {
 116         isl_id *id;
 117         isl_ast_expr *expr, *arg;
 118         const char *name;
 119
 120         expr = isl_ast_node_user_get_expr(node);
 121         arg = isl_ast_expr_get_op_arg(expr, 0);
 122         id = isl_ast_expr_get_id(arg);
 123         name = isl_id_get_name(id);
 124         if (!strcmp(name, "write")) {
 125                 p = isl_printer_start_line(p);
 126                 p = isl_printer_print_str(p, "if (++count > max)");
 127                 p = isl_printer_end_line(p);
 128                 p = isl_printer_indent(p, 4);
 129                 p = isl_printer_start_line(p);
 130                 p = isl_printer_print_str(p, "max = count;");
 131                 p = isl_printer_end_line(p);
 132                 p = isl_printer_indent(p, -4);
 133         } else {
 134                 p = isl_printer_start_line(p);
 135                 p = isl_printer_print_str(p, "--count;");
 136                 p = isl_printer_end_line(p);
 137         }
 138         isl_id_free(id);
 139         isl_ast_expr_free(arg);
 140         isl_ast_expr_free(expr);
 141         isl_ast_print_options_free(print_options);
 142         return p;
 143 }
 144
 145 static void print(__isl_keep isl_ast_node *tree, const char *inputsize)
 146 {
 147         isl_ctx *ctx;
 148         FILE *out = stdout;
 149         isl_printer *p;
 150         isl_ast_print_options *print_options;
 151
 152         ctx = isl_ast_node_get_ctx(tree);
 153
 154         p = isl_printer_to_file(ctx, out);
 155         p = isl_printer_set_output_format(p, ISL_FORMAT_C);
 156
 157         p = isl_printer_start_line(p);
 158         p = isl_printer_print_str(p, "#include <stdio.h>");
 159         p = isl_printer_end_line(p);
 160
 161         p = isl_ast_node_print_macros(tree, p);
 162
 163         p = isl_printer_start_line(p);
 164         p = isl_printer_print_str(p, "int main() {");
 165         p = isl_printer_end_line(p);
 166
 167         p = isl_printer_indent(p, 4);
 168
 169         p = isl_printer_start_line(p);
 170         p = isl_printer_print_str(p, "long count = ");
 171         p = isl_printer_print_str(p, inputsize);
 172         p = isl_printer_print_str(p, ";");
 173         p = isl_printer_end_line(p);
 174
 175         p = isl_printer_start_line(p);
 176         p = isl_printer_print_str(p, "long max = count;");
 177         p = isl_printer_end_line(p);
 178
 179         print_options = isl_ast_print_options_alloc(ctx);
 180         print_options = isl_ast_print_options_set_print_user(print_options,
 181                                                             &print_user, NULL);
 182         p = isl_ast_node_print(tree, p, print_options);
 183
 184         p = isl_printer_start_line(p);
 185         p = isl_printer_print_str(p, "printf(\"final: %ld\\n\", count);");
 186         p = isl_printer_end_line(p);
 187
 188         p = isl_printer_start_line(p);
 189         p = isl_printer_print_str(p, "printf(\"max: %ld\\n\", max);");
 190         p = isl_printer_end_line(p);
 191
 192         p = isl_printer_start_line(p);
 193         p = isl_printer_print_str(p, "return 0;");
 194         p = isl_printer_end_line(p);
 195
 196         p = isl_printer_indent(p, -4);
 197
 198         p = isl_printer_start_line(p);
 199         p = isl_printer_print_str(p, "}");
 200         p = isl_printer_end_line(p);
 201
 202         isl_printer_free(p);
 203 }
 204
 205 static void dump_program(PDG *pdg, int *output, struct options *options)
 206 {
 207     int nparam = pdg->params.size();
 208     isl_ctx *ctx = pdg->get_isl_ctx();
 209     isl_set *context = pdg->get_context_isl_set();
 210     isl_map *sched_i;
 211     isl_union_map *sched;
 212     isl_ast_build *build;
 213     isl_ast_node *tree;
 214     int maxdim = 0;
 215     isl_pw_qpolynomial *inputsize;
 216     isl_printer *p;
 217     char *s_inputsize;
 218
 219     inputsize = compute_input_size(pdg, options);
 220     inputsize = isl_pw_qpolynomial_gist(inputsize, isl_set_copy(context));
 221     p = isl_printer_to_str(pdg->get_isl_ctx());
 222     p = isl_printer_set_output_format(p, ISL_FORMAT_C);
 223     p = isl_printer_print_pw_qpolynomial(p, inputsize);
 224     s_inputsize = isl_printer_get_str(p);
 225     isl_printer_free(p);
 226     isl_pw_qpolynomial_free(inputsize);
 227
 228     sched = isl_union_map_empty(isl_set_get_space(context));
 229
 230     for (int i = 0; i < pdg->nodes.size(); ++i) {
 231         pdg::node *node = pdg->nodes[i];
 232         if (node->prefix.size() + 1 > maxdim)
 233             maxdim = node->prefix.size() + 1;
 234     }
 235
 236     for (int i = 0; i < pdg->nodes.size(); ++i) {
 237         pdg::node *node = pdg->nodes[i];
 238         pdg::statement *s = pdg->nodes[i]->statement;
 239
 240         for (int j = 0; j < pdg->dependences.size(); ++j) {
 241             pdg::dependence *dep = pdg->dependences[j];
 242             if (dep->to != pdg->nodes[i] && dep->from != pdg->nodes[i])
 243                 continue;
 244             if (!options->with_input &&
 245                     dep->type == pdg::dependence::uninitialized)
 246                 continue;
 247             isl_map *rel = dep->relation->get_isl_map(pdg->get_isl_ctx());
 248             if (dep->to == pdg->nodes[i]) {
 249                     isl_set *read = isl_map_range(isl_map_copy(rel));
 250                     sched_i = schedule(read, dep->to, dep->to_access, j,
 251                                         maxdim, 0);
 252                     sched = isl_union_map_add_map(sched, sched_i);
 253             }
 254             if (dep->from == pdg->nodes[i]) {
 255                     isl_set *write = isl_map_domain(isl_map_copy(rel));
 256                     sched_i = schedule(write, dep->from, dep->from_access, j,
 257                                         maxdim, 1);
 258                     sched = isl_union_map_add_map(sched, sched_i);
 259             }
 260             isl_map_free(rel);
 261         }
 262         for (int j = 0; j < s->accesses.size(); ++j) {
 263             pdg::access *access = s->accesses[j];
 264             if (access->type == pdg::access::read)
 265                 continue;
 266             int k;
 267             for (k = 0; k < pdg->arrays.size(); ++k)
 268                 if (pdg->arrays[k] == access->array)
 269                     break;
 270             if (!output[k])
 271                 continue;
 272             isl_set *source = node->source->get_isl_set(pdg->get_isl_ctx());
 273             sched_i = schedule(source, node, access, -(j + 1), maxdim, 1);
 274             sched = isl_union_map_add_map(sched, sched_i);
 275         }
 276     }
 277
 278     build = isl_ast_build_from_context(context);
 279     tree = isl_ast_build_ast_from_schedule(build, sched);
 280     isl_ast_build_free(build);
 281
 282     print(tree, s_inputsize);
 283
 284     isl_ast_node_free(tree);
 285
 286     free(s_inputsize);
 287 }