pdg.cc

   1 #include <isa/pdg.h>
   2 #include <algorithm>
   3 #include <vector>
   4 #include "version.h"
   5
   6 #include <isl/ctx.h>
   7 #include <isl/space.h>
   8 #include <isl/set.h>
   9 #include <isl/map.h>
  10 #include <isl/printer.h>
  11
  12 using namespace pdg;
  13 using std::vector;
  14
  15 static at_init register_history_entry(history_entry::register_type);
  16
  17 void history_entry::register_type()
  18 {
  19     static struct_description d = { create };
  20     YAML_PTR_FIELD(d, history_entry, tool, str);
  21     YAML_PTR_FIELD(d, history_entry, version, str);
  22     YAML_SEQ_FIELD(d, history_entry, arguments, str);
  23     structure::register_type("perl/history_entry", &typeid(history_entry), &d.d);
  24 }
  25
  26 static at_init register_pdg(PDG::register_type);
  27
  28 void PDG::register_type()
  29 {
  30     static struct_description pdg_d = { create };
  31     YAML_INT_FIELD(pdg_d, PDG, dimension);
  32     YAML_INT_FIELD(pdg_d, PDG, cacheline);
  33     YAML_INT_FIELD(pdg_d, PDG, root);
  34     YAML_PTR_FIELD(pdg_d, PDG, placement, str);
  35     YAML_SEQ_FIELD(pdg_d, PDG, nodes, node);
  36     YAML_SEQ_FIELD(pdg_d, PDG, arrays, array);
  37     YAML_SEQ_FIELD(pdg_d, PDG, dependences, dependence);
  38     YAML_SEQ_FIELD(pdg_d, PDG, params, parameter);
  39     YAML_PTR_FIELD(pdg_d, PDG, context, IslSet);
  40     YAML_SEQ_FIELD(pdg_d, PDG, history, history_entry);
  41     YAML_PTR_FIELD(pdg_d, PDG, name, str);
  42     YAML_SEQ_FIELD(pdg_d, PDG, statement_dimensions, int);
  43     structure::register_type("perl/PDG", &typeid(PDG), &pdg_d.d);
  44 }
  45
  46 PDG *PDG::Load(char *str, isl_ctx *ctx)
  47 {
  48     return yaml::Load<PDG>(str, ctx);
  49 }
  50
  51 PDG *PDG::Load(FILE *fp, isl_ctx *ctx)
  52 {
  53     return yaml::Load<PDG>(fp, ctx);
  54 }
  55
  56 PDG::~PDG()
  57 {
  58     if (ctx_created)
  59         isl_ctx_free(ctx);
  60 }
  61
  62 isl_ctx *PDG::get_isl_ctx()
  63 {
  64     if (!ctx) {
  65         ctx = isl_ctx_alloc();
  66         assert(ctx);
  67         ctx_created = true;
  68     }
  69     return ctx;
  70 }
  71
  72 /* Return the context of this PDG.
  73  * If this PDG has no context, then return a universe parametric set
  74  * with the same parameters as this PDG.
  75  */
  76 isl_set *PDG::get_context_isl_set()
  77 {
  78     isl_ctx *ctx = get_isl_ctx();
  79     isl_set *set;
  80
  81     if (context) {
  82         set = context->get_isl_set(ctx);
  83     } else {
  84         isl_space *dims = isl_space_params_alloc(ctx, params.size());
  85         isl_dim_set_parameter_names(dims, params);
  86         set = isl_set_universe(dims);
  87     }
  88
  89     return set;
  90 }
  91
  92 void PDG::add_history_line(const char *tool, int argc, char * argv[])
  93 {
  94     history_entry *he = new history_entry();
  95     he->tool = new str(string(tool));
  96     he->version = new str(string(pdg_version()));
  97     for (int i = 1; i < argc; ++i)
  98         he->arguments.push_back(new str(argv[i]));
  99     history.push_back(he);
 100 }
 101
 102 static at_init register_array(array::register_type);
 103
 104 void array::register_type()
 105 {
 106     static const char *at_names[array::last];
 107     at_names[input] = "input";
 108     at_names[output] = "output";
 109     at_names[temp] = "temp";
 110     static struct_description d = { create };
 111     YAML_INT_FIELD(d, array, id);
 112     YAML_PTR_FIELD(d, array, name, str);
 113     YAML_SEQ_FIELD(d, array, dims, int);
 114     YAML_PTR_FIELD(d, array, element_type, str);
 115     YAML_ENUM_FIELD(d, array, type, at_names);
 116     YAML_SEQ_FIELD(d, array, analysis_performed, dependence_type);
 117     YAML_PTR_FIELD(d, array, value_bounds, IslSet);
 118     YAML_INT_FIELD(d, array, uniquely_defined);
 119     YAML_INT_FIELD(d, array, killed);
 120     structure::register_type("perl/array", &typeid(array), &d.d);
 121 }
 122
 123 static at_init register_parameter(parameter::register_type);
 124
 125 void parameter::register_type()
 126 {
 127     static struct_description d = { create };
 128     YAML_INT_FIELD(d, parameter, id);
 129     YAML_PTR_FIELD(d, parameter, name, str);
 130     YAML_PTR_FIELD(d, parameter, value, integer);
 131     structure::register_type("perl/parameter", &typeid(parameter), &d.d);
 132 }
 133
 134 void pdg::isl_dim_set_parameter_names(isl_space *dim,
 135                                         const seq<parameter>& params)
 136 {
 137         for (int i = 0; i < params.size(); ++i)
 138                 dim = isl_space_set_dim_name(dim, isl_dim_param, i,
 139                                         params[i]->name->s.c_str());
 140 }
 141
 142 isl_set *pdg::isl_set_set_parameter_names(isl_set *set,
 143                                             const seq<parameter>& params)
 144 {
 145         for (int i = 0; i < params.size(); ++i)
 146                 set = isl_set_set_dim_name(set, isl_dim_param, i,
 147                                             params[i]->name->s.c_str());
 148         return set;
 149 }
 150
 151 static at_init register_access(pdg::access::register_type);
 152
 153 void pdg::access::register_type()
 154 {
 155     static const char *at_names[access::last];
 156     at_names[write] = "write";
 157     at_names[read] = "read";
 158     static struct_description d = { create };
 159     YAML_PTR_FIELD(d, pdg::access, array, pdg::array);
 160     YAML_ENUM_FIELD(d, pdg::access, type, at_names);
 161     YAML_PTR_FIELD(d, pdg::access, map, IslMap);
 162     YAML_INT_FIELD(d, pdg::access, nr);
 163     YAML_PTR_FIELD(d, pdg::access, extension, IslMap);
 164     YAML_PTR_FIELD(d, pdg::access, extended_map, IslMap);
 165     YAML_SEQ_FIELD(d, pdg::access, nested, call_or_access);
 166     YAML_SEQ_FIELD(d, pdg::access, sources, IslMap);
 167     structure::register_type("perl/access", &typeid(pdg::access), &d.d);
 168 }
 169
 170 static at_init register_function_call(function_call::register_type);
 171
 172 void function_call::register_type()
 173 {
 174     static struct_description s_d = { create };
 175     YAML_SEQ_FIELD(s_d, function_call, arguments, call_or_access);
 176     YAML_PTR_FIELD(s_d, function_call, name, str);
 177     structure::register_type("perl/function_call", &typeid(function_call), &s_d.d);
 178 }
 179
 180 static at_init register_call_or_access(call_or_access::register_type);
 181
 182 void call_or_access::register_type()
 183 {
 184     static const char *cat_names[call_or_access::last];
 185     cat_names[t_access] = "access";
 186     cat_names[t_call] = "call";
 187     static struct_description s_d = { create };
 188     YAML_ENUM_FIELD(s_d, pdg::call_or_access, type, cat_names);
 189     YAML_PTR_FIELD(s_d, pdg::call_or_access, access, pdg::access);
 190     YAML_PTR_FIELD(s_d, pdg::call_or_access, call, function_call);
 191     structure::register_type("perl/call_or_access", &typeid(call_or_access), &s_d.d);
 192 }
 193
 194 static at_init register_stat(statement::register_type);
 195
 196 void statement::register_type()
 197 {
 198     static struct_description s_d = { create };
 199     YAML_INT_FIELD(s_d, statement, operation);
 200     YAML_INT_FIELD(s_d, statement, line);
 201     YAML_SEQ_FIELD(s_d, statement, accesses, access);
 202     YAML_PTR_FIELD(s_d, statement, top_function, function_call);
 203     YAML_SEQ_FIELD(s_d, statement, top_outputs, access);
 204     structure::register_type("perl/statement", &typeid(statement), &s_d.d);
 205 }
 206
 207 static at_init register_node(node::register_type);
 208
 209 void node::register_type()
 210 {
 211     static struct_description node_d = { create };
 212     YAML_INT_FIELD(node_d, node, nr);
 213     YAML_PTR_FIELD(node_d, node, name, str);
 214     YAML_PTR_FIELD(node_d, node, source, IslSet);
 215     YAML_PTR_FIELD(node_d, node, schedule, IslMap);
 216     YAML_PTR_FIELD(node_d, node, statement, pdg::statement);
 217     YAML_SEQ_FIELD(node_d, node, prefix, int);
 218     YAML_SEQ_FIELD(node_d, node, filters, call_or_access);
 219     structure::register_type("perl/node", &typeid(node), &node_d.d);
 220 }
 221
 222 static at_init register_dependence(dependence::register_type);
 223
 224 void dependence::register_type()
 225 {
 226     static const char *dt_names[dependence::last];
 227     dt_names[flow] = "flow";
 228     dt_names[anti] = "anti";
 229     dt_names[pn] = "pn";
 230     dt_names[pn_union] = "pn_union";
 231     dt_names[pn_part] = "pn_part";
 232     dt_names[pn_wire] = "pn_wire";
 233     dt_names[pn_hold] = "pn_hold";
 234     dt_names[pn_shift] = "pn_shift";
 235     dt_names[reuse] = "reuse";
 236     dt_names[reuse_pair] = "reuse_pair";
 237     dt_names[output] = "output";
 238     dt_names[uninitialized] = "uninitialized";
 239     static struct_description dependence_d = { create };
 240     YAML_PTR_FIELD(dependence_d, dependence, relation, IslMap);
 241     YAML_PTR_FIELD(dependence_d, dependence, extended_relation, IslMap);
 242     YAML_PTR_FIELD(dependence_d, dependence, controlled_relation, IslMap);
 243     YAML_PTR_FIELD(dependence_d, dependence, from, pdg::node);
 244     YAML_PTR_FIELD(dependence_d, dependence, to, pdg::node);
 245     YAML_PTR_FIELD(dependence_d, dependence, from_access, pdg::access);
 246     YAML_PTR_FIELD(dependence_d, dependence, to_access, pdg::access);
 247     YAML_ENUM_FIELD(dependence_d, dependence, type, dt_names);
 248     YAML_PTR_FIELD(dependence_d, dependence, array, pdg::array);
 249     YAML_SEQ_FIELD(dependence_d, dependence, from_controls, str);
 250     YAML_SEQ_FIELD(dependence_d, dependence, to_controls, str);
 251     YAML_INT_FIELD(dependence_d, dependence, reordering);
 252     YAML_INT_FIELD(dependence_d, dependence, multiplicity);
 253     YAML_PTR_FIELD(dependence_d, dependence, size, enumerator);
 254     YAML_PTR_FIELD(dependence_d, dependence, container, dependence);
 255     YAML_PTR_FIELD(dependence_d, dependence, value_size, integer);
 256     structure::register_type("perl/dependence", &typeid(dependence), &dependence_d.d);
 257
 258     static struct_description dependence_type_d = { dependence_type::create };
 259     YAML_ENUM_FIELD(dependence_type_d, dependence_type, type, dt_names);
 260     structure::register_type("perl/dependence_type", &typeid(dependence_type), &dependence_type_d.d);
 261 }
 262
 263 static at_init register_enumerator(pdg::enumerator::register_type);
 264
 265 void pdg::enumerator::register_type()
 266 {
 267     static struct_description e_d = { create, convert };
 268     structure::register_type("perl/PDG::enumerator", &typeid(enumerator), &e_d.d);
 269 }
 270
 271 void pdg::enumerator::init(SyckParser *p, SyckNode *n)
 272 {
 273     s = new string(n->data.str->ptr, n->data.str->len);
 274 }
 275
 276 serialize *pdg::enumerator::convert(anchor_map *am, serialize *node,
 277         const type_info *type)
 278 {
 279         str *s = dynamic_cast<str *>(node);
 280         pdg::enumerator *e;
 281
 282         if (!s)
 283                 return NULL;
 284
 285         e = new enumerator(new string(s->s));
 286
 287         delete node;
 288
 289         return e;
 290 }
 291
 292 void pdg::enumerator::dump(emitter& e)
 293 {
 294     if (s)
 295         yll_emitter_write_string(e.e, s->c_str());
 296     else if (value >= 0)
 297         yll_emitter_write_int(e.e, value);
 298     else
 299         assert(0);
 300 }
 301
 302 pdg::enumerator::~enumerator()
 303 {
 304     if (s)
 305         delete s;
 306 }
 307
 308 static at_init register_isl_set(IslSet::register_type);
 309
 310 void IslSet::register_type()
 311 {
 312         static struct_description s_d = { create, convert };
 313         structure::register_type("", &typeid(IslSet), &s_d.d);
 314 }
 315
 316 serialize *IslSet::convert(anchor_map *am, serialize *node,
 317         const type_info *type)
 318 {
 319         str *s = dynamic_cast<str *>(node);
 320         isl_ctx *ctx = (isl_ctx *) am->user;
 321         isl_set *set;
 322
 323         if (s) {
 324                 set = isl_set_read_from_str(ctx, s->s.c_str());
 325                 delete node;
 326                 return new IslSet(set);
 327         }
 328
 329         return NULL;
 330 }
 331
 332 void IslSet::dump(emitter &e)
 333 {
 334         isl_printer *p;
 335         char *s;
 336
 337         if (!set) {
 338                 yll_emitter_write_null(e.e);
 339                 return;
 340         }
 341
 342         p = isl_printer_to_str(isl_set_get_ctx(set));
 343         p = isl_printer_print_set(p, set);
 344         s = isl_printer_get_str(p);
 345         isl_printer_free(p);
 346
 347         yll_emitter_write_string(e.e, s);
 348
 349         ::free(s);
 350 }
 351
 352 static at_init register_isl_map(IslMap::register_type);
 353
 354 void IslMap::register_type()
 355 {
 356         static struct_description s_d = { create, convert };
 357         structure::register_type("", &typeid(IslMap), &s_d.d);
 358 }
 359
 360 serialize *IslMap::convert(anchor_map *am, serialize *node,
 361         const type_info *type)
 362 {
 363         str *s = dynamic_cast<str *>(node);
 364         isl_ctx *ctx = (isl_ctx *) am->user;
 365         isl_map *map;
 366
 367         if (s) {
 368                 map = isl_map_read_from_str(ctx, s->s.c_str());
 369                 delete node;
 370                 return new IslMap(map);
 371         }
 372
 373         return NULL;
 374 }
 375
 376 void IslMap::dump(emitter &e)
 377 {
 378         isl_printer *p;
 379         char *s;
 380
 381         if (!map) {
 382                 yll_emitter_write_null(e.e);
 383                 return;
 384         }
 385
 386         p = isl_printer_to_str(isl_map_get_ctx(map));
 387         p = isl_printer_print_map(p, map);
 388         s = isl_printer_get_str(p);
 389         isl_printer_free(p);
 390
 391         yll_emitter_write_string(e.e, s);
 392
 393         ::free(s);
 394 }
 395
 396 /* Schedule the given dependence relations "map" according to the schedules
 397  * of the source and target of "dep".
 398  */
 399 __isl_give isl_map *pdg::schedule_dependence(PDG *pdg, pdg::dependence *dep,
 400         __isl_take isl_map *map)
 401 {
 402         isl_map *sr = dep->to->schedule->get_isl_map();
 403         map = isl_map_apply_range(map, sr);
 404         if (dep->from) {
 405                 isl_map *sw = dep->from->schedule->get_isl_map();
 406                 map = isl_map_apply_domain(map, sw);
 407         }
 408
 409         return map;
 410 }
 411
 412 __isl_give isl_map *pdg::scatter_dependence(PDG *pdg, pdg::dependence *dep)
 413 {
 414         return schedule_dependence(pdg, dep, dep->relation->get_isl_map());
 415 }
 416
 417 /* Assuming this is a read access, construct a map from the domain
 418  * of the access relation to the access relation of the corresponding
 419  * writes.  If we are unable to determine the corresponding writes, then
 420  * return a map to the read access.
 421  *
 422  * For example, if the access relation is
 423  *
 424  *      S[i] -> A[]
 425  *
 426  * and there is a single source of the form
 427  *
 428  *      [W[0,i] -> A[]] -> [S[i] -> A[]]
 429  *
 430  * then the returned map is
 431  *
 432  *      S[i] -> [W[0,i] -> A[]]
 433  *
 434  * If there are multiple writes involved, then the range of the result lives
 435  * in different spaces.
 436  *
 437  * If no source was found then return
 438  *
 439  *      S[i] -> [S[i] -> A[]]
 440  */
 441 __isl_give isl_union_map *pdg::access::extract_access_map()
 442 {
 443         isl_ctx *ctx;
 444         isl_map *access_map;
 445         isl_union_map *res;
 446
 447         access_map = map->get_isl_map();
 448         access_map = isl_map_reverse(isl_map_domain_map(access_map));
 449
 450         if (sources.size() == 0)
 451                 return isl_union_map_from_map(access_map);
 452
 453         ctx = isl_map_get_ctx(access_map);
 454         res = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
 455
 456         for (int i = 0; i < sources.size(); ++i) {
 457                 isl_map *source_map;
 458                 source_map = sources[i]->get_isl_map();
 459                 source_map = isl_map_reverse(source_map);
 460                 source_map = isl_map_apply_range(isl_map_copy(access_map),
 461                                                 source_map);
 462                 res = isl_union_map_add_map(res, source_map);
 463         }
 464
 465         isl_map_free(access_map);
 466
 467         return res;
 468 }
 469
 470 /* Return the number of outer loops that are affected by filters.
 471  *
 472  * A loop iterator is affected by a filter if it is involved
 473  * in any of the iteration domain constraints that also involves filters,
 474  * if any of the filter accesses depends on the loop iterator,
 475  * or if any of the sources of a filter depends on the loop iterator.
 476  * If no sources were recorded, then we conservatively assume that
 477  * all loops are affected by filters.
 478  */
 479 int node::get_filter_depth()
 480 {
 481         isl_map *value;
 482         isl_set *dom;
 483         int n_in, n_out;
 484
 485         if (filter_depth >= 0)
 486                 return filter_depth;
 487
 488         filter_depth = 0;
 489         value = isl_set_unwrap(source->get_isl_set());
 490         n_in = isl_map_dim(value, isl_dim_in);
 491         n_out = isl_map_dim(value, isl_dim_out);
 492
 493         dom = isl_map_domain(isl_map_copy(value));
 494         value = isl_map_gist_domain(value, isl_set_copy(dom));
 495         for (int j = n_in - 1; j >= 0; --j) {
 496                 if (!isl_map_involves_dims(value, isl_dim_in, j, 1))
 497                         continue;
 498                 if (j >= filter_depth)
 499                         filter_depth = j + 1;
 500                 break;
 501         }
 502
 503         for (int i = 0; i < n_out; ++i) {
 504                 pdg::call_or_access *coa;
 505
 506                 coa = filters[i];
 507                 assert(coa->type == pdg::call_or_access::t_access);
 508
 509                 if (coa->access->sources.size() == 0) {
 510                         filter_depth = n_in;
 511                         break;
 512                 }
 513
 514                 for (int j = 0; j < coa->access->sources.size(); ++j) {
 515                         isl_map *map;
 516                         map = coa->access->sources[j]->get_isl_map();
 517                         map = isl_map_zip(map);
 518                         map = isl_set_unwrap(isl_map_domain(map));
 519                         map = isl_map_gist_range(map, isl_set_copy(dom));
 520
 521                         for (int k = n_in - 1; k >= 0; --k) {
 522                                 if (!isl_map_involves_dims(map,
 523                                                             isl_dim_out, k, 1))
 524                                         continue;
 525                                 if (k >= filter_depth)
 526                                         filter_depth = k + 1;
 527                                 break;
 528                         }
 529
 530                         isl_map_free(map);
 531                 }
 532
 533                 for (int j = n_in - 1; j >= 0; --j) {
 534                         if (!isl_map_involves_dims(coa->access->map->map,
 535                                                     isl_dim_in, j, 1))
 536                                 continue;
 537                         if (j >= filter_depth)
 538                                 filter_depth = j + 1;
 539                         break;
 540                 }
 541
 542         }
 543         isl_set_free(dom);
 544         isl_map_free(value);
 545
 546         return filter_depth;
 547 }